@[TOC]

圖算法

1、圖的表示

1.1、鄰接矩陣（有向圖、無向圖、帶權圖、代碼實現）

1、無向圖的鄰接矩陣

2、有向圖的鄰接矩陣

3、帶權值的圖

有了上述的理解，我們可以設計數據結構，并實現了。C++實現如下：

#include

1.2、 鄰接表

1、鄰接表的提出

2、無向圖的鄰接表

3、有向圖的鄰接表（分出邊表、入邊表）

4、帶權圖的處理

有了上面的鄰接表的理解，我們可以實現代碼(java)：

package

1.3、 十字鏈表與鄰接多重表

1、十字鏈表——解決有向圖鄰接表結構缺點

2、鄰接多重表——解決無向圖鄰接表結構，邊的刪除麻煩問題

1.4、邊集數組

2、圖的遍歷

2.1、DFS（深度優先搜索、遞歸算法）

基于鄰接矩陣的DFS

template

由于是鄰接矩陣存儲結構，算法時間復雜度O(n^2^)

基于鄰接表的DFS

template

鄰接表使得算法復雜度為O(n+e),n為頂點個數，e為邊數。

2.2、BFS（寬度優先搜索、優先隊列）

對邊搜索、不斷延展。 鄰接矩陣的BFS

void

鄰接表的BFS

void

2.3、小結

3、尋找最小生成樹（兩個貪心算法）

實際問題：

3.1、Prim算法（分割法、貪心策略：尋找集合中的頂點所連接邊中最小權值邊）

貪心策略、算法分析：

template

3.2、 Kruskal算法（邊集數組、每次從剩余邊選擇最小權值邊）

圖解分析:

基于分析我們可以寫出代碼：

template

運行結果：

4、最短路徑問題

4.1、單源最短路徑問題（給定一個點，求到其余各個點的距離）

4.1.1、迪杰特斯拉（Dijkstra）算法（貪心算法）

很像prim算法，利用集合，尋找最短路徑。但是有區別。而且用途也不同。這是一個貪心算法。

基于理解上的算法實現 ：

template

未優化的算法復雜度很高

4.1.2、Floyd算法（動態規劃）

4.1.3、Bellman-Ford 算法

總結

以上是生活随笔為你收集整理的无向图的深度优先遍历非递归_图算法总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。