AdjMatrix[20][20].doc

#include #include using namespace std; #define int_max 10000#define inf 9999 #define max 20/邻接矩阵定义typedef struct ArcCellint adj;char *info;ArcCell,AdjMatrix2020;typedef struct char vexs20;AdjMatrix arcs;int vexnum,arcnum;MGraph_L;/int localvex(MGraph_L G,char v)/返回V的位置int i=0;while(G.vexsi!=v)+i;return i;int creatMGraph_L(MGraph_L &G)/创建图用邻接矩阵表示char v1,v2;int i,j,w;cout创建无向图endl请输入图G顶点和弧的个数:(4 6)不包括“()”G.vexnumG.arcnum;for(i=0;i!=G.vexnum;+i)cout输入顶点iG.vexsi;for(i=0;i!=G.vexnum;+i)for(j=0;j!=G.vexnum;+j)G.arcsij.adj=int_max;G.=NULL;for(int k=0;k!=G.arcnum;+k)cout输入一条边依附的顶点和权:(a b 3)不包括“()”v1v2w;/输入一条边依附的两点及权值i=localvex(G,v1);/确定顶点V1和V2在图中的位置j=localvex(G,v2);G.arcsij.adj=w;G.arcsji.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.arcsij.adj ;coutadjvex=j;gra.verticesi.firstarc=arc;arc-nextarc=NULL;p=arc;+j;while(G.arcsij.adj!=int_max&j!=G.vexnum)tem=(arcnode *)malloc(sizeof(arcnode);tem-adjvex=j;gra.verticesi.firstarc=tem;tem-nextarc=arc;arc=tem;+j;-j;elseif(G.arcsij.adj!=int_max&j!=G.vexnum)arc=(arcnode *)malloc(sizeof(arcnode);arc-adjvex=j;p-nextarc=arc;arc-nextarc=NULL;p=arc;gra.vexnum=G.vexnum;gra.arcnum=G.arcnum;/*for(i=0;i!=gra.vexnum;+i)arcnode *p;couti ;p=gra.verticesi.firstarc;while(p!=NULL)coutadjvex;p=p-nextarc;coutendl;*/ cout图G邻接表创建成功！endl;return 1;void adjprint(algraph gra)int i;for(i=0;i!=gra.vexnum;+i)arcnode *p;couti ;p=gra.verticesi.firstarc;while(p!=NULL)coutadjvex;p=p-nextarc;coutadjvex;int nextadjvex(algraph gra,vnode v,int w)/返回依附顶点V的相对于W的下一个顶点arcnode *p;p=v.firstarc;while(p!=NULL&p-adjvex!=w)p=p-nextarc;if(p-adjvex=w&p-nextarc!=NULL)p=p-nextarc;return p-adjvex;if(p-adjvex=w&p-nextarc=NULL)return -10;int initqueue(linkqueue &q)/初始化队列q.rear=(queueptr)malloc(sizeof(qnode);q.front=q.rear;if(!q.front)return 0;q.front-next=NULL;return 1;int enqueue(linkqueue &q,int e)/入队queueptr p;p=(queueptr)malloc(sizeof(qnode);if(!p)return 0;p-data=e;p-next=NULL;q.rear-next=p;q.rear=p;return 1;int dequeue(linkqueue &q,int &e)/出队queueptr p;if(q.front=q.rear)return 0;p=q.front-next;e=p-data;q.front-next=p-next;if(q.rear=p)q.rear=q.front;free(p);return 1;int queueempty(linkqueue q)/判断队为空if(q.front=q.rear)return 1;return 0;void bfstra(algraph gra)/广度优先遍历int i,e;linkqueue q;for(i=0;i!=gra.vexnum;+i)visitedi=0;initqueue(q);for(i=0;i!=gra.vexnum;+i)if(!visitedi)visitedi=1;coutgra.verticesi.data;enqueue(q,i);while(!queueempty(q)dequeue(q,e);/cout e=0;we=nextadjvex(gra,gra.verticese,we)if(!visitedwe)visitedwe=1;coutgra.verticeswe.data;enqueue(q,we);int dfs(algraph gra,int i);/声明DFSint dfstra(algraph gra)int i,j;for(i=0;i!=gra.vexnum;+i)visitedi=0;for(j=0;j!=gra.vexnum;+j)if(visitedj=0)dfs(gra,j);return 0;int dfs(algraph gra,int i)visitedi=1;int we1;/coutivisitediendl;coutgra.verticesi.data;/cout=0;we=nextadjvex(gra,gra.verticesi,we)/coutwevisitedweendl;we1=we;/coutnextadjvex(gra,gra.verticesi,we)endl;if(visitedwe=0)/coutdfs(gra,we);/endl;/coutiwe1endl;we=we1;/coutnextadjvex(gra,gra.verticesi,we)endl;return 12;int bfstra_fen(algraph gra)/求连通分量int i,j;for(i=0;i!=gra.vexnum;+i)visitedi=0;for(j=0;j!=gra.vexnum;+j)if(visitedj=0)dfs(gra,j);coutendl;return 0;typedef struct int adjvex;int lowcost;closedge;/*int minimum(closedge *p);int minispantree(MGraph_L G,char u)int k,j,i;closedge closedge_a20;k=localvex(G,u);/coutkendl;for(j=0;j!=G.vexnum;+j)if(j!=k)closedge_aj.adjvex=u;closedge_aj.lowcost=G.arcskj.adj;for(i=1;i!=G.vexnum;+i)k=minimum(closedge_a);coutk;coutclosedge_ak.adjvex G.vexskendl;closedge_ak.lowcost=0;for(j=0;j!=G.vexnum;+j)if(G.arcskj.adjp-lowcost)s=p-lowcost;return s;*/int prim(int gmax,int n) /最小生成树PRIM算法int lowcostmax,prevexmax; /LOWCOST存储当前集合U分别到剩余结点的最短路径/prevex存储最短路径在U中的结点int i,j,k,min; for(i=2;i=n;i+) /n个顶点，n-1条边 lowcosti=g1i; /初始化 prevexi=1; /顶点未加入到最小生成树中 lowcost1=0; /标志顶点1加入U集合 for(i=2;i=n;i+) /形成n-1条边的生成树 min=inf; k=0; for(j=2;j=n;j+) /寻找满足边的一个顶点在U,另一个顶点在V的最小边 if(lowcostjmin)&(lowcostj!=0) min=lowcostj; k=j; printf(%d,%d)%dt,prevexk-1,k-1,min); lowcostk=0; /顶点k加入U for(j=2;j=n;j+) /修改由顶点k到其他顶点边的权值 if(gkj0)f=acrvisitedf;return f;void kruscal_arc(MGraph_L G,algraph gra)edg edgs20;int i,j,k=0;for(i=0;i!=G.vexnum;+i)for(j=i;j!=G.vexnum;+j)if(G.arcsij.adj!=10000)edgsk.pre=i;edgsk.bak=j;edgsk.weight=G.arcsij.adj;+k;int x,y,m,n;int buf,edf;for(i=0;i!=gra.arcnum;+i)acrvisitedi=0;for(j=0;j!=G.arcnum;+j)m=10000;for(i=0;i!=G.arcnum;+i)if(edgsi.weightm)m=edgsi.weight;x=edgsi.pre;y=edgsi.bak;n=i;/coutxym;/coutendl;buf=find(acrvisited,x);edf=find(acrvisited,y);/coutbuf edfendl;edgsn.weight=10000;if(buf!=edf)acrvisitedbuf=edf;cout(x,y)m;coutendl;void main()algraph gra;MGraph_L G;int i,d,g2020;char a=a;d=creatMGraph_L(G);creatadj(gra,G);vnode v;coutendl#注意：若该图为非强连通图(含有多个连通分量)时endl 最小生成树不存在,则显示为非法值。endlendl;cout菜单endlendl;cout0、显示该图的邻接矩阵endl;cout1、显示该图的邻接表endl;cout2、深度优先遍历endl;cout3、广度优先遍历endl;cout4、最小生成树PRIM算法endl;cout5、最小生成树KRUSCAL算法endl;cout6、该图的连通分量endlendl;int s;char y=y;while(y=y)cout请选择菜单：s;switch(s)case 0:cout邻接矩阵显示如下：endl;ljjzprint(G);break;case 1:cout邻接表显示如下：endl;adjprint(gra);break;case 2:cout广度优先遍历：;bfstra(gra);coutendl;break;case 3:for(i=0;i!=gra.vexnum;+i