快捷導(dǎo)航

C++詳細(xì)講解圖的遍歷

更新時(shí)間：2022年05月30日 11:08:24 作者：quicklsleap

圖的遍歷是指，從給定圖中任意指定的頂點(diǎn)（稱為初始點(diǎn)）出發(fā)，按照某種搜索方法沿著圖的邊訪問(wèn)圖中的所有頂點(diǎn)，使每個(gè)頂點(diǎn)僅被訪問(wèn)一次，這個(gè)過(guò)程稱為圖的遍歷

圖的遍歷

要想遍歷圖，肯定要先儲(chǔ)存圖啊。

下面我們采用鄰接表來(lái)存圖

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

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

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

3.用 idx 保存下一個(gè) 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ào)，h[a] = idx，索引指向下一個(gè)可以存儲(chǔ)節(jié)點(diǎn)的位置，idx ++ 。

模板如下：

//鄰接表
const int N = 100010, M = N * 2;
//無(wú)向圖n條邊時(shí)，最多2n個(gè)idx，因?yàn)槊織l邊在鄰接表中會(huì)出現(xiàn)兩次
int h[N], e[M], ne[M], idx;
//n個(gè)鏈表頭，e每一個(gè)結(jié)點(diǎn)的值，ne每一個(gè)結(jié)點(diǎn)的next指針
void add(int a, int b)//a->b
{//e記錄當(dāng)前點(diǎn)的值(地址->值),ne下一點(diǎn)的地址(地址->地址)，h記錄指向的第一個(gè)點(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)先搜索的遍歷順序?yàn)橐粭l路徑走到底然后回溯再走下一條路徑這種遍歷方法很省內(nèi)存但是不能一次性給出最短路徑或者最優(yōu)解。

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

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

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

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

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

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

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

模板及注釋

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

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

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

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

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

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

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

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

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

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

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

9.檢測(cè)一個(gè)圖是否是一個(gè)二分圖，DFS和BFS都可以。

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

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

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

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

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

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

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

5.檢測(cè)一個(gè)圖是否是二分圖。

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

7.解決難題，如迷宮問(wèn)題。

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

您可能感興趣的文章: