c語(yǔ)言程序設(shè)計(jì)第七章網(wǎng)-預(yù)覽頁(yè)
【正文】 1 1 0 0 0 A B C D E A B C D E 鄰接矩陣表示法特點(diǎn)： 1）無(wú)向圖鄰接矩陣是對(duì)稱矩陣，同一條邊表示了兩次； 2）頂點(diǎn) v的度：在無(wú)向圖中等于二維數(shù)組對(duì)應(yīng)行（或列） 中 1的個(gè)數(shù)；在有向圖中 , 統(tǒng)計(jì)第 i 行 1 的個(gè)數(shù)可得 頂點(diǎn) i 的出度，統(tǒng)計(jì)第 j 列 1 的個(gè)數(shù)可得頂點(diǎn) j 的 入度。 // 該弧相關(guān)信息的指針 } ArcCell, AdjMatrix[MAX_VERTEX_NUM] [MAX_VERTEX_NUM]。 // 頂點(diǎn)數(shù)，弧數(shù) GraphKind kind。 A B E C D 有向圖的逆鄰接表 A B C D E 3 0 3 4 2 0 ? ? ? ? ? 0 1 2 3 4 在有向圖的鄰接表中，對(duì)每個(gè)頂點(diǎn)，鏈接的是指向該頂點(diǎn)的弧。 // 指向下一條弧的指針 InfoType *info。 // 指向第一條依附該頂點(diǎn)的弧 } VNode, AdjList[MAX_VERTEX_NUM]。 // 圖的種類標(biāo)志 } ALGraph。 } VexNode。 typedef struct { VexNode xlist[MAX_VERTEX_NUM]。 // 訪問(wèn)標(biāo)記 int ivex, jvex。 邊的結(jié)構(gòu)表示 typedef struct { // 鄰接多重表 VexBox adjmulist[MAX_VERTEX_NUM]。 EBox *firstedge。 一、深度優(yōu)先搜索遍歷圖 連通圖的深度優(yōu)先搜索遍歷 V w1 SG1 SG2 SG3 W W2和 W3 均為 V 的鄰接點(diǎn)， SG SG2 和 SG3 分別為含頂點(diǎn)W W2和 W3 的子圖。 VisitFunc(v)。 // 對(duì) v的尚未訪問(wèn)的鄰接頂點(diǎn) w // 遞歸調(diào)用 DFS } // DFS 首先將圖中每個(gè)頂點(diǎn)的訪問(wèn)標(biāo)志設(shè)為 FALSE, 之后搜索圖中每個(gè)頂點(diǎn)，如果未被訪問(wèn)，則以該頂點(diǎn)為起始點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點(diǎn)。 v。 ++v) if (!visited[v]) DFS(G, v)。 若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。 //初始化訪問(wèn)標(biāo)志 InitQueue(Q)。 Visit(u)。 w!=0。 // 訪問(wèn)的頂點(diǎn) w入隊(duì)列 } // if } // while 連通分量 (Connected ponent) 當(dāng)無(wú)向圖為非連通圖時(shí) , 從圖中某一頂點(diǎn)出發(fā) , 利用深度優(yōu)先 搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點(diǎn) , 只能訪問(wèn)到該頂點(diǎn)所在的最大連通子圖 (連通分量 )的所有頂點(diǎn)。 E D H G I K L A B F C J M H G I K L A B F C J M E D 非連通無(wú)向圖 DFS 訪問(wèn)序列 : ALMJBFC DE GKHI L A B F C J M H G I K L A B F C J M E D E D H G I K H G I K L A B F C J M E D (連通網(wǎng)的 )最小生成樹(shù) 假設(shè)要在 n 個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通 n 個(gè)城市只需要修建 n1條線路， 如何在最節(jié)省經(jīng)費(fèi)的前提下建立 這個(gè) 通訊網(wǎng) ？ 問(wèn)題： 構(gòu)造網(wǎng)的一棵最小生成樹(shù)，即： 在 e 條帶權(quán)的邊中選取 n1 條邊（不構(gòu)成回路），使“ 權(quán)值之和 ”為最小 。 普里姆算法的基本思想 : 在生成樹(shù)的構(gòu)造過(guò)程中，圖中 n 個(gè)頂點(diǎn)分屬兩個(gè)集合： 已落在生成樹(shù)上的頂點(diǎn)集 U 和尚未落在生成樹(shù)上的頂點(diǎn)集VU ，則應(yīng) 在所有連通 U中頂點(diǎn)和 VU中頂點(diǎn)的邊中選取權(quán)值最小的邊 。 adjvex lowcost a b c d e g f 19 5 14 18 27 16 8 21 3 12 7 c l o s e d g e0 1 2 3 4 5 6A dj v e xL o w c os ta a a 19 14 18 e12 e e8 16 d 3 d d 7 21 c 50 1 2 3 4 5 6 U: VU: a b c d e f g 0 19 ∞ ∞ 14 ∞ 18 19 0 5 7 12 ∞ ∞ ∞ 5 0 3 ∞ ∞ ∞ ∞ 7 3 0 8 21 ∞ 14 12 ∞ 8 0 ∞ 16 ∞ ∞ ∞ 21 ∞ 0 27 18 ∞ ∞ ∞ 16 27 0 a b c d e f g a b c d e f g void MiniSpanTree_P(MGraph G, VertexType u) { //用普里姆算法從頂點(diǎn) u出發(fā)構(gòu)造網(wǎng) G的最小生成樹(shù) k = LocateVex ( G, u )。 closedge[k].lowcost = 0。 k = minimum(closedge)。 j。 克魯斯卡爾算法的基本思想： a b c d e g f 19 5 14 18 27 16 8 21 3 12 7 例如 : 算法描述 : 構(gòu)造非連通圖 ST=( V,{ } )。 若 (u,v)加入 ST后不使 ST中產(chǎn)生回路 ， 則 輸出邊 (u,v)。 何謂“拓?fù)渑判颉保? 對(duì)有向圖進(jìn)行如下操作： 按照有向圖給出的次序關(guān)系，將圖中頂點(diǎn)排成一個(gè)線性序列，對(duì)于有向圖中沒(méi)有限定次序關(guān)系的頂點(diǎn)，則可以人為加上任意的次序關(guān)系。 InitStack(s) For(i=0。 While(!StackEmpty(s)) { pop(s,i)。p。 } 關(guān)鍵路徑 問(wèn)題 : 假設(shè)以有向網(wǎng)表示一個(gè)施工流圖，弧上的權(quán)值表示完成該項(xiàng)子工程所需時(shí)間。 源點(diǎn) 匯點(diǎn) 如何求關(guān)鍵活動(dòng)？ “事件 (頂點(diǎn) )” 的 最早發(fā)生時(shí)間 ve(j) ve(j) = 從源點(diǎn)到頂點(diǎn) j的最長(zhǎng)路徑長(zhǎng)度 ； “事件 (頂點(diǎn) )” 的 最遲發(fā)生時(shí)間 vl(k) vl(k) = 從頂點(diǎn) k到匯點(diǎn)的最短路徑長(zhǎng)度 。T) { FindinDdegree(G,indegree)。 while(!StackEmpty(S)) { pop(S,j)。 p。 } } if(count) ruturn ERROR。 while(!StackEmpty(T)) for(Pop(T,j),p=[j].firstarc。 if(vl[k]dutvl[j]) vl[j]=vl[k]dut。 p。 el=vl[k]dut。 下一條 路徑長(zhǎng)度次短 的最短路徑的特點(diǎn)： 路徑長(zhǎng)度最短 的最短路徑的特點(diǎn)： 它只可能有兩種情況：或者是 直接從源點(diǎn)到該點(diǎn) v2(只含一條弧 )； 或者是 從源點(diǎn)經(jīng)過(guò)頂點(diǎn) v1，再到達(dá)該頂點(diǎn) v2(由兩條弧組成 )。 設(shè)置輔助數(shù)組 Dist，其中每個(gè)分量 Dist[k] 表示 當(dāng)前 所求得的從源點(diǎn)到其余各頂點(diǎn) k 的最短路徑。 ????INF INIT Ykvar c sGkD i s t]][0[.][V0和 k之間存在弧 V0和 k之間不存在弧 其中的最小值即為最短路徑的長(zhǎng)度。v。w。} } D[v0]=0。++i){ min= INFINITY。min=D[w]。++w) if(!final[w]amp。 P[w][w]=
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1