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

模板如下：

//鄰接表
const int N = 100010, M = N * 2;
//無向圖n條邊時，最多2n個idx，因為每條邊在鄰接表中會出現(xiàn)兩次
int h[N], e[M], ne[M], idx;
//n個鏈表頭，e每一個結(jié)點的值，ne每一個結(jié)點的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);

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

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

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

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

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

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

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

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

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

模板及注釋

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

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

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

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

2.P2P網(wǎng)絡(luò)中查找臨近的結(jié)點，應(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查找附近地點等。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

您可能感興趣的文章: