【正文】 TEX_NUM]。 AdjMatrix arcs。 // 頂點(diǎn)數(shù)，弧數(shù) GraphKind kind。 網(wǎng)絡(luò)的鄰接矩陣 ???????????????????jiji,ji,jiji,ji,jijiji若或且若或且若,)(,)(),(]][[0EEEEWA .e d geA B D C E 15 9 7 21 11 3 2 ????????????????0 1 5 ∞ 9 ∞∞ 0 3 ∞ ∞= ∞ ∞ 0 ∞ 2∞ ∞ 2 1 0 ∞1 1 7 ∞ ∞A . e d g e 00 A 1 4 1 B 0 4 5 2 C 3 5 3 D 2 5 4 E 0 1 5 F 1 2 3 B A C D F E 二、圖的鄰接表 存儲表示 同一個(gè)頂點(diǎn)發(fā)出的邊 鏈接在同一個(gè)邊鏈表中 ，每一個(gè)鏈結(jié)點(diǎn)代表一 條邊 (邊結(jié)點(diǎn) ), 結(jié)點(diǎn)中有 另一頂點(diǎn)的下標(biāo) adjvex 和指針 nextedge。 A B E C D 有向圖的逆鄰接表 A B C D E 3 0 3 4 2 0 ? ? ? ? ? 0 1 2 3 4 在有向圖的鄰接表中，對每個(gè)頂點(diǎn)，鏈接的是指向該頂點(diǎn)的弧。 3）在鄰接表上容易找到任一頂點(diǎn)的第一個(gè)鄰接點(diǎn) 和下一個(gè)鄰接點(diǎn) 4）設(shè)存儲頂點(diǎn)的一維數(shù)組大小為 n(圖的頂點(diǎn)數(shù) n), G占用存儲空間： n+e； G占用存儲空間與它的頂 點(diǎn)數(shù)和邊數(shù)有關(guān)；適用于邊稀疏的圖； typedef struct ArcNode { int adjvex。 // 指向下一條弧的指針 InfoType *info。 adjvex nextarc info 弧的結(jié)點(diǎn)結(jié)構(gòu) typedef struct VNode { VertexType data。 // 指向第一條依附該頂點(diǎn)的弧 } VNode, AdjList[MAX_VERTEX_NUM]。 int vexnum, arum。 // 圖的種類標(biāo)志 } ALGraph。 InfoType *info。 } VexNode。 ArcBox *firstin, *firstout。 typedef struct { VexNode xlist[MAX_VERTEX_NUM]。 //有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) } OLGraph。 // 訪問標(biāo)記 int ivex, jvex。 InfoType *info。 邊的結(jié)構(gòu)表示 typedef struct { // 鄰接多重表 VexBox adjmulist[MAX_VERTEX_NUM]。 } AMLGraph。 EBox *firstedge。 無向圖的結(jié)構(gòu)表示 A B C D E 0 1 2 3 4 A B C D E 0 1 0 3 2 1 2 3 2 4 4 1 圖的遍歷 從圖中某個(gè)頂點(diǎn)出發(fā)游歷圖，訪遍 圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn) 僅被訪問一次的過程。 一、深度優(yōu)先搜索遍歷圖 連通圖的深度優(yōu)先搜索遍歷 V w1 SG1 SG2 SG3 W W2和 W3 均為 V 的鄰接點(diǎn)， SG SG2 和 SG3 分別為含頂點(diǎn)W W2和 W3 的子圖。 w2 w3 從上頁的圖解可見 : 1. 從深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷； 解決的辦法是：為每個(gè)頂點(diǎn)設(shè)立一個(gè) “訪問標(biāo)志 visited[w]”。 VisitFunc(v)。 w!=0。 // 對 v的尚未訪問的鄰接頂點(diǎn) w // 遞歸調(diào)用 DFS } // DFS 首先將圖中每個(gè)頂點(diǎn)的訪問標(biāo)志設(shè)為 FALSE, 之后搜索圖中每個(gè)頂點(diǎn)，如果未被訪問，則以該頂點(diǎn)為起始點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點(diǎn)。 VisitFunc = Visit。 v。 // 訪問標(biāo)志數(shù)組初始化 for (v=0。 ++v) if (!visited[v]) DFS(G, v)。 其中， Vw1, Vw2, Vw8 的路徑長度為 1； Vw7, Vw3, Vw5 的 路徑長度為 2； Vw6, Vw4 的路徑長度為 3。 若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。 v。 //初始化訪問標(biāo)志 InitQueue(Q)。 v。 Visit(u)。 // v入隊(duì)列 while (!QueueEmpty(Q)) { DeQueue(Q, u)。 w!=0。 Visit(w)。 // 訪問的頂點(diǎn) w入隊(duì)列 } // if } // while 連通分量 (Connected ponent) 當(dāng)無向圖為非連通圖時(shí) , 從圖中某一頂點(diǎn)出發(fā) , 利用深度優(yōu)先 搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點(diǎn) , 只能訪問到該頂點(diǎn)所在的最大連通子圖 (連通分量 )的所有頂點(diǎn)。 求連通分量的算法需要對圖的每一個(gè)頂點(diǎn)進(jìn)行檢測：若已被訪問過，則該頂點(diǎn)一定是落在圖中已求得的連通分量上；若還未被訪問，則從該頂點(diǎn)出發(fā)遍歷圖，可求得圖的另一個(gè)連通分量 。 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 非連通無向圖 DFS 訪問序列 : 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è)要在 n 個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通 n 個(gè)城市只需要修建 n1條線路， 如何在最節(jié)省經(jīng)費(fèi)的前提下建立 這個(gè) 通訊網(wǎng) ？ 問題： 構(gòu)造網(wǎng)的一棵最小生成樹，即： 在 e 條帶權(quán)的邊中選取 n1 條邊（不構(gòu)成回路），使“ 權(quán)值之和 ”為最小 。 算法從 U ＝{u0}(u0∈ V)， TE={ }開始 ， 重復(fù)執(zhí)行下述操作：在所有 u∈ V， v∈ VU的邊 (u,v)∈ E中找一條 代價(jià)最小 的邊 （ u0， v0） 并入集合 TE,同時(shí) v0并入 U， 直至 U=V為止 。 普里姆算法的基本思想 : 在生成樹的構(gòu)造過程中，圖中 n 個(gè)頂點(diǎn)分屬兩個(gè)集合： 已落在生成樹上的頂點(diǎn)集 U 和尚未落在生成樹上的頂點(diǎn)集VU ，則應(yīng) 在所有連通 U中頂點(diǎn)和 VU中頂點(diǎn)的邊中選取權(quán)值最小的邊 。 // U集中的頂點(diǎn) VRType lowcost。 adjvex lowcost a b c d e g f 19 5 14 18 27 16 8 21 3 12 7 cl o s ed 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