（c++）数据结构与算法之图：邻接矩阵、深度广度遍历、构造最小生成树（prim、kruskal算法）

//图的邻接矩阵实现 //广度遍历bfs和深度遍历dfs //构造最小生成树的prim、kruskal算法 #include <iostream> #include<stack> #include<queue> #define WEIGHTMAX 100 #define VERTEXMAX 50 #define VISITED 1 #define UNVISITED 0 using namespace std; class ufset //等价类 { private: int n; //个数 int *root,*next,*length; //等价类代表元、下一个元素、该元素所在等价类的元素个数 public: friend class graph; ufset(int s) //初始时均各自为等价类 { root=new int[s]; next=new int[s]; length=new int[s]; n=s; for(int i=0;i<s;i++) { root[i]=next[i]=i; length[i]=1; } } ~ufset() { delete [] root; delete [] next; delete [] length; } void show() //输出 { cout<<"root:"<<endl; for(int i=0;i<n;i++) { cout<<root[i]<<" "; } cout<<endl; cout<<"next:"<<endl; for(int i=0;i<n;i++) { cout<<next[i]<<" "; } cout<<endl; cout<<"length:"<<endl; for(int i=0;i<n;i++) { cout<<length[i]<<" "; } cout<<endl; } void Union(int u,int v) //两个等价类的合并 { if(length[root[u]]<length[root[v]]) { int temp=u; u=v; v=temp; } if(root[u]==root[v]) return; int p=next[root[u]]; //next next[root[u]]=next[root[v]]; next[root[v]]=p; length[root[v]]=1; //length length[root[u]]++; int oldroot=root[v]; //root for(int i=0;i<n;i++) if(root[i]==oldroot) root[i]=root[u]; } bool unionOK(int u,int v) //两个元素是否在同一个等价类中 { if(root[v]==root[u]) return true; else return false; } }; class edge //边类（数据公开） { public: int start,end; int weight; friend class graph; edge(){}; edge(int w) { weight=w; } edge(int s,int e,int w) { start=s; end=e; weight=w; } }; void visit(int v) { cout<<v<<"-->"; } class graph { private: int **matrix; //邻接矩阵 int v_num,e_num; //结点数、边数 int *mark; //用于判断是否被访问的数组(0:未访问 1:已访问 ) public: graph(){}; graph(int v) { if(v>=VERTEXMAX) cout<<"construct false"<<endl; v_num=v; e_num=0; mark=new int[v_num]; for(int i=0;i<v_num;i++) mark[i]=0; matrix=new int*[v_num]; int i,j; for(i=0;i<v_num;i++) matrix[i]=new int[v_num]; for(i=0;i<v_num;i++) for(j=0;j<v_num;j++) matrix[i][j]=0; } ~graph() { delete mark; for(int i=0;i<v_num;i++) delete [] matrix[i]; delete [] matrix; } void resetMark() //重置节点标记数组 { for(int i=0;i<v_num;i++) mark[i]=0; } bool isEdge(edge onee) //判断是否为边 { if(matrix[onee.start][onee.end]>0&& matrix[onee.start][onee.end]<WEIGHTMAX&& matrix[onee.end][onee.start]>0&& matrix[onee.end][onee.start]<WEIGHTMAX) return true; else return false; } void setEdge(int start,int end,int weight) //给图添加一条边 { if(matrix[start][end]==0&&matrix[end][start]==0) { e_num++; } matrix[start][end]=weight; matrix[end][start]=weight; } void delEdge(int start,int end) //删除图中一条边 { if(matrix[start][end]!=0&&matrix[end][start]!=0) e_num--; else return; matrix[start][end]=0; matrix[end][start]=0; } void showEdge() //展示邻接矩阵 { cout<<"邻接矩阵如下： "<<endl; for(int i=0;i<v_num;i++) for(int j=0;j<v_num;j++) { cout<<matrix[i][j]<<" "; if(j==v_num-1) cout<<endl; } } edge firstEdge(int v) //返回该结点按顺序的第一条边 { edge e(v,v,0); for(int i=0;i<v_num;i++) { if(matrix[v][i]!=0) { e.end=i; e.weight=matrix[v][i]; return e; } } cout<<"this vertex dont have edge"<<endl; return e; } edge nextEdge(int v,edge onee) //返回该边的下一条边（同头结点） { for(int i=onee.end+1;i<v_num;i++) { if(matrix[v][i]!=0) { edge e(v,i,matrix[v][i]); return e; } } cout<<"no next edge"<<endl; return onee; } void dfs_traverse(graph g,int fir) //递归深度遍历 { mark[fir]=1; cout<<fir<<"-->"; for(int i=0;i<v_num;i++) { if(g.matrix[fir][i]>=1&&!mark[i]) dfs_traverse(g,i); } } void dfs_notraverse() //非递归深度遍历（用栈实现） { resetMark(); stack<int> s; for(int i=0;i<v_num;i++) { if(mark[i]==0) { s.push(i); while(!s.empty()) { int pc=s.top(); s.pop(); if(mark[pc]==0) visit(pc); mark[pc]=1; for(int j=v_num-1;j>0;j--) //for(int j=0;j<v_num;j++) //??? 为何顺序颠倒？？？ { if(matrix[pc][j]>0&&matrix[pc][j]<WEIGHTMAX) if(mark[j]==0) s.push(j); } } } } } void bfs() //广度遍历（用队列实现） { resetMark(); queue<int> q; for(int i=0;i<v_num;i++) { if(mark[i]==0) { q.push(i); while(!q.empty()) { int pc=q.front(); q.pop(); if(mark[pc]==0) visit(pc); mark[pc]=1; for(int j=0;j<v_num;j++) //for(int j=v_num;j>=0;j--) //????? { if(matrix[pc][j]>0&&matrix[pc][j]<WEIGHTMAX) if(mark[j]==0) q.push(j); } } } } } void prim() //prim { resetMark(); int x=0,y=0; //下标 edge *e=new edge[v_num-1]; //构建的最小生成树的边组成的数组 int *ver=new int[v_num]; //结点的数组，用于统计哪些结点已被构建，当数组满时说明构建完成 {//初始化markedge for(int i=0;i<v_num;i++) ver[i]=-1; } ver[0]=0; //放入首个结点 mark[0]=1; y++; while(y<v_num) //如果结点没有全部访问完则循环 { int minWeight=WEIGHTMAX,sta,en; for(int i=0;ver[i]!=-1;i++) //遍历寻找权重最小的边 { for(int j=0;j<v_num;j++) { //如果边满足：权重最小、边的尾结点未被访问，则加入边的尾结点 if(matrix[ver[i]][j]!=0&&minWeight>matrix[ver[i]][j] &&mark[j]==0) { minWeight=matrix[ver[i]][j]; sta=ver[i]; en=j; } } } edge temp(sta,en,minWeight); e[x++]=temp; ver[y++]=en; mark[en]=1; } {//展示结果： cout<<"插入边顺序： "<<endl; for(int i=0;i<v_num-1;i++) cout<<e[i].start<<"---"<<e[i].weight<<"--->"<<e[i].end<<endl; cout<<"插入结点顺序： "; for(int i=0;i<v_num;i++) cout<<ver[i]<<" "; cout<<endl; } delete [] ver; delete [] e; } void kruskal() //kruskal { int n=v_num,union_num=0; queue<edge> q; ufset ufs(n); {//遍历使所有边按权重从小到大的顺序排成数组,进队 edge eq[e_num]; int x=0; int **edgew=new int*[n]; edgew=matrix; while(x<+e_num) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(edgew[i][j]!=0) { edge e(i,j,edgew[i][j]); eq[x++]=e; edgew[i][j]=edgew[j][i]=0; } } } } for(int i=0;i<e_num;i++) { int minweight=eq[i].weight; for(int j=0;j<e_num;j++) { if(eq[j].weight>minweight) { minweight=eq[j].weight; edge temp; temp=eq[j]; eq[j]=eq[i]; eq[i]=temp; } } } for(int i=0;i<e_num;i++) q.push(eq[i]); delete edgew; } cout<<"边插入顺序："<<endl; while(!q.empty()) { edge e=q.front(); q.pop(); if(!ufs.unionOK(e.start,e.end)) { cout<<e.start<<"---"<<e.weight<<"--->"<<e.end<<endl; ufs.Union(e.start,e.end); } } cout<<"结点插入顺序："; for(int i=0;i<n;i++) { cout<<ufs.next[i]<<" "; } cout<<endl; } }; int main() { graph a(8); {//set edge（初始化图） a.setEdge(0,1,1); a.setEdge(0,2,2); a.setEdge(1,3,3); a.setEdge(1,4,5); a.setEdge(3,7,4); a.setEdge(4,7,4); a.setEdge(2,6,1); a.setEdge(2,5,3); a.setEdge(5,6,2); } cout<<"带权无向图：(P160 4-12)"<<endl; a.showEdge(); cout<<" node1 first edge's weight: "<<a.firstEdge(1).weight<<endl; cout<<"node2 first edge's next edge's weight: "<<a.nextEdge(2,a.firstEdge(2)).weight<<endl; cout<<"递归深度遍历： "; a.dfs_traverse(a,0); cout<<endl; cout<<"非递归深度遍历： "; a.dfs_notraverse(); cout<<endl; cout<<" 广度遍历： "; a.bfs(); cout<<endl; cout<<"prim:"<<endl; a.prim(); cout<<"kruskal:"<<endl; a.kruskal(); cout << "Hello world!" << endl; return 0; }