圖的操作算法

2020年112020年1110日一、實驗目的及要求熟悉各種圖的存儲結構。掌握圖的各種搜索路徑的遍歷方法。二、實驗內(nèi)容（或?qū)嶒炘?、實驗拓撲?.任選一種存儲結構（鄰接表為主），完成圖的DFS（深度優(yōu)先遍歷）和BFS（廣度優(yōu)先遍歷）的操作（8.18.2）2．練習如何構造最小生成樹（8.58.6）3.練習如何尋找并求得關鍵路徑并調(diào)試出例8.15的拓撲排序。學生姓名學號實驗成績專業(yè)19計科班級2班實驗日期課程名稱數(shù)據(jù)結構與算法任課教師實驗名稱圖的操作算法實驗序號實驗地點S510實驗臺號指導教師三、實驗設備與環(huán)境三、實驗設備與環(huán)境WindowsDEV-C++四、實驗設計方案（包括實驗步驟、設計思想、算法描述或開發(fā)流程等）8.1設計思路CreateMat(&g):創(chuàng)建圖，由相關數(shù)據(jù)構造一個圖gDispMat(g):輸出圖，顯示圖g的頂點和邊信息。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++) 給鄰接表中所有頭結點的指針域置初值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)建一個結點p->adjvex=j; //鄰接點編號p->weight=A[i][j]; //邊的權重p->nextarc=G->adjlist[i].firstarc; //采用頭插法插入結點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("頂點%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; //preiif(pre!=NULL){p=pre->nextarc;while(p!=NULL)//釋放第i個單鏈表的所有邊結點{free(pre);pre=p;p=p->nextarc;}free(pre);}}free(G); //釋放頭結點數(shù)組}8.2DFS(g,v):從頂點v出發(fā)深度優(yōu)先遍歷圖g.BFS(g,v):從頂點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的第一個鄰接點while(p)//查找v的所有臨界點{if(visited[p->adjvex]==0)//若當前鄰接點未被訪問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;//恢復環(huán)境，使該頂點可重復使用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的下一個鄰接點}}printf("\n");}voidBFS(ALGraph*G,intv){ArcNode*p;//定義指針intqueue[MAXV],front=0,rear=0;//定義頂點訪問標記數(shù)組intw,i;for(i=0;i<G->n;i++)//訪問標記數(shù)組初始化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");}8.5鄰接矩陣的基本運算算法 */創(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];}鄰接表的基本運算算法創(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));p->adjvex=j;鄰接點編號p->weight=A[i][j];//邊的權重p->nextarc=G->adjlist[i].firstarc; //采用頭插法插入結點G->adjlist[i].firstarc=p;}}}}8.6

G->n=n;G->e=e;鄰接矩陣的基本運算算法創(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");}}鄰接表的基本運算算法創(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++) 給鄰接表中所有頭結點的指針域置初值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));p->adjvex=j;鄰接點編號p->weight=A[i][j];//邊的權重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個單鏈表的首結點if(pre!=NULL){p=pre->nextarc;while(p!=NULL)//釋放第i個單鏈表的所有邊結點{free(pre);pre=p;p=p->nextarc;}free(pre);}}free(G); //釋放頭結點數(shù)組}功能:采用克魯斯卡爾算法輸出圖g的一棵最小生成樹(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邊集合按權值w:\n");for(i=0;i<g.e;i++){printf(" 邊(%d,%d)=%d\n",E[i].u,E[i].v,E[i].w);}printf("圖全部頂點集合vset={");for(i=0;i<g.n;i++)//初始化輔助數(shù)組{vset[i]=i;printf("%d",vset[i]);}printf("}\n");k=1;//k表示當前構造生成樹的第幾條邊,初值為1j=0;//E中邊的下標,初值為0while(k<g.n)//生成的邊數(shù)小于頂點個數(shù)n時循環(huán){u1=E[j].u;//取一條邊的起始頂點和終止頂點v1=E[j].v;sn1=vset[u1];sn2=vset[v1];//分別得到兩個頂點所屬的集合編號printf(" 起始頂點u1=%d所屬集合編號sn1=%d,終止頂點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++)//兩個集合統(tǒng)一編號{if(vset[i]==sn2) //集合編號為sn2的改為sn1{vset[i]=sn1;}}}j++; //掃描下一條邊}}8.15*------------------采用鄰接矩陣存儲的圖g中從頂點v出發(fā)進行深度優(yōu)先遍歷 */staticvoidMDFS(MatGraphg,intv){intw;visited[v]=1; //置訪問標記for(w=0;w<g.n;w++)//找頂點v的所有鄰接點{if((g.edges[v][w]!=0)&&(g.edges[v][w]!=INF)&&(visited[w]==0)){MDFS(g,w);//找頂點v的未訪問過的鄰接點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 //若不連通，則恢復第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ù)據(jù)、運行結果等）8.18.28.58.68.15六、實驗小結（包括收獲、心得體會、注意事項、存在問題及解決辦法、建議等）通過這節(jié)課的學習，我獲得了很多知識，有很大的收獲。老師也講的很仔細，熟悉了各種圖的存儲結構，并且也掌握圖的各種搜索路徑的遍歷方法。領會了圖的兩種存儲結構，兩種遍歷方法以及深度優(yōu)先遍歷和廣度優(yōu)先遍歷，但是還有一些細節(jié)掌握的還不是太好，還應該多加練習，，尤其是在一些算法的實現(xiàn)時，具體的思想還是了解了。七、附錄（包括作品、流程圖、源程序及命令清單等）8.1#include<stdio.h>#include<malloc.h>#defineINF 32767 //∞#defineMAXV 100 //最大頂點個數(shù)typedefcharInfoType;/*-------------------------以下定義鄰接矩陣類型 */typedefstruct{intno; //頂點編號InfoTypeinfo; //頂點信息}VertexType; //頂點類型typedefstruct{intedges[MAXV][MAXV]; //(間關系))intn; //頂點數(shù)inte; //邊數(shù)vexs[MAXV]; //存放頂點信息()}MatGraph; //完整的圖鄰接矩陣類型//鄰接表表示法-將每個頂點的鄰接點串成一個單鏈表/*-----------以下定義鄰接表類型 */typedefstructArcNode{intadjvex; //該邊的鄰接點編號structArcNode*nextarc; //指向下一條邊的指intweight; //()}ArcNode; //邊結點類型typedefstructVNode{InfoTypeinfo; //頂點其他信息intcnt; //,僅用于拓撲排序ArcNode*firstarc; //指向第一條邊}VNode; //鄰接表結點類型typedefstruct{VNodeadjlist[MAXV]; //鄰接表頭結點數(shù)組intn; //圖中頂點數(shù)inte; //圖中邊數(shù)}AdjGraph; //完整的圖鄰接表類型/*-------------------------鄰接矩陣的基本運算算法 *//*------------由邊數(shù)組A、頂點數(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");}}/*-------------------------鄰接表的基本運算算法 *//*-------------------由邊數(shù)組A、頂點數(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)建一個結點p->adjvex=j; //鄰接點編號p->weight=A[i][j]; //邊的權重p->nextarc=G->adjlist[i].firstarc; //采用頭插法插入結點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指向第i個單鏈表的首結點if(pre!=NULL){p=pre->nextarc;while(p!=NULL) //i的所有邊結點{free(pre);pre=p;p=p->nextarc;}free(pre);}}free(G); //釋放頭結點數(shù)組}intmain(void){MatGraphg;AdjGraph*G;intn=6; 圖中的頂點數(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; //頂點編號intinfo; //頂點其余的信息}VertexType;typedefstruct{intedges[MAXV][MAXV]; //鄰接矩陣intn,e; //頂點數(shù)，弧數(shù)VertexTypevexs[MAXV]; //存放頂點信}MGraph;//一下定義鄰接表類型typedefstructANode //弧的節(jié)點結構類型{intadjvex; //structANode*nextarc;intinfo; //弧的相關信息}ArcNode;typedefstructVnode //鄰接表頭結點類型{intdata; //頂點信息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("從頂點0開始的DFS（遞歸算法）：\n");printf("\n");printf("從頂點0開始的DFS（非遞歸算法printf("\n");printf("從頂點0開始的BFS（遞歸算法printf("\n");}8.5#include<stdio.h>#include<malloc.h>#defineINF 32767 //∞#defineMAXV 100 //最大頂點個數(shù)typedefcharInfoType;/*-------------------------以下定義鄰接矩陣類型 */typedefstruct{intno; //頂點編號InfoTypeinfo; //頂點信息}VertexType; //頂點類型typedefstruct{intedges[MAXV][MAXV]; //鄰接矩陣數(shù)組(用一個二維數(shù)組存放頂點間關系(邊或弧)的數(shù)據(jù))intn; //頂點數(shù)inte; //邊數(shù)vexs[MAXV]; //存放頂點信息(用一個一維數(shù)組存放圖中所有頂點數(shù)據(jù))}MatGraph; //完整的圖鄰接矩陣類型//鄰接表表示法-將每個頂點的鄰接點串成一個單鏈表/*-----------以下定義鄰接表類型 */typedefstructArcNode{intadjvex; //該邊的鄰接點編號structArcNode*nextarc; //指向下一條邊的指intweight; //()}ArcNode; //邊結點類型typedefstructVNode{InfoTypeinfo; //頂點其他信息intcnt; //,僅用于拓撲排序ArcNode*firstarc; //指向第一條邊}VNode; //鄰接表結點類型typedefstruct{VNodeadjlist[MAXV]; //鄰接表頭結點數(shù)組intn; //圖中頂點數(shù)inte; //圖中邊數(shù)}AdjGraph; //完整的圖鄰接表類型/*-------------------------鄰接矩陣的基本運算算法 *//*------------由邊數(shù)組A、頂點數(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");}}/*-------------------------鄰接表的基本運算算法 *//*-------------------由邊數(shù)組A、頂點數(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)建一個結點p->adjvex=j; //鄰接點編號p->weight=A[i][j]; //邊的權重p->nextarc=G->adjlist[i].firstarc; //采用頭插法插入結點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個單鏈表的所有邊結點{free(pre);pre=p;p=p->nextarc;}free(pre);}}free(G); //釋放頭結點數(shù)組}/*--------------采用普里姆算法輸出圖g中從頂點v出發(fā)的一棵最小生成樹 *//**功能:采用普里姆算法輸出圖g中從頂點v(n個頂點，n-1條邊)備注:全部頂點的集合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個頂點{min_weight=INF;for(j=0;j<g.n;j++) //在U最近的頂點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; //標記k已經(jīng)加入Ufor(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 //最大頂點個數(shù)typedefcharInfoType;/*-------------------------以下定義鄰接矩陣類型 */typedefstruct{intno; //頂點編號InfoTypeinfo; //頂點信息}VertexType; //頂點類型typedefstruct{intedges[MAXV][MAXV]; //鄰接矩陣數(shù)組(用一個二維數(shù)組存放頂點間關系(或弧))intn; //頂點數(shù)inte; //邊數(shù)vexs[MAXV]; //存放頂點信息(用一個一維數(shù)組存放圖中所有頂點數(shù)據(jù))}MatGraph; //完整的圖鄰接矩陣類型//鄰接表表示法-將每個頂點的鄰接點串成一個單鏈表/*-----------以下定義鄰接表類型 */typedefstructArcNode{intadjvex; //該邊的鄰接點編號structArcNode*nextarc; //指向下一條邊的指intweight; //()}ArcNode; //邊結點類型typedefstructVNode{InfoTypeinfo; //頂點其他信息intcnt; //,僅用于拓撲排序ArcNode*firstarc; //指向第一條邊}VNode; //鄰接表結點類型typedefstruct{VNodeadjlist[MAXV]; //鄰接表頭結點數(shù)組intn; //圖中頂點數(shù)inte; //圖中邊數(shù)}AdjGraph; //完整的圖鄰接表類型/*-------------------------鄰接矩陣的基本運算算法 *//*------------由邊數(shù)組A、頂點數(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");}}/*-------------------------鄰接表的基本運算算法 *//*-------------------由邊數(shù)組A、頂點數(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)建一個結點p->adjvex=j; //鄰接點編號p->weight=A[i][j]; //邊的權重p->nextarc=G->adjlist[i].firstarc; //采用頭插法插入結點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個單鏈表的所有邊結點{free(pre);pre=p;p=p->nextarc;}free(pre);}}free(G); //釋放頭結點數(shù)組}#defineMAX_SIZE 100typedefstructEdge{intu; //邊的起始頂點intv; //邊的終止頂點intw; //邊的權值}Edge;/**/r/