图的深度广度遍历和最小生成树PRIM和KRUSCAL算法的实现.doc

图的深度广度遍历和最小生成树PRIM和KRUSCAL算法的实现昨天上实验课，偶然看到这个程序，和大家一起共享一下..... //图的遍历和生成树求解实现//（邻接矩阵、邻接表 —图的深度广度遍历算法的实现和最小生成树PRIM和KRUSCAL算法的实现） #include iostream#include malloc.husing namespace std; #define int_max 10000#define inf 9999 #define max 20//…………………………………………邻接矩阵定义……………………typedef struct ArcCell{int adj;char *info;}ArcCell,AdjMatrix[max][max];typedef struct {char vexs[max];AdjMatrix arcs;int vexnum,arcnum;}MGraph_L;//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^int localvex(MGraph_L G,char v)//返回V的位置{int i=0;while(G.vexs[i]!=v)++i;return i;} int creatMGraph_L(MGraph_L G)//创建图用邻接矩阵表示{char v1,v2;int i,j,w;cout…………创建无向图…………endl请输入图G顶点和弧的个数:(4 6)不包括“()”endl;cinG.vexnumG.arcnum;for(i=0;i!=G.vexnum;++i){cout输入顶点iendl;cinG.vexs[i];}for(i=0;i!=G.vexnum;++i)for(j=0;j!=G.vexnum;++j){ ?? G.arcs[i][j].adj=int_max;?? G.arcs[i][j].info=NULL;}for(int k=0;k!=G.arcnum;++k){ ?? cout输入一条边依附的顶点和权:(a b 3)不包括“()”endl;?? cinv1v2w;//输入一条边依附的两点及权值?? i=localvex(G,v1);//确定顶点V1和V2在图中的位置?? j=localvex(G,v2);?? G.arcs[i][j].adj=w;?? G.arcs[j][i].adj=w;}cout图G邻接矩阵创建成功！endl;return G.vexnum;}void ljjzprint(MGraph_L G) //邻接矩阵的输出 {int i,j;for(i=0;i!=G.vexnum;++i){?? for(j=0;j!=G.vexnum;++j)??? coutG.arcs[i][j].adj ;?? coutendl;}}int visited[max];//访问标记int we;typedef struct arcnode//弧结点{int adjvex;//该弧指向的顶点的位置struct arcnode *nextarc;//弧尾相同的下一条弧char *info;//该弧信息}arcnode;typedef struct vnode//邻接链表顶点头接点{char data;//结点信息arcnode *firstarc;//指向第一条依附该结点的弧的指针}vnode,adjlist;typedef struct//图的定义{adjlist vertices[max];int vexnum,arcnum;int kind;}algraph;//…………………………………………队列定义……………………typedef struct qnode{int data;struct qnode *next;}qnode,*queueptr;typedef struct{queueptr front;queueptr rear;}linkqueue;//………………………………………………………………………typedef struct acr{int pre;//弧的一结点int bak;//弧另一结点int weight;//弧的权}edg; int creatadj(algraph gra,MGraph_L G)//用邻接表存储图{int i=0,j=0;arcnode *arc,*tem,*p;for(i=0;i!=G.vexnum;++i)