圖論-基本概念及算法介紹

(1)、圖的定義：

圖由V(G) 和E(G) 組成，記為G=(V,E)

(2)、圖的分類

連通圖

 任意兩個頂點都互相可以到達的無向圖

強連通圖

 任意兩個頂點間都是互相可以到達的有向圖

非連通圖

 至少兩個頂點間是互相不可到達的圖

完全圖

 圖中n 個頂點與其它n-1個頂點之間都有邊

(3)、圖的兩種存儲結構

 (a)、鄰接表

 (b)、鄰接矩陣

 鄰接矩陣(Adjacency Matrix)

 無向圖的鄰接矩陣必定對稱

 無向圖的鄰接矩陣第i行或列的非0元素個數正好是第i個頂點的度數。

 有向圖的第i行非0元素正好是第i 個頂點的出度，第i 列非0元素正好是第i 個頂點的入度

 鄰接表(Adjacency List)

 每個頂點建立一個帶表頭結點的的單連結清單

 第i個單連結清單中的結點表示依附頂點vi的邊的另外一頂點

 n個單連結清單的表頭結點以順序結構存儲

 圖的鄰接表不唯一，但圖的鄰接矩陣必定唯一

(4)、圖的操作

 無向圖和有向圖的周遊

 深度優先搜尋，和廣度優先搜尋

(5)、生成樹算法

 取圖G的全部頂點集合V 及部分邊集構成的子圖，如果子圖邊既将圖中所有

 的頂點連通，又不形成回路，則這個子圖就是G的一顆生成樹

 生成樹特性：

 生成樹是邊數最少的連通圖

 生成樹中恰好有(n-1) 條邊

 生成樹不唯一。可分深度優先生成樹和廣度優先生成樹

(6)、最小生成樹(MST)

 實際應用，在n個城市中合理設定n-1條通信線路，使通信線路網總造價最低

 最小生成樹算法

無權圖最小生成樹算法：深度周遊

有權圖最小生成樹算法： Prim算法，Kruskal 算法