圖的定義和術(shù)語及存儲(chǔ)結(jié)構(gòu)-在線瀏覽
2024-09-04 03:44本頁面
【正文】 點(diǎn)都有一條弧指向其它 n1個(gè)頂點(diǎn) , 因此總邊數(shù) =n(n1) 1 2 3 4 6 證明： 從①可以直接推論出無向完全圖的邊數(shù) ——因?yàn)闊o方向，兩弧合并為一邊，所以邊數(shù)減半，總邊數(shù)為 n(n1)/2。 1 2 3 4 例：判斷下列 4種圖形各屬什么類型？ 7 稀疏圖： 稠密圖： 設(shè)有兩個(gè)圖 G＝ (V, E) 和 G’＝ (V’, E’)。 子 圖： 邊較少的圖。 無向圖中，邊數(shù)接近 n(n1)/2 有向圖中，邊數(shù)接近 n(n1) B B C A B E C F A B E C F 例如： 8 A B E C F 15 9 7 21 11 3 2 有向網(wǎng) 或 無向網(wǎng) 是弧或邊帶權(quán)的圖 。 邊 (v,w) 依附 于頂點(diǎn) v 和 w，或者與頂點(diǎn) v,w相關(guān)聯(lián) 。記為 OD(v). 頂點(diǎn) v的入度 : 以頂點(diǎn) v 為頭的弧的數(shù)目 ,記為 ID(v). 頂點(diǎn)的度 (TD)=出度 (OD)+入度 (ID) 問：當(dāng)有向圖中僅 1個(gè)頂點(diǎn)的入度為 0,其余頂點(diǎn)的入度均為 1，此時(shí)是何形狀？ 答：是樹！而且是一棵有向樹！ 9 路徑 :設(shè)圖 G=(V,VR)中的一個(gè)頂點(diǎn)序列 : v=vi,0 ,vi,1 , … , vi,m=w 中， (vi,j1 ,vi,j)（或〈 vi,j1,vi,j〉 ） ?VR 1≤j≤m, 則稱從頂點(diǎn) v 到頂點(diǎn) w 之間存在一條路徑。 A B E C F 如 :從 A到 F長度為 3 的路徑{A,B,C,F}或 {A， E， C， F} 簡單路徑 :指序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。 10 連通圖： 無向 圖 G中任意兩個(gè)頂點(diǎn)之間都有路徑相連通。 B A C D F E B A C D F E 強(qiáng)連通圖： 在有向圖中 , 每一對(duì)頂點(diǎn) vi和 vj, 都存在一條從 vi到 vj和從 vj到vi的路徑 強(qiáng)連通分量： 非強(qiáng)連通圖中的極大強(qiáng)連通子圖。 由若干棵 生成樹 組成，含全部頂點(diǎn)，但構(gòu)成這些樹的邊是最少的。G, V, VR)//按定義 (V,VR)構(gòu)造圖 DestroyGraph(amp。 GetVex(G, v) // 返回 v 的值。G, v, value) // 對(duì) v 賦值 value。 //返回 v的“第一個(gè)鄰接點(diǎn)” 若該頂點(diǎn)在 G中沒有鄰接點(diǎn)，則返回 “ 空 ” 。 //返回 v的（相對(duì)于 w的） “下一個(gè)鄰接點(diǎn) ” 。 插入或刪除頂點(diǎn) InsertVex(amp。 //在圖 G中增添新頂點(diǎn) v。G, v)； //刪除 G中頂點(diǎn) v及其相關(guān)的弧。G, v, w)。 DeleteArc(amp。 //在 G中刪除弧 v,w，若 G是無向的，則還刪除對(duì)稱弧 w,v。 //從頂點(diǎn) v起深度優(yōu)先遍歷圖 G，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù) Visit一次且僅一次。 //從頂點(diǎn) v起廣度優(yōu)先遍歷圖 G，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù) Visit一次且僅一次。 非線性結(jié)構(gòu) （ m :n） 鄰接矩陣 ?鄰接表 ?十字鏈表 ?鄰接多重表 各種表示法成立的原則：存入電腦后能唯一復(fù)原 16 ① 建立一個(gè) 頂點(diǎn)表 和一個(gè) 鄰接矩陣 。 例 1： 鄰接矩陣： = （ v1 v2 v3 v4 v5 ） v1 v2 v3 v4 v5 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 頂點(diǎn)表： 無向圖的鄰接矩陣如何表示？ v1 v2 v3 v5 v4 A 18 例 2 ：有向圖的鄰接矩陣如何表示？ 分析 1： 有向圖的鄰接矩陣可能是不對(duì)稱的。 頂點(diǎn) vi的入度 =第 i列元素之和 。 v1 v2 v3 v4 A 鄰接矩陣：
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1