圖的各種算法(深度、廣度等)(編輯修改稿)
2025-08-21 03:44 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 1 0 4 4 top 2 p=NULL 0 0 0 0 in link 5 5 4 3 ^ ^ ^ vex next 1 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 1 3 2 3 2 1 0 4 4 top 2 p=NULL 0 0 0 0 in link 5 5 4 3 ^ ^ ^ vex next 1 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 1 3 2 3 2 1 0 4 4 top p=NULL 0 0 0 0 in link 5 5 4 3 ^ ^ ^ vex next 1 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 1 3 2 4 3 2 1 0 4 4 top 0 0 0 0 in link 5 5 4 3 ^ ^ ^ vex next 1 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 1 3 2 4 3 2 1 0 4 top p 0 0 0 0 in link 5 5 4 3 ^ ^ ^ vex next 0 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 1 3 2 4 3 2 1 0 4 top p 5 0 0 0 0 in link 5 5 4 3 ^ ^ ^ vex next 0 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 1 3 2 4 3 2 1 0 4 top p=NULL 5 0 0 0 0 in link 5 5 4 3 ^ ^ ^ vex next 0 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 1 3 2 4 5 3 2 1 0 4 top 5 0 0 0 0 in link 5 5 4 3 ^ ^ ^ vex next 0 ^ 2 5 ^ 2 4 0 1 2 3 4 5 6 ^ 輸出序列： 6 1 3 2 4 5 3 2 1 0 4 top p=NULL 49 拓?fù)渑判蛩惴蚣?: Status TopologicalOrder(ALGraph G, Stack amp。T) { // 算法 // 有向網(wǎng) G采用鄰接表存儲(chǔ)結(jié)構(gòu)， T為拓?fù)湫蛄卸c(diǎn)棧， S為零入度頂點(diǎn)棧。 // 若 G無回路則用棧 T返回 G的一個(gè)拓?fù)湫蛄?,且函數(shù)值為 OK,否則為 ERROR。 FindInDegree(G, indegree)。 // 對(duì)各頂點(diǎn)求入度indegree[0..vernum1] for (int j=0。 j。 ++j) // 建零入度頂點(diǎn)棧 S if (indegree[j]==0) Push(S, j)。 // 入度為 0者進(jìn)棧 InitStack(T)。//建拓?fù)湫蛄许旤c(diǎn)棧 T count = 0。 while (!StackEmpty(S)) { Pop(S, j)。 Push(T, j)。 ++count。 // j號(hào)頂點(diǎn)入 T棧并計(jì)數(shù) for (p=[j].firstarc。 p。 p=pnextarc) { k = padjvex。 // 對(duì) j號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減 1 if (indegree[k] == 0) Push(S, k)。 // 若入度減為 0，則入棧 }//for }//while if (count) return ERROR。 // 該有向網(wǎng)有回路 else return OK。 } // TopologicalOrder 構(gòu)造網(wǎng)的一棵最小生成樹，即： 在 e 條帶權(quán)的邊中選取 n1 條邊（不構(gòu)成回路），使“權(quán)值之和”為最小 。 算法二：（克魯斯卡爾算法） 算法一：（普里姆算法） 四、最小生成樹 ? 構(gòu)造最小生成樹方法 –方法一：普里姆 (Prim)算法 187。算法思想：設(shè) N=(V,{E})是連通網(wǎng)， TE是 N上最小生成樹中邊的集合 ?初始令 U={u0},(u0?V), TE=? ?在所有 u?U,v?VU的邊 (u,v)?E中，找一條代價(jià)最小的邊 (u0,v0) ?將 (u0,v0)并入集合 TE， 同時(shí) v0并入 U ?重復(fù)上述操作直至 U=V為止，則 T=(V,{TE})為N的最小生成樹 187。算法實(shí)現(xiàn)：圖用鄰接矩陣表示 a b c d e g f 19 5 14 18 27 16 8 21 3 12 7 例如 : 所得生成樹權(quán)值和 = 14+8+3+5+16+21 = 67 在生成樹的構(gòu)造過程中，圖中 n 個(gè)頂點(diǎn)分屬兩個(gè)集合： 已落在生成樹上的頂點(diǎn)集 U 和尚未落在生成樹上的頂點(diǎn)集VU ，則應(yīng) 在所有連通 U中頂點(diǎn)和 VU中頂點(diǎn)的邊中選取權(quán)值最小的邊 。 一般情況下所添加的頂點(diǎn)應(yīng)滿足下列條件 : U VU 設(shè)置一個(gè)輔助數(shù)組，對(duì)當(dāng)前 V－ U集中的每個(gè)頂點(diǎn)，記錄和頂點(diǎn)集 U中頂點(diǎn)相連接的代價(jià)最小的邊： struct { VertexType adjvex。 // U集中的頂點(diǎn)序號(hào) VRType lowcost。 // 邊的權(quán)值 } closedge[MAX_VERTEX_NUM]。 a b c d e g f 19 5 14 18 27 16 8 21 3
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1