2020年112020年1110日一、實(shí)驗(yàn)?zāi)康募耙笫煜じ鞣N圖的存儲(chǔ)結(jié)構(gòu)。掌握圖的各種搜索路徑的遍歷方法。二、實(shí)驗(yàn)內(nèi)容（或?qū)嶒?yàn)原理、實(shí)驗(yàn)拓?fù)洌?.任選一種存儲(chǔ)結(jié)構(gòu)（鄰接表為主），完成圖的DFS（深度優(yōu)先遍歷）和BFS（廣度優(yōu)先遍歷）的操作（8.18.2）2．練習(xí)如何構(gòu)造最小生成樹（8.58.6）3.練習(xí)如何尋找并求得關(guān)鍵路徑并調(diào)試出例8.15的拓?fù)渑判颉W(xué)生姓名學(xué)號(hào)實(shí)驗(yàn)成績專業(yè)19計(jì)科班級(jí)2班實(shí)驗(yàn)日期課程名稱數(shù)據(jù)結(jié)構(gòu)與算法任課教師實(shí)驗(yàn)名稱圖的操作算法實(shí)驗(yàn)序號(hào)實(shí)驗(yàn)地點(diǎn)S510實(shí)驗(yàn)臺(tái)號(hào)指導(dǎo)教師三、實(shí)驗(yàn)設(shè)備與環(huán)境三、實(shí)驗(yàn)設(shè)備與環(huán)境WindowsDEV-C++四、實(shí)驗(yàn)設(shè)計(jì)方案（包括實(shí)驗(yàn)步驟、設(shè)計(jì)思想、算法描述或開發(fā)流程等）8.1設(shè)計(jì)思路CreateMat(&g):創(chuàng)建圖，由相關(guān)數(shù)據(jù)構(gòu)造一個(gè)圖gDispMat(g):輸出圖，顯示圖g的頂點(diǎn)和邊信息。DestroyGraph(&g):銷毀圖，釋放圖g占用的內(nèi)存空間。創(chuàng)建圖的鄰接矩陣voidCreateMat(MatGraph&g,intA[MAXV][MAXV],intn,inte)//創(chuàng)建圖的鄰接矩陣{inti,j;g.n=n;g.e=e;for(i=0;i<g.n;i++)for(j=0;j<g.n;g.edges[i][j]=A[i][j];}輸出鄰接矩陣voidDispMat(MatGraphg){inti,j;for(i=0;i<g.n;i++){for(j=0;j<g.n;j++){if(g.edges[i][j]!=INF)printf("%4d",g.edges[i][j]);elseprintf("%4s","∞");}printf("\n");}}鄰接表創(chuàng)建圖的鄰接表voidCreateAdj(AdjGraph*&G,intA[MAXV][MAXV],intn,inte)//創(chuàng)建圖的鄰接表{inti,j;ArcNode*p;G=(AdjGraph*)malloc(sizeof(AdjGraph));for(i=0;i<n;i++) 給鄰接表中所有頭結(jié)點(diǎn)的指針域置初值NULL{G->adjlist[i].firstarc=NULL;}for(i=0;i<n;i++) 檢查鄰接矩陣中的每個(gè)元素{for(j=n-1;j>=0;j--){if(A[i][j]!=0&&A[i][j]!=INF)//存在一條邊{p=(ArcNode*)malloc(sizeof(ArcNode));創(chuàng)建一個(gè)結(jié)點(diǎn)p->adjvex=j; //鄰接點(diǎn)編號(hào)p->weight=A[i][j]; //邊的權(quán)重p->nextarc=G->adjlist[i].firstarc; //采用頭插法插入結(jié)點(diǎn)G->adjlist[i].firstarc=p;}}}G->n=n;G->e=e;}輸出鄰接表voidDispAdj(AdjGraph*G){ArcNode*p;for(inti=0;i<G->n;{p=G->adjlist[i].firstarc;printf("頂點(diǎn)%d:",i);while(p!=NULL){printf("%3d[%d]->",p->adjvex,p->weight); //鄰接點(diǎn)編號(hào)[p=p->nextarc;}printf("∧\n");}}銷毀圖的鄰接表voidDestroyAdj(AdjGraph*&G){ArcNode*pre,*p;for(inti=0;i<G->n;i++){pre=G->adjlist[i].firstarc; //preiif(pre!=NULL){p=pre->nextarc;while(p!=NULL)//釋放第i個(gè)單鏈表的所有邊結(jié)點(diǎn){free(pre);pre=p;p=p->nextarc;}free(pre);}}free(G); //釋放頭結(jié)點(diǎn)數(shù)組}8.2DFS(g,v):從頂點(diǎn)v出發(fā)深度優(yōu)先遍歷圖g.BFS(g,v):從頂點(diǎn)v出發(fā)廣度優(yōu)先遍歷圖g.//遞歸深度優(yōu)先遍歷voidDFS(ALGraph*G,intv){ArcNode*p;visited[v]=1;printf("%3d",v);p=G->adjlist[v].firstarc;//指向v的第一個(gè)鄰接點(diǎn)while(p)//查找v的所有臨界點(diǎn){if(visited[p->adjvex]==0)//若當(dāng)前鄰接點(diǎn)未被訪問DFS(G,p->adjvex);//p=p->nextarc;//}}//非遞歸深度優(yōu)先遍歷voidDFS1(ALGraph*G,intv){ArcNode*p;ArcNode*St[MAXV];inttop=-1,i,w;for(i=0;i<G->n;i++)visited[i]=0;//恢復(fù)環(huán)境，使該頂點(diǎn)可重復(fù)使用printf("%3d",v);visited[v]=1;top++;St[top]=G->adjlist[v].firstarc;while(top>-1){p=St[top];top--;while(p){w=p->adjvex;if(visited[w]==0)//若w未被訪問,則遞歸訪問之{printf("%3d",w);visited[w]=1;top++;St[top]=G->adjlist[w].firstarc;break;}p=p->nextarc;//找u的下一個(gè)鄰接點(diǎn)}}printf("\n");}voidBFS(ALGraph*G,intv){ArcNode*p;//定義指針intqueue[MAXV],front=0,rear=0;//定義頂點(diǎn)訪問標(biāo)記數(shù)組intw,i;for(i=0;i<G->n;i++)//訪問標(biāo)記數(shù)組初始化visited[i]=0;printf("%3d",v);//輸出被訪問頂點(diǎn)編號(hào)visited[v]=1;//置已訪問標(biāo)記rear=(rear+1)%MAXV;queue[rear]=v;while(front!=rear){front=(front+1)%MAXV;w=queue[front];p=G->adjlist[w].firstarc;while(p){if(visited[p->adjvex]==0)//若當(dāng)前鄰接點(diǎn)未被訪問{printf("%3d",p->adjvex);//訪問該鄰接點(diǎn)visited[p->adjvex]=1;//置已訪問標(biāo)記rear=(rear+1)%MAXV;queue[rear]=p->adjvex;//該頂點(diǎn)進(jìn)棧}p=p->nextarc;//找下一個(gè)鄰接點(diǎn)}}printf("\n");}8.5鄰接矩陣的基本運(yùn)算算法 */創(chuàng)建圖的鄰接矩陣voidCreateMat(MatGraph&g,intA[MAXV][MAXV],intn,inte){inti,j;g.n=n;g.e=e;for(i=0;i<g.n;i++)for(j=0;j<g.n;g.edges[i][j]=A[i][j];}鄰接表的基本運(yùn)算算法創(chuàng)建圖的鄰接表G-voidCreateAdj(AdjGraph*&G,intA[MAXV][MAXV],intn,inte){inti,j;ArcNode*p;G=(AdjGraph*)malloc(sizeof(AdjGraph));for(i=0;i<n;i++)//給鄰接表中所有頭結(jié)點(diǎn)的指針域置初值NULL{G->adjlist[i].firstarc=NULL;}for(i=0;i<n;i++)//檢查鄰接矩陣中的每個(gè)元素{for(j=n-1;j>=0;j--){if(A[i][j]!=0&&A[i][j]!=INF)//存在一條邊{p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;鄰接點(diǎn)編號(hào)p->weight=A[i][j];//邊的權(quán)重p->nextarc=G->adjlist[i].firstarc; //采用頭插法插入結(jié)點(diǎn)G->adjlist[i].firstarc=p;}}}}8.6

G->n=n;G->e=e;鄰接矩陣的基本運(yùn)算算法創(chuàng)建圖的鄰接矩陣voidCreateMat(MatGraph&g,intA[MAXV][MAXV],intn,inte){inti,j;g.n=n;g.e=e;for(i=0;i<g.n;i++)for(j=0;j<g.n;g.edges[i][j]=A[i][j];}/*------------輸出鄰接矩陣g */voidDispMat(MatGraphg){inti,j;for(i=0;i<g.n;i++){for(j=0;j<g.n;j++){if(g.edges[i][j]!=INF)printf("%4d",g.edges[i][j]);else}

printf("%4s","∞");printf("\n");}}鄰接表的基本運(yùn)算算法創(chuàng)建圖的鄰接表voidCreateAdj(AdjGraph*&G,intA[MAXV][MAXV],intn,inte){inti,j;ArcNode*p;G=(AdjGraph*)malloc(sizeof(AdjGraph));for(i=0;i<n;i++) 給鄰接表中所有頭結(jié)點(diǎn)的指針域置初值NULL{G->adjlist[i].firstarc=NULL;}for(i=0;i<n;i++) 檢查鄰接矩陣中的每個(gè)元素{for(j=n-1;j>=0;j--){if(A[i][j]!=0&&A[i][j]!=INF)//存在一條邊{p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;鄰接點(diǎn)編號(hào)p->weight=A[i][j];//邊的權(quán)重p->nextarc=G->adjlist[i].firstarc;G->adjlist[i].firstarc=p;}}}G->n=n;G->e=e;}-輸出鄰接表GvoidDispAdj(AdjGraph*G){ArcNode*p;for(inti=0;i<G->n;i++){p=G->adjlist[i].firstarc;printf("%d:",i);while(p!=NULL){printf("%3d[%d]->",p->adjvex,p->weight); //[p=p->nextarc;}printf("∧\n");}}銷毀圖的鄰接表voidDestroyAdj(AdjGraph*&G){ArcNode*pre,*p;for(inti=0;i<G->n;i++){pre=G->adjlist[i].firstarc;//pre指向第i個(gè)單鏈表的首結(jié)點(diǎn)if(pre!=NULL){p=pre->nextarc;while(p!=NULL)//釋放第i個(gè)單鏈表的所有邊結(jié)點(diǎn){free(pre);pre=p;p=p->nextarc;}free(pre);}}free(G); //釋放頭結(jié)點(diǎn)數(shù)組}功能:采用克魯斯卡爾算法輸出圖g的一棵最小生成樹(n個(gè)頂點(diǎn)，n-1條邊)voidKruskal(MatGraphg){intu1,v1;intsn1,sn2;inti,j;intk;EdgeE[MAX_SIZE];intvset[MAXV];k=0; //E0printf("g:\n");for(i=0;i<g.n;i++)//由g產(chǎn)生的邊集E{for(j=0;j<=i;j++){if(g.edges[i][j]!=0&&g.edges[i][j]!=INF){E[k].u=i;E[k].v=j;E[k].w=g.edges[i][j];k++;printf(" 邊(%d,%d)=%d\n",i,j,g.edges[i][j]);}}}insert_sort(E,采用直接插入排序方法對E[0...n-1]wprintf("g邊集合按權(quán)值w:\n");for(i=0;i<g.e;i++){printf(" 邊(%d,%d)=%d\n",E[i].u,E[i].v,E[i].w);}printf("圖全部頂點(diǎn)集合vset={");for(i=0;i<g.n;i++)//初始化輔助數(shù)組{vset[i]=i;printf("%d",vset[i]);}printf("}\n");k=1;//k表示當(dāng)前構(gòu)造生成樹的第幾條邊,初值為1j=0;//E中邊的下標(biāo),初值為0while(k<g.n)//生成的邊數(shù)小于頂點(diǎn)個(gè)數(shù)n時(shí)循環(huán){u1=E[j].u;//取一條邊的起始頂點(diǎn)和終止頂點(diǎn)v1=E[j].v;sn1=vset[u1];sn2=vset[v1];//分別得到兩個(gè)頂點(diǎn)所屬的集合編號(hào)printf(" 起始頂點(diǎn)u1=%d所屬集合編號(hào)sn1=%d,終止頂點(diǎn)v1=%dsn2=%d\n",u1,sn1,v1,sn2);if(sn1!=sn2){printf(" 圖g最小生成樹的(%d,%d)=%d\n",u1,v1,E[j].w);k++; //生成邊數(shù)增1for(i=0;i<g.n;i++)//兩個(gè)集合統(tǒng)一編號(hào){if(vset[i]==sn2) //集合編號(hào)為sn2的改為sn1{vset[i]=sn1;}}}j++; //掃描下一條邊}}8.15*------------------采用鄰接矩陣存儲(chǔ)的圖g中從頂點(diǎn)v出發(fā)進(jìn)行深度優(yōu)先遍歷 */staticvoidMDFS(MatGraphg,intv){intw;visited[v]=1; //置訪問標(biāo)記for(w=0;w<g.n;w++)//找頂點(diǎn)v的所有鄰接點(diǎn){if((g.edges[v][w]!=0)&&(g.edges[v][w]!=INF)&&(visited[w]==0)){MDFS(g,w);//找頂點(diǎn)v的未訪問過的鄰接點(diǎn)w}}}/*-----------------判定圖g的連通性 */staticboolconnect(MatGraphg){boolflag=true;intk;for(k=0;k<g.n;k++){visited[k]=0;}MDFS(g,0);for(k=0;k<g.n;k++){if(visited[k]==0){flag=false;}}returnflag;}/*------------------求圖g的最小生成樹 */staticvoidspantree(MatGraph&g){inti,j,k=0,e;Edgetemp;Edgeedges[MAXE];for(i=0;i<g.n;i++) //獲取圖中所有邊信息{for(j=0;j<i;j++){if((g.edges[i][j]!=0)&&(g.edges[i][j]!=INF)){edges[k].u=i;edges[k].v=j;edges[k].w=g.edges[i][j];k++;}}}for(i=1;i<g.e;i++) //edges數(shù)組按w遞減排序{if(edges[i].w>edges[i-1].w){temp=edges[i];j=i-1;do{edges[j+1]=edges[j];j--;}while((j>=0)&&(edges[j].w<temp.w));edges[j+1]=temp;}}k=0;e=g.e;while(e>={g.edges[edges[k].u][edges[k].v]=INF;//k條邊g.edges[edges[k].v][edges[k].u]=INF;if(connect(g))//若連通，則刪除{e--;printf(" (%d)刪除邊(%d,%d):%d\n",g.e-e,edges[k].u,edges[k].v,edges[k].w);}else //若不連通，則恢復(fù)第k條邊{}k++;}

g.edges[edges[k].u][edges[k].v]=edges[k].w;g.edges[edges[k].v][edges[k].u]=edges[k].w;g.e-=e;//修改圖中的邊數(shù)}五、實(shí)驗(yàn)結(jié)果（包括設(shè)計(jì)效果、測試數(shù)據(jù)、運(yùn)行結(jié)果等）8.18.28.58.68.15六、實(shí)驗(yàn)小結(jié)（包括收獲、心得體會(huì)、注意事項(xiàng)、存在問題及解決辦法、建議等）通過這節(jié)課的學(xué)習(xí)，我獲得了很多知識(shí)，有很大的收獲。老師也講的很仔細(xì)，熟悉了各種圖的存儲(chǔ)結(jié)構(gòu)，并且也掌握圖的各種搜索路徑的遍歷方法。領(lǐng)會(huì)了圖的兩種存儲(chǔ)結(jié)構(gòu)，兩種遍歷方法以及深度優(yōu)先遍歷和廣度優(yōu)先遍歷，但是還有一些細(xì)節(jié)掌握的還不是太好，還應(yīng)該多加練習(xí)，，尤其是在一些算法的實(shí)現(xiàn)時(shí)，具體的思想還是了解了。七、附錄（包括作品、流程圖、源程序及命令清單等）8.1#include<stdio.h>#include<malloc.h>#defineINF 32767 //∞#defineMAXV 100 //最大頂點(diǎn)個(gè)數(shù)typedefcharInfoType;/*-------------------------以下定義鄰接矩陣類型 */typedefstruct{intno; //頂點(diǎn)編號(hào)InfoTypeinfo; //頂點(diǎn)信息}VertexType; //頂點(diǎn)類型typedefstruct{intedges[MAXV][MAXV]; //(間關(guān)系))intn; //頂點(diǎn)數(shù)inte; //邊數(shù)vexs[MAXV]; //存放頂點(diǎn)信息()}MatGraph; //完整的圖鄰接矩陣類型//鄰接表表示法-將每個(gè)頂點(diǎn)的鄰接點(diǎn)串成一個(gè)單鏈表/*-----------以下定義鄰接表類型 */typedefstructArcNode{intadjvex; //該邊的鄰接點(diǎn)編號(hào)structArcNode*nextarc; //指向下一條邊的指intweight; //()}ArcNode; //邊結(jié)點(diǎn)類型typedefstructVNode{InfoTypeinfo; //頂點(diǎn)其他信息intcnt; //,僅用于拓?fù)渑判駻rcNode*firstarc; //指向第一條邊}VNode; //鄰接表結(jié)點(diǎn)類型typedefstruct{VNodeadjlist[MAXV]; //鄰接表頭結(jié)點(diǎn)數(shù)組intn; //圖中頂點(diǎn)數(shù)inte; //圖中邊數(shù)}AdjGraph; //完整的圖鄰接表類型/*-------------------------鄰接矩陣的基本運(yùn)算算法 *//*------------由邊數(shù)組A、頂點(diǎn)數(shù)n和邊數(shù)e創(chuàng)建圖的鄰接矩陣g */voidCreateMat(MatGraph&g,intA[MAXV][MAXV],intn,inte){inti,j;g.n=n;g.e=e;for(i=0;i<g.n;i++)for(j=0;j<g.n;g.edges[i][j]=A[i][j];}/*------------輸出鄰接矩陣g */voidDispMat(MatGraphg){inti,j;for(i=0;i<g.n;i++){for(j=0;j<g.n;j++){if(g.edges[i][j]!=INF)printf("%4d",g.edges[i][j]);elseprintf("%4s","∞");}printf("\n");}}/*-------------------------鄰接表的基本運(yùn)算算法 *//*-------------------由邊數(shù)組A、頂點(diǎn)數(shù)n和邊數(shù)e創(chuàng)建圖的鄰接表G */voidCreateAdj(AdjGraph*&G,intA[MAXV][MAXV],intn,inte){inti,j;ArcNode*p;G=(AdjGraph*)malloc(sizeof(AdjGraph));for(i=0;i<n;i++) //的指針域置初值NULL{G->adjlist[i].firstarc=NULL;}for(i=0;i<n;i++) //元素{for(j=n-1;j>=0;j--){if(A[i][j]!=0&&A[i][j]!=INF) //存在一條邊{p=(ArcNode*)malloc(sizeof(ArcNode));創(chuàng)建一個(gè)結(jié)點(diǎn)p->adjvex=j; //鄰接點(diǎn)編號(hào)p->weight=A[i][j]; //邊的權(quán)重p->nextarc=G->adjlist[i].firstarc; //采用頭插法插入結(jié)點(diǎn)G->adjlist[i].firstarc=p;}}}G->n=n;G->e=e;}/*-------------------輸出鄰接表G */voidDispAdj(AdjGraph*G){ArcNode*p;for(inti=0;i<G->n;i++){p=G->adjlist[i].firstarc;printf("頂點(diǎn)%d:",i);while(p!=NULL){printf("%3d[%d]->",p->adjvex,p->weight); //[p=p->nextarc;}printf("∧\n");}}/*-------------------銷毀圖的鄰接表G */voidDestroyAdj(AdjGraph*&G){ArcNode*pre,*p;for(inti=0;i<G->n;i++){pre=G->adjlist[i].firstarc; //pre指向第i個(gè)單鏈表的首結(jié)點(diǎn)if(pre!=NULL){p=pre->nextarc;while(p!=NULL) //i的所有邊結(jié)點(diǎn){free(pre);pre=p;p=p->nextarc;}free(pre);}}free(G); //釋放頭結(jié)點(diǎn)數(shù)組}intmain(void){MatGraphg;AdjGraph*G;intn=6; 圖中的頂點(diǎn)數(shù)inte=10; //圖中的邊數(shù)intA[MAXV][MAXV]={{0,5,INF,7,INF,INF},{INF,0,4,INF,INF,INF},{8,INF,0,INF,INF,9},{INF,INF,5,0,INF,6},{INF,INF,INF,5,0,INF},{3,INF,INF,INF,1,0}};CreateMat(g,A,n,e);printf("(1)圖的鄰接矩陣:\n");DispMat(g);CreateAdj(G,A,n,e);printf("(2)圖的鄰接表:\n");DispAdj(G);printf("(3)銷毀圖的鄰接表\n");DestroyAdj(G);return0;}8.2#include<stdio.h>#include<malloc.h>#defineMAXV//以下定義鄰接矩陣類型typedefstruct{intno; //頂點(diǎn)編號(hào)intinfo; //頂點(diǎn)其余的信息}VertexType;typedefstruct{intedges[MAXV][MAXV]; //鄰接矩陣intn,e; //頂點(diǎn)數(shù)，弧數(shù)VertexTypevexs[MAXV]; //存放頂點(diǎn)信}MGraph;//一下定義鄰接表類型typedefstructANode //弧的節(jié)點(diǎn)結(jié)構(gòu)類型{intadjvex; //structANode*nextarc;intinfo; //弧的相關(guān)信息}ArcNode;typedefstructVnode //鄰接表頭結(jié)點(diǎn)類型{intdata; //頂點(diǎn)信息ArcNode*firstarc; //指向第一條}VNode;typedefVNode typedefstruct{AdjListadjlist;intn,e;}ALGraph;intvisited[MAXV];//遞歸深度優(yōu)先遍歷voidDFS(ALGraph*G,intv){ArcNode*p;visited[v]=1;printf("%3d",v);p=G->adjlist[v].firstarc;while(p){if(visited[p->adjvex]==0)DFS(G,p->adjvex);p=p->nextarc;}}voidDFS1(ALGraph*G,intv){ArcNode*p;ArcNode*St[MAXV];inttop=-1,i,w;for(i=0;i<G->n;i++)visited[i]=0;printf("%3d",v);visited[v]=1;top++;St[top]=G->adjlist[v].firstarc;while(top>-1){p=St[top];top--;while(p){w=p->adjvex;if(visited[w]==0){printf("%3d",w);visited[w]=1;top++;St[top]=G->adjlist[w].firstarc;break;}p=p->nextarc;}}printf("\n");}voidBFS(ALGraph*G,intv){ArcNode*p;intqueue[MAXV],front=0,rear=0;intw,i;for(i=0;i<G->n;i++)visited[i]=0;printf("%3d",v);visited[v]=1;rear=(rear+1)%MAXV;queue[rear]=v;while(front!=rear){front=(front+1)%MAXV;w=queue[front];p=G->adjlist[w].firstarc;while(p){if(visited[p->adjvex]==0){printf("%3d",p->adjvex);visited[p->adjvex]=1;rear=(rear+1)%MAXV;queue[rear]=p->adjvex;}p=p->nextarc;}}printf("\n");}voidDispAdj(ALGraph*G) //輸出鄰接表{inti;ArcNode*p;for(i=0;i<G->n;i++){p=G->adjlist[i].firstarc;if(p)printf("%3d:",i);while(p){printf("%3d->",p->adjvex);p=p->nextarc;}printf("\n");}}voidMatToList(MGraphg,ALGraph*&G) //將鄰接矩陣gG{inti,j,n=g.n;ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;i<n;i++)G->adjlist[i].firstarc=NULL;for(i=0;i<n;i++)for(j=n-1;j>=0;j--)if(g.edges[i][j]){p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->info=g.edges[i][j];p->nextarc=G->adjlist[i].firstarc;G->adjlist[i].firstarc=p;}G->n=n;G->e=g.e;}intmain(){inti,j;MGraphg;ALGraph*G;intA[MAXV][6]={{0,5,0,7,0,0},{0,0,4,0,0,0},{8,0,0,0,0,9},{0,0,5,0,0,6},{0,0,0,5,0,0},{3,0,0,0,1,0}};g.n=6;g.e=10;for(i=0;i<g.n;i++)for(j=0;j<g.n;j++)g.edges[i][j]=A[i][j];G=(ALGraph*)malloc(sizeof(ALGraph));MatToList(g,G);printf("從頂點(diǎn)0開始的DFS（遞歸算法）：\n");printf("\n");printf("從頂點(diǎn)0開始的DFS（非遞歸算法printf("\n");printf("從頂點(diǎn)0開始的BFS（遞歸算法printf("\n");}8.5#include<stdio.h>#include<malloc.h>#defineINF 32767 //∞#defineMAXV 100 //最大頂點(diǎn)個(gè)數(shù)typedefcharInfoType;/*-------------------------以下定義鄰接矩陣類型 */typedefstruct{intno; //頂點(diǎn)編號(hào)InfoTypeinfo; //頂點(diǎn)信息}VertexType; //頂點(diǎn)類型typedefstruct{intedges[MAXV][MAXV]; //鄰接矩陣數(shù)組(用一個(gè)二維數(shù)組存放頂點(diǎn)間關(guān)系(邊或弧)的數(shù)據(jù))intn; //頂點(diǎn)數(shù)inte; //邊數(shù)vexs[MAXV]; //存放頂點(diǎn)信息(用一個(gè)一維數(shù)組存放圖中所有頂點(diǎn)數(shù)據(jù))}MatGraph; //完整的圖鄰接矩陣類型//鄰接表表示法-將每個(gè)頂點(diǎn)的鄰接點(diǎn)串成一個(gè)單鏈表/*-----------以下定義鄰接表類型 */typedefstructArcNode{intadjvex; //該邊的鄰接點(diǎn)編號(hào)structArcNode*nextarc; //指向下一條邊的指intweight; //()}ArcNode; //邊結(jié)點(diǎn)類型typedefstructVNode{InfoTypeinfo; //頂點(diǎn)其他信息intcnt; //,僅用于拓?fù)渑判駻rcNode*firstarc; //指向第一條邊}VNode; //鄰接表結(jié)點(diǎn)類型typedefstruct{VNodeadjlist[MAXV]; //鄰接表頭結(jié)點(diǎn)數(shù)組intn; //圖中頂點(diǎn)數(shù)inte; //圖中邊數(shù)}AdjGraph; //完整的圖鄰接表類型/*-------------------------鄰接矩陣的基本運(yùn)算算法 *//*------------由邊數(shù)組A、頂點(diǎn)數(shù)n和邊數(shù)e創(chuàng)建圖的鄰接矩陣g */voidCreateMat(MatGraph&g,intA[MAXV][MAXV],intn,inte){inti,j;g.n=n;g.e=e;for(i=0;i<g.n;i++)for(j=0;j<g.n;g.edges[i][j]=A[i][j];}/*------------輸出鄰接矩陣g */voidDispMat(MatGraphg){inti,j;for(i=0;i<g.n;i++){for(j=0;j<g.n;j++){if(g.edges[i][j]!=INF)printf("%4d",g.edges[i][j]);elseprintf("%4s","∞");}printf("\n");}}/*-------------------------鄰接表的基本運(yùn)算算法 *//*-------------------由邊數(shù)組A、頂點(diǎn)數(shù)n和邊數(shù)e創(chuàng)建圖的鄰接表G */voidCreateAdj(AdjGraph*&G,intA[MAXV][MAXV],intn,inte){inti,j;ArcNode*p;G=(AdjGraph*)malloc(sizeof(AdjGraph));for(i=0;i<n;i++) //初值NULL{G->adjlist[i].firstarc=NULL;}for(i=0;i<n;i++) //檢查鄰接矩陣中的每個(gè)元素{for(j=n-1;j>=0;j--){if(A[i][j]!=0&&A[i][j]!=INF) //存在一條邊{p=(ArcNode*)malloc(sizeof(ArcNode));創(chuàng)建一個(gè)結(jié)點(diǎn)p->adjvex=j; //鄰接點(diǎn)編號(hào)p->weight=A[i][j]; //邊的權(quán)重p->nextarc=G->adjlist[i].firstarc; //采用頭插法插入結(jié)點(diǎn)G->adjlist[i].firstarc=p;}}}G->n=n;G->e=e;}/*-------------------輸出鄰接表G */voidDispAdj(AdjGraph*G){ArcNode*p;for(inti=0;i<G->n;i++){p=G->adjlist[i].firstarc;printf("%d:",i);while(p!=NULL){printf("%3d[%d]->",p->adjvex,p->weight); //[p=p->nextarc;}printf("∧\n");}}/*-------------------銷毀圖的鄰接表G */voidDestroyAdj(AdjGraph*&G){ArcNode*pre,*p;for(inti=0;i<G->n;i++){pre=G->adjlist[i].firstarc; //pre指向第iif(pre!=NULL){p=pre->nextarc;while(p!=NULL) //i個(gè)單鏈表的所有邊結(jié)點(diǎn){free(pre);pre=p;p=p->nextarc;}free(pre);}}free(G); //釋放頭結(jié)點(diǎn)數(shù)組}/*--------------采用普里姆算法輸出圖g中從頂點(diǎn)v出發(fā)的一棵最小生成樹 *//**功能:采用普里姆算法輸出圖g中從頂點(diǎn)v(n個(gè)頂點(diǎn)，n-1條邊)備注:全部頂點(diǎn)的集合U:已被挑選出來的集合*/voidPrim(MatGraphg,intv){intlowcost[MAXV];intmin_weight;intclosest[MAXV];inti,j;intk;for(i=0;i<g.n;i++) //lowcost[]closest[]的初值{lowcost[i]=g.edges[v][i];closest[i]=v;}for(i=1;i<g.n;i++) //找出n-1個(gè)頂點(diǎn){min_weight=INF;for(j=0;j<g.n;j++) //在U最近的頂點(diǎn)k{if(lowcost[j]!=0&&lowcost[j]<min_weight){min_weight=lowcost[j];k=j;}}printf(" 邊(%d,%d):%d\n",closest[k],k,min_weight);lowcost[k]=0; //標(biāo)記k已經(jīng)加入U(xiǎn)for(j=0;j<g.n;j++) //修改數(shù)組lowcostclosest{if(g.edges[k][j]!=0&&g.edges[k][j]<lowcost[j]){lowcost[j]=g.edges[k][j];closest[j]=k;}}}}intmain(void){intv=0;MatGraphg;intn=6;inte=10;intA[MAXV][MAXV]={{0,5,8,7,INF,3},{5,0,4,INF,INF,INF},{8,4,0,5,INF,9},{7,INF,5,0,5,6},{INF,INF,INF,5,0,1},{3,INF,9,6,1,0}};CreateMat(g,A,n,e); //printf("G:\n");DispMat(g);printf("普里姆算法求解最小生成樹:\n");Prim(g,v);return0;}8.6#include<stdio.h>#include<malloc.h>#defineINF 32767 //∞#defineMAXV 100 //最大頂點(diǎn)個(gè)數(shù)typedefcharInfoType;/*-------------------------以下定義鄰接矩陣類型 */typedefstruct{intno; //頂點(diǎn)編號(hào)InfoTypeinfo; //頂點(diǎn)信息}VertexType; //頂點(diǎn)類型typedefstruct{intedges[MAXV][MAXV]; //鄰接矩陣數(shù)組(用一個(gè)二維數(shù)組存放頂點(diǎn)間關(guān)系(或弧))intn; //頂點(diǎn)數(shù)inte; //邊數(shù)vexs[MAXV]; //存放頂點(diǎn)信息(用一個(gè)一維數(shù)組存放圖中所有頂點(diǎn)數(shù)據(jù))}MatGraph; //完整的圖鄰接矩陣類型//鄰接表表示法-將每個(gè)頂點(diǎn)的鄰接點(diǎn)串成一個(gè)單鏈表/*-----------以下定義鄰接表類型 */typedefstructArcNode{intadjvex; //該邊的鄰接點(diǎn)編號(hào)structArcNode*nextarc; //指向下一條邊的指intweight; //()}ArcNode; //邊結(jié)點(diǎn)類型typedefstructVNode{InfoTypeinfo; //頂點(diǎn)其他信息intcnt; //,僅用于拓?fù)渑判駻rcNode*firstarc; //指向第一條邊}VNode; //鄰接表結(jié)點(diǎn)類型typedefstruct{VNodeadjlist[MAXV]; //鄰接表頭結(jié)點(diǎn)數(shù)組intn; //圖中頂點(diǎn)數(shù)inte; //圖中邊數(shù)}AdjGraph; //完整的圖鄰接表類型/*-------------------------鄰接矩陣的基本運(yùn)算算法 *//*------------由邊數(shù)組A、頂點(diǎn)數(shù)n和邊數(shù)e創(chuàng)建圖的鄰接矩陣g */voidCreateMat(MatGraph&g,intA[MAXV][MAXV],intn,inte){inti,j;g.n=n;g.e=e;for(i=0;i<g.n;i++)for(j=0;j<g.n;g.edges[i][j]=A[i][j];}/*------------輸出鄰接矩陣g */voidDispMat(MatGraphg){inti,j;for(i=0;i<g.n;i++){for(j=0;j<g.n;j++){if(g.edges[i][j]!=INF)printf("%4d",g.edges[i][j]);elseprintf("%4s","∞");}printf("\n");}}/*-------------------------鄰接表的基本運(yùn)算算法 *//*-------------------由邊數(shù)組A、頂點(diǎn)數(shù)n和邊數(shù)e創(chuàng)建圖的鄰接表G */voidCreateAdj(AdjGraph*&G,intA[MAXV][MAXV],intn,inte){inti,j;ArcNode*p;G=(AdjGraph*)malloc(sizeof(AdjGraph));for(i=0;i<n;i++) //初值NULL{G->adjlist[i].firstarc=NULL;}for(i=0;i<n;i++) //檢查鄰接矩陣中的每個(gè)元素{for(j=n-1;j>=0;j--){if(A[i][j]!=0&&A[i][j]!=INF) //存在一條邊{p=(ArcNode*)malloc(sizeof(ArcNode));創(chuàng)建一個(gè)結(jié)點(diǎn)p->adjvex=j; //鄰接點(diǎn)編號(hào)p->weight=A[i][j]; //邊的權(quán)重p->nextarc=G->adjlist[i].firstarc; //采用頭插法插入結(jié)點(diǎn)G->adjlist[i].firstarc=p;}}}G->n=n;G->e=e;}/*-------------------輸出鄰接表G */voidDispAdj(AdjGraph*G){ArcNode*p;for(inti=0;i<G->n;i++){p=G->adjlist[i].firstarc;printf("%d:",i);while(p!=NULL){printf("%3d[%d]->",p->adjvex,p->weight); //[p=p->nextarc;}printf("∧\n");}}/*-------------------銷毀圖的鄰接表G */voidDestroyAdj(AdjGraph*&G){ArcNode*pre,*p;for(inti=0;i<G->n;i++){pre=G->adjlist[i].firstarc; //pre指向第iif(pre!=NULL){p=pre->nextarc;while(p!=NULL) //i個(gè)單鏈表的所有邊結(jié)點(diǎn){free(pre);pre=p;p=p->nextarc;}free(pre);}}free(G); //釋放頭結(jié)點(diǎn)數(shù)組}#defineMAX_SIZE 100typedefstructEdge{intu; //邊的起始頂點(diǎn)intv; //邊的終止頂點(diǎn)intw; //邊的權(quán)值}Edge;/**/r/