圖的深度遍歷和廣度遍歷以及最小生成樹(shù).docx

/本程序主要包含以下功能/采用鄰接矩陣構(gòu)造圖/圖的深度遍歷和廣度遍歷/采用普里姆算法和克魯斯卡爾算法構(gòu)造最小生成樹(shù)#include#include #define INFINITY 999#define MAX_VERTEX_NUM 20#define OK 1#define ERROR -1typedef char VertexType;typedef char InfoType;typedef VertexType QElemType;bool visitedMAX_VERTEX_NUM;/ 訪問(wèn)標(biāo)志數(shù)組 typedef struct /*輔助數(shù)組*/ VertexType adjvex; int lowcost;closedgeMAX_VERTEX_NUM;typedef struct int begin;int end;int flag;int weight;edge; edge edges50;typedef struct ArcCellint adj;InfoType *info;ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexType vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum,arcnum; MGraph;typedef struct QNodeQElemType data;struct QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front;QueuePtr rear;LinkQueue;int InitQueue(LinkQueue &Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); if(!Q.front) return ERROR;Q.front-next=NULL;return OK;int DestroyQueue(LinkQueue &Q)while(Q.front)Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;return OK;/DestroyQueueint EnQueue(LinkQueue &Q,QElemType e)QueuePtr p; /p=(QueuePtr)malloc(sizeof(QNode);if(!p) return ERROR;p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;int DeQueue(LinkQueue &Q,QElemType &e)if(Q.front=Q.rear) return ERROR;QueuePtr p;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p) Q.rear=Q.front;free(p);return OK;int QueueEmpty(LinkQueue Q)if(Q.rear=Q.front) return 1;else return 0; int LocateVex(MGraph G,VertexType u)int i;for(i = 0; i =0 & kG.vexnum) /k合理 for(int i=0;i=0 & i=0 & jG.vexnum) /i,j合理 for(int k=j+1;kG.vexnum;k+) if(G.arcsik.adj!=INFINITY) return k; return -1; int CreateUDN(MGraph &G) / 算法 7.2 / 采用數(shù)組（鄰接矩陣）表示法，構(gòu)造無(wú)向網(wǎng)G。 int i,j,k,w,p=0; VertexType v1,v2; printf(G.vexnum : ); scanf(%d,&G.vexnum); printf(G.arcnum :); scanf(%d,&G.arcnum); getchar(); /* 加上此句getchar()! */ / scanf(%d,%d,%d,&G.vexnum, &G.arcnum, &IncInfo); for (i=0; iG.vexnum; i+ ) printf(G.vexs%d : ,i); scanf(%c,&G.vexsi); getchar(); / 構(gòu)造頂點(diǎn)向量 for (i=0; iG.vexnum; +i ) / 初始化鄰接矩陣 for (j=0; jG.vexnum; +j ) G.arcsij.adj = INFINITY; /adj,info G.= NULL; for (k=0; kG.arcnum; +k ) / 構(gòu)造鄰接矩陣 printf(v1 (char) : ); scanf(%c, &v1);getchar(); printf(v2 (char) : ); scanf(%c, &v2);getchar(); printf(w (int) : ); scanf(%d, &w); getchar(); / 輸入一條邊依附的頂點(diǎn)及權(quán)值 i = LocateVex(G, v1); j = LocateVex(G, v2); / 確定v1和v2在G中位置 G.arcsij.adj = w; / 弧的權(quán)值 / if (IncInfo) scanf(G.); / 輸入弧含有相關(guān)信息 G.arcsji.adj = G.arcsij.adj; / 置的對(duì)稱(chēng)弧 edgesp.begin=i; edgesp.end=j; edgesp.weight=G.arcsij.adj; edgesp.flag=0; p+; printf(圖的鄰接矩陣為：n); for ( i = 0; i G.vexnum; i+)for ( j = 0; j G.vexnum; j+) printf(%4d ,G.arcsij.adj); printf(n); return OK; / CreateUDNvoid DFS(MGraph G, int v) / 從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G。 int w; visitedv = true; printf(%c ,G.vexsv);/ 訪問(wèn)第i個(gè)頂點(diǎn) for (w=FirstAdjVex(G, v); w!=-1; w=NextAdjVex(G, v, w) if (!visitedw) / 對(duì)v的尚未訪問(wèn)的鄰接頂點(diǎn)w遞歸調(diào)用DFS DFS(G, w);void DFSTraverse(MGraph G) / 對(duì)圖G作深度優(yōu)先遍歷。 int v; for (v=0; vG.vexnum; +v) visitedv = false; / 訪問(wèn)標(biāo)志數(shù)組初始化 for (v=0; vG.vexnum; +v) if (!visitedv) DFS(G, v); / 對(duì)尚未訪問(wèn)的頂點(diǎn)調(diào)用DFSvoid BFSTraverse(MGraph G ) / 按廣度優(yōu)先非遞歸遍歷圖G。使用輔助隊(duì)列Q和訪問(wèn)標(biāo)志數(shù)組visited。 QElemType v,w; LinkQueue Q; QElemType u; for (v=0; vG.vexnum; +v) visitedv = false; InitQueue(Q); / 置空的輔助隊(duì)列Q for (v=0; v=0; w=NextAdjVex(G, u, w) if (!visitedw) / u的尚未訪問(wèn)的鄰接頂點(diǎn)w入隊(duì)列Q visitedw = true; printf(%c ,G.vexsw); EnQueue(Q, w); /if /while /if / BFSTraverseint minimum(closedge SZ,MGraph G)int i=0,j,k,min;while(!SZi.lowcost)i+;min=SZi.lowcost; / 第一個(gè)不為0的值 k=i;for(j=i+1;j0)if(minSZj.lowcost)min=SZj.lowcost;k=j;return k; /=普里姆算法=void MiniSpanTree_PRIM(MGraph G, VertexType u) / 用普里姆算法從第u個(gè)頂點(diǎn)出發(fā)構(gòu)造網(wǎng)G的最小生成樹(shù)T，輸出T的各條邊。 / 記錄從頂點(diǎn)集U到VU的代價(jià)最小的邊的輔助數(shù)組定義： / struct / VertexType adjvex; / VRType lowcost; / closedgeMAX_VERTEX_NUM;printf(普里姆算法最小生成樹(shù)為：); int i,j,k; closedge closedge; k = LocateVex ( G, u ); for ( j=0; jG.vexnum; +j ) / 輔助數(shù)組初始化 if (j!=k) closedgej.adjvex=u; closedgej.lowcost=G.arcskj.adj; closedgek.lowcost = 0; / 初始，Uu printf(n); for (i=1; i0, viV-U printf( %dn,closedgek.adjvex, G.vexsk,G.arcsLocateVex( G,closedgek.adjvex )k.adj); / 輸出生成樹(shù)的邊 closedgek.lowcost = 0; / 第k頂點(diǎn)并入U(xiǎn)集 for (j=0; jG.vexnum; +j) if (G.arcskj.adj closedgej.lowcost) / 新頂點(diǎn)并入U(xiǎn)后重新選擇最小邊 / closedgej = G.vexsk, G.arcskj.adj ; closedgej.adjvex=G.vexsk; closedgej.lowcost=G.arcskj.adj; / MiniSpanTree/=克魯斯卡爾算=void Swapn(edge *edges,int i, int j) int temp; temp = edgesi.begin; edgesi.begin = edgesj.begin; edgesj.begin = temp; temp = edgesi.end; edgesi.end = edgesj.end; edgesj.end = temp; temp = edgesi.weight; edgesi.weight = edgesj.weight; edgesj.weight = temp; void sort(edge edges,MGraph G)/對(duì)權(quán)值進(jìn)行排序 int i, j;for ( i = 0; i G.arcnum; i+)for ( j = i + 1; j edgesj.weight)Swapn(edges, i, j);printf(按造價(jià)排序之后的邊順序?yàn)?序號(hào) 邊 代價(jià)):n);for (i = 0; i G.arcnum; i+)printf(%d. %dn, i,G.vexsedgesi.begin, G.vexsedgesi.end, edgesi.weight);int Find(int *parent, int f)while ( parentf 0)f = parentf;return f;void MiniSpanTree_KRUSKAL(MGraph G)/生成最小生成樹(shù) int i, j, n, m,Mincost=0; int parent100; sort(edges, G);for (i = 0; i G.arcnum; i+)parenti = 0;printf(克魯斯卡爾算法最小生成樹(shù)為:n);for (i = 0; i G.arcnum; i+) n = Find(parent, edgesi.begin);m = Find(parent, edgesi.end);if (n != m)parentn = m;printf( %dn,G.vexs edgesi.begin,G.vexs edgesi.end, edgesi.weight);Mincost+=edgesi.weight;printf(使各個(gè)頂點(diǎn)連通的最小代價(jià)為：Minc