普里姆算法求最小生成樹(shù)課程設(shè)計(jì)報(bào)告-在線瀏覽
2025-03-10 17:05本頁(yè)面
【正文】 vertextype vertex。 }vertexnode。typedef struct { AdjList adjlist。}ALgraph。typedef struct{ edgetype vexs[MaxVertexNum]。 int n,e。 /*鄰接表轉(zhuǎn)換成鄰接矩陣輔助結(jié)構(gòu)體*/void CreateMGraph(MGraph *G){ int i,j,k,weight。printf(請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)：)。(Gn),amp。 printf(請(qǐng)輸入頂點(diǎn)信息:)。iGn。(Gvexs[i]))。iGn。jGn。 else Gedges[i][j]=max。 for (k=0。k++){ scanf(\n%d,%d,%d,amp。j,amp。 Gedges[i][j]=weight。 OutPut(G)。 prim(Gedges,Gn,Gvexs)。 printf(\t==無(wú)向網(wǎng)圖鄰接矩陣==\n)。 scanf(%d,%d,amp。(Ge))。 for (i=0。i++) scanf(\n%d,amp。 for (i=0。i++) for (j=0。j++) { if(i==j) Gedges[i][j]=0。 } /*初始化鄰接矩陣*/ printf(輸入邊對(duì)應(yīng)的兩個(gè)頂點(diǎn)的序號(hào)及權(quán)值：)。kGe。i,amp。weight)。 Gedges[j][i]=weight。 OutPut(G)。 prim(Gedges,Gn,Gvexs)。 edgenode *s。 printf(輸入頂點(diǎn)數(shù)和邊數(shù):)。(gn),amp。 printf(\n輸入頂點(diǎn):)。ign。(gadjlist[i].vertex))。 } printf(\n輸入邊和權(quán)值:)。kge。i,amp。w)。 sadjvex=j。 snext=gadjlist[i].firstedges。 } DispAdjList(g)。 edgenode *s。 printf(輸入頂點(diǎn)數(shù)和邊數(shù):)。(gn),amp。 printf(\n輸入頂點(diǎn):)。ign。(gadjlist[i].vertex))。} printf(\n輸入邊和權(quán)值:)。kge。i,amp。w)。 sadjvex=j。 snext=gadjlist[i].firstedges。 s=(edgenode*)malloc(sizeof(edgenode))。 sweight=w。 gadjlist[j].firstedges=s。} prim算法求最小生成樹(shù)/*記錄從頂點(diǎn)集合U到VU的代價(jià)最小的邊的數(shù)組定義*/typedefVertexType adjvex。lowcost。void MiniSpanTree_PRIM (MGraph G,VertexType u)/*利用普里姆算法求從第u個(gè)頂點(diǎn)出發(fā)構(gòu)造網(wǎng)G的最小生成樹(shù)T*/{ int i,j,k。 k=LocateVertex(G,u)。j。 closedge[j].lowcost=[k][j].adj。/*初始時(shí)集合U只包括頂點(diǎn)u*/ printf(最小代價(jià)生成樹(shù)的各條邊為:\n)。i。/*k為與U中頂點(diǎn)相鄰接的下一個(gè)頂點(diǎn)的序號(hào)*/ printf((%s%s)\n,closedge[k].adjvex,[k])。/*第k頂點(diǎn)并入U(xiǎn)集*/ for(j=0。j++) if([k][j].adjclosedge[j].lowcost)/*新頂點(diǎn)加入U(xiǎn)集后重新將最小邊存入到數(shù)組*/ { strcpy(closedge[j].adjvex,[k])。 } }}void OutPut (MGraph *G){ int i,j。 for (i=0。i++) printf(%d ,Gvexs[i])。 printf(\n)。iGn。jGn。 printf(\n)。 edgenode *p。 for (i=0。 i++) { printf([%d,%3d]=,i,gadjlist[i].vertex)。 while (p!=NULL) { printf((%d,%d),padjvex,pweight)。 } printf(^\n)。 edgenode *p。 M=(graph*)malloc(sizeof(graph))。 Me=ge。iMe。jMe。 else Medges[i][j]=MaxVertexNum。ign。 for(i=0。i++){ p=gadjlist[i].firstedges。 p=pnext。}4 測(cè)試選取包含六個(gè)頂點(diǎn)及10條邊的圖進(jìn)行程序的測(cè)試，分別將需要測(cè)試的數(shù)據(jù)按要求鍵入，根據(jù)提示進(jìn)行下級(jí)菜單的確定與選擇，直到求解出測(cè)試數(shù)據(jù)的最小生成樹(shù)。其中鄰接矩陣存儲(chǔ)有向圖、無(wú)向圖及調(diào)用普里姆算法生成最小生成樹(shù)、任務(wù)書(shū)填寫(xiě)由舒勝、樊坤完成；鄰接表存儲(chǔ)有向圖、無(wú)向圖及調(diào)用普里姆算法生成最小生成樹(shù)、菜單界面由黃義完成；周德負(fù)責(zé)流程圖繪制、文檔排版等綜合應(yīng)用。數(shù)據(jù)結(jié)構(gòu)這門課是非常奧妙的。正是這些奇妙的東西引發(fā)我在計(jì)算機(jī)科學(xué)這條大路上一直迸發(fā)前進(jìn)，勇敢的去探索科學(xué)中未知而美妙的事。typedef int EdgeType。 EdgeType edges[MaxVertexNum][MaxVertexNum]。 }MGraph。typedef struct node{ int adjvex。 struct node *next。typedef s
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1