C++詳細講解圖的遍歷

2022-05-30 18:03:22

圖的遍歷

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

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

也可以看：點這裡

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）

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

深度優先遍歷的步驟

存取頂點V
依次從頂點V的未被存取的鄰節點出發，進行深度優先搜尋，直至和V有路徑相通的頂點都被存取到。
對於連通圖進行遍歷時，從一個頂點出發即可存取圖中所有的頂點。
對於非連通圖進行遍歷時，若圖中尚有頂點未被存取，則另選一未曾存取的頂點作為起始點，進行深度優先搜尋，直至所有頂點都被存取

// 需要標記陣列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出發廣度優先搜尋的步驟

存取頂點V
依次存取頂點V的各個未被存取的臨接點（橫向存取）
從V的這些鄰接點出發依次存取他們的鄰接點，致使“先被存取的頂點的鄰接點先於"後存取的頂點的鄰接點"被存取(一般可以藉助佇列實現），直至圖中所有已被存取的頂點的鄰接點均被存取。
對於非連通圖進行遍歷時，若圖中尚有頂點未被存取，則另選一未曾存取的頂點作為起始點，進行廣度優先搜尋，直至所有頂點都被存取

模板及註釋

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++圖的遍歷內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！