數(shù)據(jù)結(jié)構(gòu)c語(yǔ)言描述圖(參考版)
2025-08-04 15:06本頁(yè)面
【正文】 面對(duì)實(shí)際問(wèn)題時(shí)，學(xué)會(huì)引用本章的有關(guān)內(nèi)容。 相對(duì)而言之，圖這一章內(nèi)容較難，尤其是離散數(shù)學(xué)基礎(chǔ)較差的讀者，也許難度更大些。 最小生成樹(shù) (Minimun Spanning Tree)：權(quán)最小的生成樹(shù)稱為 G的最小生成樹(shù) 。 網(wǎng)絡(luò) (Network)：若將圖的每條邊都賦上一個(gè)權(quán) ， 則稱這種帶權(quán)圖為網(wǎng)絡(luò) 。 強(qiáng)連通圖 ：在有向圖 G中 ， 若對(duì)于 V(G)中任意兩個(gè)不同的頂點(diǎn) vi和 vj， 都存在從 vi到 vj以及從 vj到 vi的路徑 ， 則稱 G是強(qiáng)連通圖 。 連通圖 (Connected Graph)：若 V(G)中任意兩個(gè)不同的頂點(diǎn) vi和 vj都連通 (即有路徑 )， 則稱 G為連通圖 。 有根圖 ：在一個(gè)有向圖中 ， 若存在一個(gè)頂點(diǎn) v， 從該頂點(diǎn)有路徑可以到達(dá)圖中其它所有頂點(diǎn) ， 則稱此有向圖為有根圖 ， v稱作圖的根 。 簡(jiǎn)單路徑 ：若一條路徑上除了 vp和 vq可以相同外 ， 其余頂點(diǎn)均不相同 ， 則稱此路徑為一條簡(jiǎn)單路徑 。 路徑 (Path)：在無(wú)向圖 G中 ， 若存在一個(gè)頂點(diǎn)序列 vp,vi1,vi2… ， vin， vq， 使得 (vp， vil)，(vi1,vi2)， … ， (vin， vq)均屬于 E(G)， 則稱頂點(diǎn) vp到 vq存在一條路徑 。 出度 (outdegree)：把以頂點(diǎn) v為始點(diǎn)的邊的數(shù)目 ， 稱為 v的出度 ， 記為 OD(v)。 度 (Degree)：無(wú)向圖中頂點(diǎn) v的度是關(guān)聯(lián)于該頂點(diǎn)的邊的數(shù)目 。 有向完全圖 (Directed Complete Graph)：恰有 n(n1)條邊的有向圖稱為有向完全圖 。 無(wú)向圖 （ Undigraph） ： 若圖 G中的每條邊都是沒(méi)有方向的 ， 則稱 G為無(wú)向圖 。 E(G)可以是空集 ， 若 E(G)為空 ， 則圖 G只有頂點(diǎn)而沒(méi)有邊 ， 稱為空?qǐng)D 。 本章涉及到的基本概念有： 圖 ：由兩個(gè)集合 V和 E組成 ， 記為 G＝ (V， E)， 其中 v是頂點(diǎn)的有窮非空集合 ， E是 V中頂點(diǎn)偶對(duì) （ 稱為邊 ） 的有窮集 。判斷AOV網(wǎng)是否有有向環(huán)的方法是對(duì)該 AOV網(wǎng)進(jìn)行拓?fù)渑判?，?AOV網(wǎng)中頂點(diǎn)排列成一個(gè)線性有序序列，若該線性序列中包含 AOV網(wǎng)全部頂點(diǎn)，則 AOV網(wǎng)無(wú)環(huán)，否則， AOV網(wǎng)中存在有向環(huán)，該 AOV網(wǎng)所代表的工程是不可行的。對(duì)程序流程而言，將出現(xiàn)死循環(huán)。從前驅(qū)和后繼的傳遞性和反自反性來(lái)看， AOV網(wǎng)中不能出現(xiàn)有向回路（或稱有向環(huán)）。 在 AOV網(wǎng)中， i,j有向邊表示 i活動(dòng)應(yīng)先于 j活動(dòng)開(kāi)始，即i活動(dòng)必須完成后， j活動(dòng)才可以開(kāi)始，并稱 i為 j的直接前驅(qū)， j為 i的直接后繼。例如，計(jì)算機(jī)專業(yè)學(xué)生的課程開(kāi)設(shè)可看成是一個(gè)工程，每一門課程就是工程中的活動(dòng)，圖 724給出了若干門所開(kāi)設(shè)的課程，其中有些課程的開(kāi)設(shè)有先后關(guān)系，有些則沒(méi)有先后關(guān)系，有先后關(guān)系的課程必須按先后關(guān)系開(kāi)設(shè)，如開(kāi)設(shè)數(shù)據(jù)結(jié)構(gòu)課程之前必須先學(xué)完程序設(shè)計(jì)基礎(chǔ)及離散數(shù)學(xué)，而開(kāi)設(shè)離散數(shù)學(xué)則必須學(xué)完高等數(shù)學(xué)。具體做法為：第一步，讓所有邊上加入中間頂點(diǎn) 1，取A[i][j]與 A[i][1]+A[1][j]中較小的值作 A[i][j]的值，完成后得到 A(1)，第二步，讓所有邊上加入中間頂點(diǎn) 2，取A[i][j]與 A[i][2]+A[2][j]中較小的值，完成后得到 A(2)… ，如此進(jìn)行下去，當(dāng)?shù)?n步完成后，得到 A(n)， A(n)即為我們所求結(jié)果， A(n)[i][j]表示頂點(diǎn) i到頂點(diǎn) j的最短距離。 算法的基本思想是 :設(shè)置一個(gè) nxn的矩陣 A(k)， 其中除對(duì)角線的元素都等于 0外 ， 其他元素 a(k)[i][j]表示頂點(diǎn) i到頂點(diǎn) j的路徑長(zhǎng)度 ， K表示運(yùn)算步驟 。解決此問(wèn)題的一個(gè)有效方法是 :輪流以每一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行迪杰斯特拉算法 n次，即可求得每一對(duì)頂點(diǎn)之間的最短路徑 ,總的時(shí)間復(fù)雜度為 O(n3)。路徑上的開(kāi)始頂點(diǎn) (出發(fā)點(diǎn) )稱為源點(diǎn)，路徑上的最后一個(gè)頂點(diǎn)稱為終點(diǎn)，并假定討論的權(quán)值不能為負(fù)數(shù)。 求兩個(gè)頂點(diǎn)之間的最短路徑 ， 不是指路徑上邊數(shù)之和最少 ， 而是指路徑上各邊的權(quán)值之和最小 。 最短路徑 交通網(wǎng)絡(luò)中常常提出這樣的問(wèn)題：從甲地到乙地之間是否有公路連通 ?在有多條通路的情況下 ， 哪一條路最短 ? 交通網(wǎng)絡(luò)可用帶權(quán)圖來(lái)表示 。 顯然， Prim算法的關(guān)鍵是如何找到連接 U和 VU的最短邊來(lái)擴(kuò)充生成樹(shù) T。 此時(shí) ， 必有 U＝ V， TE中有 n1條邊 。 Prim算法的基本思想是：首先從 v中任取一個(gè)頂點(diǎn) u0， 將生成樹(shù) T置為僅有一個(gè)結(jié)點(diǎn) u0的樹(shù) ， 即置 U＝ {u0}；然后只要 U是 V的真子集 ， 就在所有那些其一個(gè)端點(diǎn) u己在 T(即 u∈ U)、 另一個(gè)端點(diǎn) v還未在 T(即 v∈ V— U)的邊中 ， 找一條最短 (即權(quán)最小 )的邊 (u， v)， 并把該條邊 (u， v)和其不在 T中的頂點(diǎn) v， 分別并入 T的邊集 TE和頂點(diǎn)集 U。 設(shè)所求的最小生成樹(shù)為 T＝ (U，TE)， 其中 U是 T的頂點(diǎn)集 ， TE是 T的邊集 。刪去邊 (u′，v′)，上述回路即被消除，由此得到另一棵生成樹(shù) T′， T′和 T的區(qū)別僅在于用邊 (u， v)取代了 T中的邊 (u′， v′)。由于 T是樹(shù)，且是連通的，因此有一條從 u到 v的路徑；且該路徑上必有一條連接兩個(gè)頂點(diǎn)集 U和 VU的邊 (u′， v′)，其中 u′∈ U，v′∈ VU，否則 u和 v不連通。 MST性質(zhì)可用反證法證明：假設(shè) G的任何一棵最小生成樹(shù)中都不含邊 (u， v)。若 (u，
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1