C++圖的遍歷實例分析

這篇文章主要介紹了C++圖的遍歷實例分析的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇C++圖的遍歷實例分析文章都會有所收獲，下面我們一起來看看吧。

圖的遍歷

要想遍歷圖，肯定要先儲存圖啊。

下面我們采用鄰接表來存圖

也可以看： 點這里

1.用 h 數組保存各個節點能到的第一個節點的編號。開始時，h[i] 全部為 -1。

2.用 e 數組保存節點編號，ne 數組保存 e 數組對應位置的下一個節點所在的索引。

3.用 idx 保存下一個 e 數組中，可以放入節點位置的索引

4.插入邊使用的頭插法，例如插入：a->b。首先把b節點存入e數組，e[idx] = b。然后 b 節點的后繼是h[a]，ne[idx] = h[a]。最后，a 的后繼更新為 b 節點的編號，h[a] = idx，索引指向下一個可以存儲節點的位置，idx ++ 。

模板如下：

//鄰接表
const int N = 100010, M = N * 2;
//無向圖n條邊時，最多2n個idx，因為每條邊在鄰接表中會出現兩次
int h[N], e[M], ne[M], idx;
//n個鏈表頭，e每一個結點的值，ne每一個結點的next指針
void add(int a, int b)//a->b
{//e記錄當前點的值(地址->值),ne下一點的地址(地址->地址)，h記錄指向的第一個點的地址(值->地址)
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}//頭插法
// 初始化
idx = 0;
memset(h, -1, sizeof h);

圖的深度優先遍歷（DFS, depth first search）

方法：深度優先搜索的遍歷順序為一條路徑走到底然后回溯再走下一條路徑這種遍歷方法很省內存但是不能一次性給出最短路徑或者最優解。 

深度優先遍歷的步驟

1. 訪問頂點V

2. 依次從頂點V的未被訪問的鄰節點出發，進行深度優先搜索，直至和V有路徑相通的頂點都被訪問到。

3. 對于連通圖進行遍歷時，從一個頂點出發即可訪問圖中所有的頂點。

4. 對于非連通圖進行遍歷時，若圖中尚有頂點未被訪問，則另選一未曾訪問的頂點作為起始點，進行深度優先搜索，直至所有頂點都被訪問

// 需要標記數組st[N],  遍歷節點的每個相鄰的點
void dfs(int u) {
    st[u] = true; // 標記一下，記錄為已經被搜索過了，下面進行搜索過程
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
//因為每個節點的編號都是不一樣的，所以 用編號為下標 來標記是否被訪問過
        if (!st[j]) {
            dfs(j);
        }
    }
}

圖的寬度優先遍歷（BFS, breadth first search）

方法：從圖的某一結點出發，首先依次訪問該結點的所有鄰接頂點（再按這些頂點被訪問的先后次序依次訪問與它們相鄰接的所有未被訪問的頂點，重復此過程，直至所有頂點均被訪問為止。

從頂點V出發廣度優先搜索的步驟

1. 訪問頂點V

2. 依次訪問頂點V的各個未被訪問的臨接點（橫向訪問）

3. 從V的這些鄰接點出發依次訪問他們的鄰接點，致使“先被訪問的頂點的鄰接點先于"后訪問的頂點的鄰接點"被訪問(一般可以借助隊列實現），直至圖中所有已被訪問的頂點的鄰接點均被訪問。

4. 對于非連通圖進行遍歷時，若圖中尚有頂點未被訪問，則另選一未曾訪問的頂點作為起始點，進行廣度優先搜索，直至所有頂點都被訪問

模板及注釋

queue<int> q;//借助隊列實現
st[1] = true; // 表示1號點已經被遍歷過
q.push(1);//1號節點入隊列
while (q.size())//對列非空，就一直往后搜索
{
    int t = q.front();//隊頭出隊，找該點能到的點
    q.pop();//遍歷完就出隊列
    for (int i = h[t]; i != -1; i = ne[i])//遍歷所有t節點能到的點，i為節點索引
    {
        int j = e[i];//通過索引i得到t能到的節點編號
        if (!st[j])//如果沒有遍歷過
        {
            st[j] = true; // 表示點j已經被遍歷過
            q.push(j);//節點入隊
        }
    }
}

寬度優先搜索BFS的應用

圖論算法中大量使用了BFS或類似的算法，其常見的應用如下：

1.求最短路徑路徑和最小生成樹，兩個頂點的最短路徑是指兩個頂點間含有最少頂點的路徑，另外最小生成樹也可以使用DFS。

2.P2P網絡中查找臨近的結點，應用場景如P2P文件下載，P2P語音視頻通信。

3.搜索引擎的網絡爬蟲的主要算法之一，DFS也是。

4.社交網絡網站，在社交網絡中可以搜索k層級以內查找一個人。

5.GPS導航系統，使用BFS查找附近地點等。

6.網絡廣播，在網絡中使用BFS將廣播包發送給每個節點。 垃圾回收算法，例如Cheney算法。

7.無向圖環或圈檢測，BFS和DFS都可以檢測無向圖的環或圈，有向圖環檢測只能使用DFS。

8.查找最大流，如下面會談到的Ford-Fulkerson算法。

9.檢測一個圖是否是一個二分圖，DFS和BFS都可以。

10.路徑查找，使用BFS和DFS檢測兩個頂點是否有一條路徑，查找一個頂點到所有可達到的頂點等等。

深度優先遍歷DFS的應用

DFS和BFS是圖論算法的主要算法，其應用非常多，下面是一些常見例子：

1.無權圖中求最短路徑和最小生成樹。

2.檢測環或圈。

3.路徑查找，使用DFS查找u到v的一條路徑，使用棧stack作為輔助，使用遞歸算法遇到目標頂點v則入棧，后面陸續入棧，打印內容即為所求路徑。

4.拓撲排序：計算機中根據作業之間的關系來調度作業（或根據一定先后順序優先級等）；計算機中的指令調度（先后順序）；重新計算公式值公式單元的計算順序；邏輯合成；makefile編譯任務的執行順序；數據序列化；編譯器中的鏈接器中解決符號依賴關系。

5.檢測一個圖是否是二分圖。

6.查找有向圖的強連通分量，后面會詳細討論其實現算法。

7.解決難題，如迷宮問題。

關于“C++圖的遍歷實例分析”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“C++圖的遍歷實例分析”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。