樹和圖的DFS和BFS周遊

樹和圖的DFS和BFS周遊，本質是dfs和bfs搜尋在圖論中的應用，邏輯都是一樣的，不一樣或者說需要注意的是：在數和圖中往往每個節點隻會被通路一次。此外，實作方式也略有不同。時間複雜度都是O(n+m)。

DFS模闆

int dfs(int u)
{
    st[u] = true; // st[u] 表示點u已經被周遊過

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}
           

• 用數組模拟連結清單實作的鄰接表，在dfs過程中做狀态轉移時，初始為頭節點（h[u])，更新為指針指向的節點，結束條件為-1.
• 往往隻會通路一遍節點，用一個state[N]的bool數組表示各個點是否被通路過。

例題

樹的重心

BFS模闆

queue<int> q;
st[1] = true; // 表示1号點已經被周遊過
q.push(1);

while (q.size())
{
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示點j已經被周遊過
            q.push(j);
        }
    }
}

作者：yxc
連結：https://www.acwing.com/blog/content/405/
來源：AcWing
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。
           

例題

圖中點的層次