徐州工程學(xué)院數(shù)據(jù)結(jié)構(gòu)最小生成樹實(shí)驗(yàn)文檔

1、實(shí)驗(yàn)九 圖的最小生成樹算法的實(shí)現(xiàn)實(shí)驗(yàn)預(yù)備知識：1 .理解圖最小生成樹的意義和相應(yīng)算法。2. 掌握帶權(quán)圖的存儲結(jié)構(gòu)。、實(shí)驗(yàn)?zāi)康?. 使學(xué)生熟悉最小生成樹的算法實(shí)現(xiàn)。2. 掌握帶權(quán)圖的存儲結(jié)構(gòu)和處理方法。二、實(shí)驗(yàn)環(huán)境1. 硬件：每個學(xué)生需配備計(jì)算機(jī)一臺。操作系統(tǒng)：DOS或Windows2. 軟件：DOS或 Windows操作系統(tǒng) +Turbo C;三、實(shí)驗(yàn)要求1. 能夠獨(dú)立完成帶權(quán)圖的存儲和最小生成樹的生成 四、實(shí)驗(yàn)內(nèi)容1. 在自己的U盤的“姓名+學(xué)號”文件夾中創(chuàng)建“實(shí)驗(yàn)9”文件夾，本 次實(shí)驗(yàn)的所有程序和數(shù)據(jù)都要求存儲到本文件夾中。2. 現(xiàn)在某電信公司要對如下圖的幾個城市之間進(jìn)行光纖連接布線，請

2、用合適的存儲結(jié)構(gòu)將下圖存儲到計(jì)算機(jī)中方便進(jìn)行處理。3. 現(xiàn)在公司想以最小的代價將所有城市連通，方便所有城市間通信，請用 普里姆算法和克魯斯卡爾算法實(shí)現(xiàn)本圖的最小生成樹#in clude <stdio.h>#in clude <stdlib.h>#defi neINF 50typ edef struct ArcNodeint adjvex;struct ArcNode *n extarc; int weight;ArcNode;/該弧所指向的頂點(diǎn)位置/下一個臨接點(diǎn)/弧的權(quán)重/表結(jié)點(diǎn)/頂點(diǎn)信息/指向下一個結(jié)點(diǎn)typ edef struct VNode char data;

3、ArcNode *firstarc;VNode,AdjList6;typ edef struct AdjList LH; int vexnum; int arcnum;Grap h;創(chuàng)建頭結(jié)點(diǎn)數(shù)組/圖的點(diǎn)的個數(shù)/圖的邊的個數(shù)typ edef struct char n extvex; int lowcost; int know;/輔助數(shù)組結(jié)構(gòu)體Auxiliary_array;void main (void)void buildtu (Gra ph*);void prin tgra ph(Gra ph*);void p rim( Graph *G, char u);char u;Graph UD

4、G;Graph *G = & UDG;buildtu(G);printgraph(G);/ 打印圖printf(”請輸入起始頂點(diǎn)：n"); while(getchar()!='n');u = getchar();prim(G ,u);void buildtu (Gra ph *G) / 建圖int search(Gra ph *G,char a);int i,n 1, n2,w; char a,b; ArcNode *p, *q;printf(”請輸入頂點(diǎn)個數(shù)和邊的條數(shù)：n”)；scan f("%d %d",&G->vex n

5、um,&G->arc num);printf(”請輸入頂點(diǎn)信息n");for (i = 0; i < G->vex num; +i)while (getchar()!='n');sca nf("%c", &G->LHi.data); G->LHi.firstarc = NULL;printf(”請輸入有關(guān)系的結(jié)點(diǎn)和該邊的權(quán)重:n");for(i=0;i<G->arc nu m;+i)while (getchar()!='n');sca nf("%c %c

6、%d"，& a,&b,&w);n 1=search(G,a);n2=search(G,b);p=G->LH n1.firstarc;if(p = NULL)p=G->LH n1.firstarc=(ArcNode *) malloc (sizeof(ArcNode); elsewhile( p-> nextarc !=NULL )p=p->n extarc;p=p->n extarc=(ArcNode *) malloc (sizeof(ArcNode);q=G->LH n2.firstarc;if(q = NULL)q=G

7、->LH n2.firstarc=(ArcNode *) malloc (sizeof(ArcNode);elsewhile( q-> nextarc !=NULL )q=q->n extarc;q=q->n extarc=(ArcNode *) malloc (sizeof(ArcNode); p->adjvex=n2;p->weight=w;p->n extarc=NULL;q->adjvex=n1; q->weight=w; q->n extarc=NULL;int search (Graph *G,char a) II確定頂點(diǎn)

8、a在頭結(jié)點(diǎn)數(shù)組中的位置 int i;for(i=0;i<G->vex nu m;+i)if(G->LHi.data=a) return i;void printgraph(Graph *G)/ 打印圖int i;ArcNode *p;for (i=0 ; i < G->vex num; +i)p=G->LHi.firstarc;prin tf("data:%c t",G->LHi.data);while( p!=NULL)prin tf("firstarc->adjvex=%d", p->adjvex

9、); p=p->n extarc;prin tf("n");void prim( Graph *G, char u)/用prim算法實(shí)現(xiàn)最小生成樹 int search (Gra ph *G,char a);int mi ni mize(Gra ph *G, Auxiliary_array);void prin ttable(Auxiliary_array);Auxiliary_array A6;/ 創(chuàng)建輔助數(shù)組int i,j,seat;int locatio n;ArcNode *p ;for (i = 0; i < G->vex num; +i) Ai

10、 .n extvex = '0'Ai.k now = 0;Ai.lowcost = INF;location = search(G ,u);/確定u元素在頭結(jié)點(diǎn)數(shù)組中的位置 for (p=G->LHlocati on .firstarc ; p != NULL; p=p->n extarc )i = p->adjvex;Ai. nextvex = G->LHlocati on .data;Ai .lo wcost = p->weight;Ai.k now = 0;Alocati on .k now = 1;Alocati on .lowcost =

11、 0;Alocati on . nextvex = 'O'for(j=0;j<G->vex nu m-1;+j)seat = mini mize( G,A );prin tf("select min: %dn", seat);Aseat.k now = 1;p=G->LHseat.firstarc;for (p; p != NULL; p=p->n extarc)i=p->adjvex;if(Ai.k now = 0 && p->weight < Ai.lowcost)Ai. nextvex = G-

12、>LHseat.data;Ai .lo wcost = p->weight;printtable(A); /打印輔助數(shù)組中的信息for (j = 0; j < G->vex num; +j)if (j != locati on)prin tf("%c<->%c rr,Aj. nextvex,G->LHj.data);int mi nimize(Gra ph *G, Auxiliary_array A)/取出輔助數(shù)組中權(quán)值最小的頂點(diǎn)所在的位置int i,p lace ,num;num = INF;for (i = 0; i < G->

13、;vex num; +i)if(Ai.k now = 0 && num >= Ai.lowcost) num = Ai.lowcost;p lace = i;retur n p lace; void prin ttable(Auxiliary_array A) / 打印輔助數(shù)組int i;for (i = 0; i < 6; i+) prin tf("modifier:%clowcost:%d known:%dn",Ai. nextvex,Ai.lowcost,Ai.k no w);實(shí)驗(yàn)總結(jié)：通過該實(shí)驗(yàn)，我深刻明白到了自己對循環(huán)的能力不足，書寫代

14、碼的邏輯性也不夠 強(qiáng)，相信在以后的學(xué)習(xí)中能加強(qiáng)這方面的學(xué)習(xí)，爭取在以后的學(xué)習(xí)中解決這兩個方面 的問題。請福j m點(diǎn)牛我利7占的索；聶: 13請輜入頂點(diǎn)信息abdf請輸入有關(guān)系的結(jié)點(diǎn)和該邊的權(quán)重;bcdf c d £1firstarc->adjuex= 1 f irttar(;->adjuex=2f irsterc->acl ju«x=3 firstarc->adjuex=Ofirstarc->adjuex=firstarc->aci juex=2 firstarc->adjuex=Ofiritarc->adju«x=

15、>lfirstare->adju#x=5firstarc->adjuex=1datadatadataf ir®tarc->aclkiex=3 dat A data ：e data：ffirstflrc->fldjuex=Ofirstart->adjuex=5firstarc->aci jux=2 firs t arc->adj uex=1firetarc*>adjvex=2fir&terc-adjyex=5 firstarc->adjuex=2fir3tarc->adjuexi3firstarc->aci ju*x=4 請輸入起始頂點(diǎn)！3w«lectselectselectselect001 電 Ctmin： min： min：min： mini itiodifier：O