数据结构邻接矩阵DFS非递归算法以及PRIM算法最小生成树

#include<iostream> #include<string> using namespace std; #define MAX_NUM 30 #define MAX 400 typedef struct //用于储存顶点信息 { int num; //编号 string name; //其他信息 }VertexType; typedef struct //图 { int edges[MAX_NUM][MAX_NUM]; //邻接矩阵 int vexnum,arcnum; //顶点数，弧数 VertexType vex[MAX_NUM]; //存放顶点信息 }MGraph; typedef struct { VertexType adjvex; //顶点 int lowcost; //权值 }closedge[MAX_NUM]; void CreatMGraph(MGraph &M) { int const INF=32767; int v,a; cout<<"首先创建一个图\n"; cout<<"输入顶点数：\n"; cin>>v; M.vexnum=v; cout<<"输入弧数:\n"; cin>>a; M.arcnum=a; for(int i=1;i<=v;i++) { for(int j=1;j<=v;j++) { if(i==j) M.edges[i][j]=0; else M.edges[i][j]=INF; } } cout<<"输入一条弧的两个顶点和这条弧的权值（例如 1 2 3 代表点1和点2之间的弧权值为3）:\n"; for(int i=0;i<a;i++) { int x,y,z; cin>>x>>y>>z; M.edges[x][y]=z; M.edges[y][x]=z; } cout<<"请输入各个顶点的编号和对应的名字：\n"; for(int i=1;i<=v;i++) { int n; string na; cin>>n>>na; M.vex[i].num=n; M.vex[i].name=na; } } void DFS(MGraph graph,int start) { int visited[MAX_NUM]; //用来标记顶点是否访问过 int tag; int stack[MAX_NUM]; //堆栈 int top=0,temp; int i; memset(visited,0,sizeof(visited)); //将所有顶点设置为未访问过 for(start;start<=graph.vexnum; start++) { if(visited[start]==0) { stack[top++]=start; //先将第一个访问的顶点入栈 visited[start]=1; //将初始点设置为已访问 cout<<start<<" "; //输出初始点 cout<<graph.vex[start].name<<endl; while(top>0) //当堆栈不为空时 { temp=stack[top-1]; tag=0; //标志位初始值设置为0 for(i=1;i<=graph.vexnum;i++) { if((graph.edges[i][temp]<MAX)&&(visited[i]==0)) //小于最大值，并且没有访问过 { stack[top++]=i; //入栈 tag=1; //标志位变为1,表示已经找到弧的另一端点 visited[i]=1; //设置该点为已访问 cout<<i<<" "; cout<<graph.vex[i].name<<endl; break; //退出for循环 } } if(tag==0) top--; } } } for(start; start>0; start--) { if(visited[start]==0) { stack[top++]=start; //先将第一个访问的顶点入栈 visited[start]=1; //将初始点设置为已访问 while(top>0) //当堆栈不为空时 { temp=stack[top-1]; tag=0; //标志位初始值设置为0 for(i=1;i<=graph.vexnum;i++) { if((graph.edges[i][temp]<MAX)&&(visited[i]==0)) //小于最大值，并且没有访问过 { stack[top++]=i; //入栈 tag=1; //标志位变为1,表示已经找到弧的另一端点 visited[i]=1; //设置该点为已访问 cout<<i<<" "; cout<<graph.vex[i].name<<endl; break; //退出for循环 } } if(tag==0) top--; } } } } void PRIM(MGraph G,VertexType u) //从u出发 { int const INF=32767; //无穷大 closedge close; int i,j,k; int min; cout<<u.name<<endl; for(i=1;i<=G.vexnum;i++) // 辅助数组初始化 { close[i].adjvex.num=u.num; close[i].adjvex.name=u.name; close[i].lowcost=G.edges[i][u.num]; } close[u.num].lowcost=0; //把u并入U集合 for(i=1;i<G.vexnum;i++) { min=INF; for(j=1;j<=G.vexnum;j++) { if(close[j].lowcost!=0&&close[j].lowcost<min) //找出权值最小的 { min=close[j].lowcost; k=j; } } cout<<"边("<<close[k].adjvex.num<<","<<k<<") / ("<<close[k].adjvex.name<<","<<G.vex[k].name<<") 权值 "<<min<<endl; close[k].lowcost=0; //第k顶点并入U集 for(j=1;j<=G.vexnum;j++) { if(G.edges[k][j]<close[j].lowcost) { close[j].lowcost=G.edges[k][j]; //用最小权值替代临时数组里面的权值 close[j].adjvex.num=k; //顶点替代 close[j].adjvex.name=G.vex[k].name; } } } } int main() { int const INF=32767; MGraph g; VertexType u; int start; int flag; cout<<"请先输入图是否是连通的，连通输入1，不连通输入0:\n"; cin>>flag; CreatMGraph(g); cout<<"输出无向图的邻接矩阵：\n"; for (int i=1;i<=g.vexnum;i++) { for(int j=1;j<=g.vexnum;j++) { if(g.edges[i][j]==INF) cout<<" "; else cout<<g.edges[i][j]<<" "; } cout<<endl; } cout<<"DFS:\n"; cout<<"请输入遍历的初始点(用顶点编号表示）：\n"; cin>>start; cout<<"遍历结果如下：\n"; DFS(g,start); if(flag==1) { cout<<"请输入用Prim方法建立最小生成树的顶点（格式：1 a）：\n"; cin>>u.num; cin>>u.name; cout<<"最小生成树如下：\n"; PRIM(g,u); } else if(flag==0) cout<<"不存在最小生成树\n"; system("pause"); return 0; }