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)/創(chuàng)建圖用鄰接矩陣表示char v1,v2;int i,j,w;cout創(chuàng)建無向圖endl請輸入圖G頂點(diǎn)和弧的個(gè)數(shù):(4 6)不包括“()”G.vexnumG.arcnum;for(i=0;i!=G.vexnum;+i)cout輸入頂點(diǎn)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輸入一條邊依附的頂點(diǎn)和權(quán):(a b 3)不包括“()”v1v2w;/輸入一條邊依附的兩點(diǎn)及權(quán)值i=localvex(G,v1);/確定頂點(diǎn)V1和V2在圖中的位置j=localvex(G,v2);G.arcsij.adj=w;G.arcsji.adj=w;cout圖G鄰接矩陣創(chuàng)建成功！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鄰接表創(chuàng)建成功！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)/返回依附頂點(diǎn)V的相對于W的下一個(gè)頂點(diǎn)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)/初始化隊(duì)列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)/入隊(duì)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)/出隊(duì)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)/判斷隊(duì)為空if(q.front=q.rear)return 1;return 0;void bfstra(algraph gra)/廣度優(yōu)先遍歷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存儲當(dāng)前集合U分別到剩余結(jié)點(diǎn)的最短路徑/prevex存儲最短路徑在U中的結(jié)點(diǎn)int i,j,k,min; for(i=2;i=n;i+) /n個(gè)頂點(diǎn)，n-1條邊 lowcosti=g1i; /初始化 prevexi=1; /頂點(diǎn)未加入到最小生成樹中 lowcost1=0; /標(biāo)志頂點(diǎn)1加入U(xiǎn)集合 for(i=2;i=n;i+) /形成n-1條邊的生成樹 min=inf; k=0; for(j=2;j=n;j+) /尋找滿足邊的一個(gè)頂點(diǎn)在U,另一個(gè)頂點(diǎn)在V的最小邊 if(lowcostjmin)&(lowcostj!=0) min=lowcostj; k=j; printf(%d,%d)%dt,prevexk-1,k-1,min); lowcostk=0; /頂點(diǎn)k加入U(xiǎn) for(j=2;j=n;j+) /修改由頂點(diǎn)k到其他頂點(diǎn)邊的權(quán)值 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#注意：若該圖為非強(qiáng)連通圖(含有多個(gè)連通分量)時(shí)endl 最小生成樹不存在,則顯示為非法值。endlendl;cout菜單endlendl;cout0、顯示該圖的鄰接矩陣endl;cout1、顯示該圖的鄰接表endl;cout2、深度優(yōu)先遍歷endl;cout3、廣度優(yōu)先遍歷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廣度優(yōu)先遍歷：;bfstra(gra);coutendl;break;case 3:for(i=0;i!=gra.vexnum;+i