數(shù)據(jù)結(jié)構(gòu)（c語言描述）圖-預(yù)覽頁
【正文】 的入度和出度之和，即 D(v)＝ ID(v)十 OD(v)。若一條路徑上除了 vp和 vq可以相同外；其余頂點均不相同，則稱此路徑為一條 簡單路徑 。 在一個有向圖中，若存在一個頂點 v，從該頂點有路徑可以到達圖中其它所有頂點，則稱此有向圖為 有根圖 ， v稱作圖的 根 。 無向圖 G的極大連通子圖稱為 G的 連通分量 (connected Component)。有向圖 G的極大強連通子圖稱為 G的 強連通分量 。通常權(quán)是具有某種意義的數(shù) . 它們可以表示兩個頂點之間的距離，耗費等 圖的存儲結(jié)構(gòu) ? 鄰接矩陣 (Adjacency Matrix)是表示頂點之間相鄰關(guān)系的矩陣 。 由于無向圖或無向網(wǎng)絡(luò)的鄰接矩陣是對稱的 ， 故可采用壓縮存儲的方法 ， 僅存儲下三角陣 (不包括對角線上的元素 )中的元素即可 。j， amp。 對于圖 G中的每個頂點 vi，該方法把所有鄰接于 vi的頂點 vj鏈成一個單鏈表，這個單鏈表就稱為頂點 vi的鄰接表 (Adjacency List)。 建立有向圖的鄰接表與此類似，只是更加簡單，每讀入一個頂點對序號＜ i， j＞時，僅需生成十個鄰接點序號為 j的邊表結(jié)點，將其插入到 vi的出邊表頭部即可。下面從空間及執(zhí)行某些常用操作的時間這兩方面來作一比較。若圖中邊的數(shù)目遠遠小于 n2(即 e＜＜ n2)，此類圖稱作稀疏圖 (Sparse Graph)，這時用鄰接表表示比用鄰接矩陣表示節(jié)省存儲空間；若 e接近于 n2 (準確地說，無向圖 e接近于 n(n1)／ 2，有向圖 e接近于 n(n1))，此類圖稱作稠密圖 (Dense Graph)，考慮到鄰接表中要附加鏈域，則應(yīng)取鄰接矩陣表示法為宜。 若有向圖采用逆鄰接表表示 ， 則與鄰接表表示相反 ， 求頂點的入度容易 ，而求頂點出度較難 。 圖的遍歷 和樹的遍歷類似，圖的遍歷也是從某個頂點出發(fā)，沿著某條搜索路徑對圖中所有頂點各作一次訪問。為此，可設(shè)置一個布爾向量 visited[n]，它的初值為 false，一旦訪問了頂點 vi，便將 visited[i1]置為 TRUE。例如，設(shè) x是剛訪問過的頂點，按深度優(yōu)先搜索方法，下一步將選擇一條從 x出發(fā)的未檢測過的邊(x， y)。此時，若 x不是初始出發(fā)點，則回溯到在 x之前被訪問過的頂點；若 x是初始出發(fā)點，則整個搜索過程結(jié)束。執(zhí)行DFS(1)，首先訪問 v2，將其標記為已訪問過，然后從 v2搜索到的第 1個鄰接點是 vl，但 vl已訪問過，故繼續(xù)搜索到第 2個鄰接點 v4，v4未曾訪過，因此調(diào)用 DFS(3)。類似地由 v4回溯到 v2。此時， vl的所有鄰接點都已搜索過，故 DFS(0)執(zhí)行完畢。 顯然，上述搜索法的特點是盡可能先對橫向進行搜索，故稱之為寬度優(yōu)先搜索。 最小生成樹 圖的生成樹不是唯一的 ， 從不同的頂點出發(fā)進行遍歷 ，可以得到不同的生成樹 。令圖 G的頂點表示城市，邊表示連接兩個城市之間的通訊線路。構(gòu)造最小生成樹可以有多種算法，其中大多數(shù)構(gòu)造算法都是利用了最小生成樹的下述性質(zhì)：設(shè) G＝ (V， E)是一個連通網(wǎng)絡(luò)， U是頂點集 V的一個真子集。設(shè) T是 G的一棵最小生成樹，但不包含邊 (u， v)。因為 (u， v)的權(quán)＜ (u′， v′)的權(quán)，故 T′的權(quán)＜ T的權(quán)，因此 T′也是 G的最小生成樹，它包含邊 (u， v)，與假設(shè)矛盾 ! 假設(shè) G＝ (V， E)是連通網(wǎng)絡(luò) ， 為簡單起見 ， 我們用序號 1至 n來表示頂點集合 ， 即 v＝ {1， 2， … ， n}。 如此進行下去 ， 每次往生成樹里并入一個頂點和一條邊 ，直到把所有頂點都包括進生成樹 T為止 。為直觀解釋方便，設(shè)想在構(gòu)造過程中， T的頂點集 U中頂點和邊集 TE中的邊均被涂成紅色， U之外的頂點集 VU中的頂點均被涂成藍色，連接紅點和藍點的邊均被涂成紫色，那么．最短紫邊就是連接 U和 VU的最短邊。 另外，若兩個頂點之間沒有邊，則認為兩個頂點無通路，但有可能有間接通路（從其他頂點達到 )）。 弗洛伊德算法仍然使用前面定義的圖的鄰接矩陣cost[n+1][n+1]來存儲帶權(quán)有向圖 。 拓撲排序 通常我們把計劃、施工過程、生產(chǎn)流程、程序流程等都當成一個工程，一個大的工程常常被劃分成許多較小的子工程，這些子工程稱為活動，這些活動完成時，整個工程也就完成了。這種前驅(qū)與后繼的關(guān)系有傳遞性，此外，任何活動 i不能以它自己作為自己的前驅(qū)或后繼，這叫做反自反性。因此，對給定的 AOV網(wǎng)，應(yīng)先判斷它是否存在有向環(huán)。 通常 ， 也將圖 G的頂點集和邊集分別記為 V(G)和E(G)。 無向完全圖 (Undirected Complete Graph)： 恰好有 n(n1)／ 2條邊的無向圖稱為無向完全圖 。 人度 (1ndegree)若 G為有向圖 ， 則把以頂點 v為終點的邊的數(shù)目 ， 稱為 v的人度 ， 記為ID(v)。 路徑長度 ：該路徑上邊的數(shù)目 。 連通 ：在無向圖 G中 ， 若從頂點 vi到頂點 vj有路徑 (當然從 vj到 vi也一定有路徑 )， 則稱 vi和 vj是連通的 。 強連通分量 ：有向圖 G的極大強連通子圖稱為 G的強連通分量 。 本章在介紹圖的基本概念的基礎(chǔ)上 ， 還介紹了圖的兩種常用的存儲結(jié)構(gòu) ， 對圖的遍歷 、 最小生成樹等問題做了較詳細的討論 ， 給出了相應(yīng)的求解算法 ， 有的算法采用自頂向下 、 逐步求精的方法加以介紹 ， 也許能便于讀者理解它們 。
教學課件相關(guān)推薦
鄂ICP備17016276號-1