C++詳細講解圖的遍歷

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

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

圖的遍歷

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

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

也可以看：點這里

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

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

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

4.插入邊使用的頭插法，例如插入：a->b。首先把b節(jié)點存入e數組，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，因為每條邊在鄰接表中會出現兩次
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);

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

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

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

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

// 需要標記數組st[N],  遍歷節(jié)點的每個相鄰的點
void dfs(int u) {
    st[u] = true; // 標記一下，記錄為已經被搜索過了，下面進行搜索過程
    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）

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

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

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

模板及注釋

queue<int> q;//借助隊列實現
st[1] = true; // 表示1號點已經被遍歷過
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已經被遍歷過
            q.push(j);//節(jié)點入隊
        }
    }
}