最小生成樹和最短路徑-數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)(編輯修改稿)
2025-07-20 20:11 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 X_NUM]。 int k=0。 for (int i=0。i。i++) { for (int j=0。j。j++) { if ([i][j].adj!=INFINITY) { E[k].va=i。 E[k].vb=j。 E[k].w=[i][j].adj。 k++。 } } } Heapsort(E,G)。 Initialize(G)。 //初始化輔助數(shù)組 k=1。 //生成的邊數(shù)，最后要?jiǎng)偤脼榭傔厰?shù) int j=0。 //E中的下標(biāo) printf(最小代價(jià)生成樹的各條邊及相應(yīng)權(quán)值為:\n)。 while (k) { int sn1=Vset[E[j].va]。 int sn2=Vset[E[j].vb]。 //得到兩頂點(diǎn)屬于的集合編號(hào) if (sn1!=sn2) //不在同一集合編號(hào)內(nèi)的話，把邊加入最小生成樹 { printf((%s%s):%d\n,[E[j].va],[E[j].vb],E[j].w)。 k++。 for (i=0。i。i++) if (Vset[i]==sn2) Vset[i]=sn1。 } j++。 }} void main() { MGraph G。 CreateAN(G)。 cout普里姆算法輸出從頂點(diǎn)V1出發(fā)的最小生成樹\nendl。 MiniSpanTree_PRIM(G,[0])。 cout\nendl。 cout克魯斯卡爾算法輸出從頂點(diǎn)V1出發(fā)的最小生成樹\nendl。 MiniSpanTree_Kruskal(G)。 coutendl。 }運(yùn)行結(jié)果： l 采用迪杰斯特拉算法求單源最短路徑ecgfadb152125 431086 94編寫一個(gè)算法，采用迪杰斯特拉算法，輸出如下圖所示的有向帶權(quán)圖G中從頂點(diǎn)a到其他各頂點(diǎn)的最短路徑長(zhǎng)度和最短路徑。圖的存儲(chǔ)結(jié)構(gòu)自選。 源代碼：: includeincludeinclude //malloc( )include // INT ,MAXinclude //EOF,NULLinclude //atoi( )include //eof( )include //floor( ),ceil( ),abs( )include //exit( )include //cout,cin//函數(shù)結(jié)果狀態(tài)代碼define TRUE 1define FALSE 0define OK 1define ERROR 0define INFEASIBLE 1//OVERFLOW 在 中已定義為3typedef int Status。typedef int Boolean。 // 布爾類型:includedefine MAX_NAME 5 /* 頂點(diǎn)字符串的最大長(zhǎng)度+1 */define MAX_INFO 20 /* 相關(guān)信息字符串的最大長(zhǎng)度+1 */typedef int VRType。typedef char InfoType。typedef char VertexType[MAX_NAME]。/*圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示 */define INFINITY INT_MAX /* 用整型最大值代替∞ */define MAX_VERTEX_NUM 20 /* 最大頂點(diǎn)個(gè)數(shù) */typedef enum{DG,DN,AG,AN}GraphKind。 /* {有向圖,有向網(wǎng),無(wú)向圖,無(wú)向網(wǎng)} */typedef struct{ VRType adj。 /* 頂點(diǎn)關(guān)系類型。對(duì)無(wú)權(quán)圖，用1(是)或0(否)表示相鄰否； */ /* 對(duì)帶權(quán)圖，c則為權(quán)值類型 */ InfoType *info。 /* 該弧相關(guān)信息的指針(可無(wú)) */}ArcCell,AdjMatrix[MAX
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1