數(shù)據(jù)結(jié)構(gòu)c語言描述圖-資料下載頁
2025-08-01 15:06本頁面
【正文】 活動完成時，整個工程也就完成了。例如，計算機專業(yè)學生的課程開設可看成是一個工程，每一門課程就是工程中的活動，圖 724給出了若干門所開設的課程，其中有些課程的開設有先后關(guān)系，有些則沒有先后關(guān)系，有先后關(guān)系的課程必須按先后關(guān)系開設，如開設數(shù)據(jù)結(jié)構(gòu)課程之前必須先學完程序設計基礎(chǔ)及離散數(shù)學，而開設離散數(shù)學則必須學完高等數(shù)學。在圖 724（ b）中，我們用一種有向圖來表示課程開設，在這種有向圖中，頂點表示活動，有向邊表示活動的優(yōu)先關(guān)系，這有向圖叫做頂點表示活動的網(wǎng)絡 (Active On Vertices)簡稱為AOV網(wǎng)。 在 AOV網(wǎng)中， i,j有向邊表示 i活動應先于 j活動開始，即i活動必須完成后， j活動才可以開始，并稱 i為 j的直接前驅(qū)， j為 i的直接后繼。這種前驅(qū)與后繼的關(guān)系有傳遞性，此外，任何活動 i不能以它自己作為自己的前驅(qū)或后繼，這叫做反自反性。從前驅(qū)和后繼的傳遞性和反自反性來看， AOV網(wǎng)中不能出現(xiàn)有向回路（或稱有向環(huán)）。在 AOV網(wǎng)中如果出現(xiàn)了有向環(huán)，則意味著某項活動應以自己作為先決條件，這是不對的，工程將無法進行。對程序流程而言，將出現(xiàn)死循環(huán)。因此，對給定的 AOV網(wǎng)，應先判斷它是否存在有向環(huán)。判斷AOV網(wǎng)是否有有向環(huán)的方法是對該 AOV網(wǎng)進行拓撲排序，將 AOV網(wǎng)中頂點排列成一個線性有序序列，若該線性序列中包含 AOV網(wǎng)全部頂點，則 AOV網(wǎng)無環(huán)，否則， AOV網(wǎng)中存在有向環(huán)，該 AOV網(wǎng)所代表的工程是不可行的。 本章小結(jié) 圖是一種復雜的非線性結(jié)構(gòu) ， 具有廣泛的應用背景 。 本章涉及到的基本概念有： 圖 ：由兩個集合 V和 E組成 ， 記為 G＝ (V， E)， 其中 v是頂點的有窮非空集合 ， E是 V中頂點偶對 （ 稱為邊 ） 的有窮集 。 通常 ， 也將圖 G的頂點集和邊集分別記為 V(G)和E(G)。 E(G)可以是空集 ， 若 E(G)為空 ， 則圖 G只有頂點而沒有邊 ， 稱為空圖 。 有向圖 （ Digraph） ：若圖 G中的每條邊都是有方向的 ， 則稱 G為有向圖 。 無向圖 （ Undigraph） ： 若圖 G中的每條邊都是沒有方向的 ， 則稱 G為無向圖 。 無向完全圖 (Undirected Complete Graph)： 恰好有 n(n1)／ 2條邊的無向圖稱為無向完全圖 。 有向完全圖 (Directed Complete Graph)：恰有 n(n1)條邊的有向圖稱為有向完全圖 。 鄰接點 (Adjacent)：若 (vi， vj)是一條無向邊 ， 則稱頂點 vi和 vj互為鄰接點 。 度 (Degree)：無向圖中頂點 v的度是關(guān)聯(lián)于該頂點的邊的數(shù)目 。 人度 (1ndegree)若 G為有向圖 ， 則把以頂點 v為終點的邊的數(shù)目 ， 稱為 v的人度 ， 記為ID(v)。 出度 (outdegree)：把以頂點 v為始點的邊的數(shù)目 ， 稱為 v的出度 ， 記為 OD(v)。 子圖 (Subgraph)：設 G＝ (V， E)是一個圖，若 v′ 是 v的子集， E′ 是 E的子集，且 E′中的邊所關(guān)聯(lián)的頂點均在 v′ 中，則 G′ ＝ (V′ ， E′ )也是一個圖，并稱其為 G的子圖。 路徑 (Path)：在無向圖 G中 ， 若存在一個頂點序列 vp,vi1,vi2… ， vin， vq， 使得 (vp， vil)，(vi1,vi2)， … ， (vin， vq)均屬于 E(G)， 則稱頂點 vp到 vq存在一條路徑 。 路徑長度 ：該路徑上邊的數(shù)目 。 簡單路徑 ：若一條路徑上除了 vp和 vq可以相同外 ， 其余頂點均不相同 ， 則稱此路徑為一條簡單路徑 。 簡單回路或簡單環(huán) (Cycle)：起點和終點相同 (vp＝ vq)的簡單路徑稱為簡單回路或簡單環(huán) 。 有根圖 ：在一個有向圖中 ， 若存在一個頂點 v， 從該頂點有路徑可以到達圖中其它所有頂點 ， 則稱此有向圖為有根圖 ， v稱作圖的根 。 連通 ：在無向圖 G中 ， 若從頂點 vi到頂點 vj有路徑 (當然從 vj到 vi也一定有路徑 )， 則稱 vi和 vj是連通的 。 連通圖 (Connected Graph)：若 V(G)中任意兩個不同的頂點 vi和 vj都連通 (即有路徑 )， 則稱 G為連通圖 。 連通分量 (connected Component)：無向圖 G的極大連通子圖稱為 G的連通分量 。 強連通圖 ：在有向圖 G中 ， 若對于 V(G)中任意兩個不同的頂點 vi和 vj， 都存在從 vi到 vj以及從 vj到 vi的路徑 ， 則稱 G是強連通圖 。 強連通分量 ：有向圖 G的極大強連通子圖稱為 G的強連通分量 。 網(wǎng)絡 (Network)：若將圖的每條邊都賦上一個權(quán) ， 則稱這種帶權(quán)圖為網(wǎng)絡 。 生成樹 (Spanning Tree)：連通圖 G的一個子圖如果是一棵包含 G的所有頂點的樹 ， 則該子圖稱為 G的生成樹 。 最小生成樹 (Minimun Spanning Tree)：權(quán)最小的生成樹稱為 G的最小生成樹 。 本章在介紹圖的基本概念的基礎(chǔ)上 ， 還介紹了圖的兩種常用的存儲結(jié)構(gòu) ， 對圖的遍歷 、 最小生成樹等問題做了較詳細的討論 ， 給出了相應的求解算法 ， 有的算法采用自頂向下 、 逐步求精的方法加以介紹 ， 也許能便于讀者理解它們 。 相對而言之，圖這一章內(nèi)容較難，尤其是離散數(shù)學基礎(chǔ)較差的讀者，也許難度更大些。建議讀者知難而進，理解本章所介紹的算法實質(zhì)，掌握圖的有關(guān)術(shù)語和存儲表示。面對實際問題時，學會引用本章的有關(guān)內(nèi)容。
教學課件相關(guān)推薦
鄂ICP備17016276號-1