圖的遍歷

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

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

也可以看： 點(diǎn)這里

1.用 h 數(shù)組保存各個節(jié)點(diǎn)能到的第一個節(jié)點(diǎn)的編號。開始時，h[i] 全部為 -1。

2.用 e 數(shù)組保存節(jié)點(diǎn)編號，ne 數(shù)組保存 e 數(shù)組對應(yīng)位置的下一個節(jié)點(diǎn)所在的索引。

3.用 idx 保存下一個 e 數(shù)組中，可以放入節(jié)點(diǎn)位置的索引

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

模板如下：

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

圖的深度優(yōu)先遍歷（DFS, depth first search）

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

深度優(yōu)先遍歷的步驟

1. 訪問頂點(diǎn)V
2. 依次從頂點(diǎn)V的未被訪問的鄰節(jié)點(diǎn)出發(fā)，進(jìn)行深度優(yōu)先搜索，直至和V有路徑相通的頂點(diǎn)都被訪問到。
3. 對于連通圖進(jìn)行遍歷時，從一個頂點(diǎn)出發(fā)即可訪問圖中所有的頂點(diǎn)。
4. 對于非連通圖進(jìn)行遍歷時，若圖中尚有頂點(diǎn)未被訪問，則另選一未曾訪問的頂點(diǎn)作為起始點(diǎn)，進(jìn)行深度優(yōu)先搜索，直至所有頂點(diǎn)都被訪問

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

圖的寬度優(yōu)先遍歷（BFS, breadth first search）

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

從頂點(diǎn)V出發(fā)廣度優(yōu)先搜索的步驟

1. 訪問頂點(diǎn)V
2. 依次訪問頂點(diǎn)V的各個未被訪問的臨接點(diǎn)（橫向訪問）
3. 從V的這些鄰接點(diǎn)出發(fā)依次訪問他們的鄰接點(diǎn)，致使“先被訪問的頂點(diǎn)的鄰接點(diǎn)先于"后訪問的頂點(diǎn)的鄰接點(diǎn)"被訪問(一般可以借助隊列實(shí)現(xiàn)），直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)均被訪問。
4. 對于非連通圖進(jìn)行遍歷時，若圖中尚有頂點(diǎn)未被訪問，則另選一未曾訪問的頂點(diǎn)作為起始點(diǎn)，進(jìn)行廣度優(yōu)先搜索，直至所有頂點(diǎn)都被訪問

模板及注釋

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

寬度優(yōu)先搜索BFS的應(yīng)用

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

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

2.P2P網(wǎng)絡(luò)中查找臨近的結(jié)點(diǎn)，應(yīng)用場景如P2P文件下載，P2P語音視頻通信。

3.搜索引擎的網(wǎng)絡(luò)爬蟲的主要算法之一，DFS也是。

4.社交網(wǎng)絡(luò)網(wǎng)站，在社交網(wǎng)絡(luò)中可以搜索k層級以內(nèi)查找一個人。

5.GPS導(dǎo)航系統(tǒng)，使用BFS查找附近地點(diǎn)等。

6.網(wǎng)絡(luò)廣播，在網(wǎng)絡(luò)中使用BFS將廣播包發(fā)送給每個節(jié)點(diǎn)。 垃圾回收算法，例如Cheney算法。

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

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

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

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

深度優(yōu)先遍歷DFS的應(yīng)用

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

1.無權(quán)圖中求最短路徑和最小生成樹。

2.檢測環(huán)或圈。

3.路徑查找，使用DFS查找u到v的一條路徑，使用棧stack作為輔助，使用遞歸算法遇到目標(biāo)頂點(diǎn)v則入棧，后面陸續(xù)入棧，打印內(nèi)容即為所求路徑。

4.拓?fù)渑判颍河嬎銠C(jī)中根據(jù)作業(yè)之間的關(guān)系來調(diào)度作業(yè)（或根據(jù)一定先后順序優(yōu)先級等）；計算機(jī)中的指令調(diào)度（先后順序）；重新計算公式值公式單元的計算順序；邏輯合成；makefile編譯任務(wù)的執(zhí)行順序；數(shù)據(jù)序列化；編譯器中的鏈接器中解決符號依賴關(guān)系。

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

6.查找有向圖的強(qiáng)連通分量，后面會詳細(xì)討論其實(shí)現(xiàn)算法。

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

到此這篇關(guān)于C++詳細(xì)講解圖的遍歷的文章就介紹到這了,更多相關(guān)C++圖的遍歷內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！