數據結構09圖

第七章圖 Graph

?

7.1 圖的定義和術語

頂點 Vertex?
V 是頂點的有窮非空集合，頂點數 |V| = n
VR 兩個頂點之間關系的集合，邊數 |VR| = e

有向圖 Digraph
<v, w> Arc
v Tail / Inital node
w Head / Terminal node

無向圖 Undigraph
<v, w> 必有 <w, v> Edge

完全圖（Completed graph）：有 n(n-1)/2 條邊的無向圖
有向完全圖：有 n(n-1) 條弧的有向圖
稀疏圖（Sparse graph）：很少邊或弧，如 e < nlogn
稠密圖（Dense graph）
權（Weight）：邊或弧的相關數
子圖（Subgraph）： $V'\subseteq V and\ E'\subseteq E$
鄰接點（Adjacent）： $(v, v')\in E$ ，則稱頂點 v 和 v' 互為鄰接點
? $Arc\ <v, v'> \in A$ ，則稱頂點v鄰接到頂點v'，頂點v'鄰接自頂點v
依附（Incident）：邊 $(v, v')$ 依附于頂點 v 和 v'，或者說相關聯。
度（Degree）：頂點v相關聯的邊數，記為 $TD(V)$
入度（InDegree）：以頂點v為頭的弧數， $ID(v)$
出度（OutDegree）：以頂點v為尾的弧數， $OD(v)$
$TD(v)=ID(v)+OD(v)$
$e=\frac{1}{2}\sum_{i=1}^{n}TD(v_{i})$

路徑（Path）：從頂點 v 到 v' 的一個頂點序列
環（Cycle）：第一個頂點和最后一個頂點相同的路徑
簡單路徑：序列中頂點不重復出現的路
簡單回路 / 簡單環：除第一個頂點和最后一個頂點之外，其余頂點不重復出現的回路

連通：在無向圖G中，如果頂點v 到頂點v' 有路徑，則稱v 和 v' 連通
連通圖（Connected Graph）：無向圖中，任意兩個頂點有路徑
連通分量（Connected Component）：無向圖中的極大連通子圖
強連通圖：有向圖G中，任意兩個頂點之間有路徑
強連通分量：有向圖中，極大強連通子圖

生成樹：連通圖的一個極小連通子圖，包含全部頂點，n-1條邊
如果一個圖有n個頂點，小于n-1條邊，則是非連通圖。
如果大于n-1條邊，一定有環。
有n-1條邊的圖不一定是生成樹。

如果一個有向圖恰有一個頂點入度為0，其余頂點入度均為1，則是一棵有向樹。
生成森林：一個有向圖的生成森林，由若干棵有向樹組成，含圖中全部頂點，最少條邊。

圖中的頂點不存在全序關系，即無法排成一個線性序列。
任何一個頂點都可以被看成是第一個頂點；任一頂點的鄰接點之間也不存在次序關系。

7.2 圖的存儲結構

鄰接矩陣、鄰接表、鄰接多重表、十字鏈表

7.2.1?鄰接矩陣

7.2.2 鄰接表

總在表頭插入結點，所以鄰接表的存儲結構還與弧的輸入順序有關。

圖的鄰接表存儲結構適合存儲弧相對較少的稀疏圖。

7.3 圖的遍歷

對圖的搜索就是對圖中頂點的遍歷。

為了不重復訪問頂點，需要為頂點向量設立一個訪問標志數組visit[]，并將初值置為FALSE，即未被訪問。
遍歷時，在訪問后，將標志的值改為TRUE。

兩種搜索原則：

深度優先搜索；
廣度優先搜索。

7.3.1 深度優先搜索

7.3.2 廣度優先搜索

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/387028.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/387028.shtml
英文地址，請注明出處：http://en.pswp.cn/news/387028.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！