本文主要內容為：圖的定義以及基本術語
- 圖的定義
- 圖
圖G的組成：由 資料元素的集合E 和 資料間的關系集合E 組成，記作：G = <V, E>
頂點 (vertex)：資料元素，V就是頂點的有窮非空集合
邊 (edge): 頂點的序偶對，例如 (v1, v2)，E就是邊的集合
-
- 子圖
定義：設 G=<V, E> 是一個圖，E' 是 E 的子集，V' 是 V 的子集，且 E' 中的邊權 僅與 V' 中的頂點相關聯，
則 G' = <V', E'> 稱為 圖G 的子圖
特殊的子圖：空圖，只有一個頂點，圖G本身
-
- 無向圖
定義：代表一條邊的頂點的序偶是無序的（即該邊無方向）
表示：無序的序偶對用圓括號表示，例如 (v1, v2) 和 (v2, v1) 是代表同一條邊
-
- 有向圖
定義：代表一條邊的頂點的序偶是有序的（即該邊有方向）
表示：有序的序偶對用尖括號表示，例如 <v1, v2> 和 <v2, v1> 是代表不同的邊
弧：有向圖的邊的別稱
弧尾 / 始點：邊的起點，例如 <v1, v2> 中的 v1
弧頭 / 終點：邊的終點，例如 <v1, v2> 中的 v2
-
- 帶權圖
定義：圖的每條邊邊或弧都附帶權(weight)
權的作用：可以用于表示從一個頂點到另一個頂點的距離，費用，代價等等
-
- 稀疏圖：邊比較少的圖
- 稠密圖：邊比較多的圖
- 完全圖：任何兩個頂點間都有邊相關聯的圖
- 圖的基本術語
- 無向圖頂點 v 的度：與該頂點相關的邊的數目，記作 D(v)
- 有向圖頂點 v 的入度：以頂點 v 為終點的弧的數目，記作 ID(v)
- 有向圖頂點 v 的出度：以頂點 v 為起點的弧的數目， 記作 OD(v)
- 終端頂點 / 葉子：出度為 0 的頂點
-
- 路徑：從一個頂點到另一個頂點，中間允許經過其他頂點，有向圖的路徑也是有向的
- 路徑長度：路徑上的 邊 或 弧 * 權重 之和
- 回路 / 環：路徑的起點和終點是同一個頂點的路徑
- 圖的根：從該頂點有路徑可以到達圖的其他所有頂點
-
- 連通圖：無向圖的任意兩個頂點有路徑
- 強連通圖：有向圖的任意兩個頂點之間有來回路徑
- 連通分量：無向圖中的極大連通子圖
- 強連通分量：有向圖強連通的極大子圖
- 網路：帶權的連通圖
- 圖的相關計算
n：表示圖中頂點的數目
e：表示圖中邊的數目
-
- 無向圖 e 的取值范圍：[0，n(n - 1) / 2]
- 有向圖 e 的取值范圍：[0, n(n - 1)]
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/231714.html
標籤：C++
上一篇：c++prime筆記八、 IO
下一篇：圖的代碼實作 (鄰接矩陣)