樹與圖的DFS與BFS

  • 樹與圖的DFS與BFS
  • DFS
  • BFS

首先，樹是一種特殊結構的圖，所以樹與圖的存儲是相同的，而圖又分為有向圖與無向圖，對無向圖我們可以在兩個點之間添加兩條邊。

有向圖的存儲方式主要有兩種

  • 稀疏圖（點多邊少）一般用鄰接表存儲
  • 稠密圖（點少邊多）一般用鄰接矩陣存儲。

在鄰接表的實現中，用數組h來記錄每個節點向外的邊的鏈表頭指針，初始時都是空（即-1）。用idx來表示鏈表節點的分配位置。數組e表示節點的值，即是目標節點的編號。數組ne表示節點的next指針，也就是鏈表節點的下一節點被分配的下標。

注意，當用鄰接表去存無向圖（或者樹）的時候，因為a → b和b → a的邊都要存，所以放置鏈表節點信息的e數組和ne數組至少要開到邊總數目的兩倍大。

DFS

題目鏈接：AcWing 846. 樹的重心

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, M = N * 2;

int n;
int h[N], e[M], ne[M], idx; // 鄰接表存儲樹，無向邊所以e與ne數組開兩倍大小
bool st[N];  // 標記節點是否被訪問過
int ans = N; // 記錄答案（各個連通塊中點數的最大值）

// 添加一條a到b的有向邊
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u)
{
    // 標記當前節點已經被訪問
    st[u] = true;
    
    // sum存儲以當前節點為根的子樹大小
    // res存儲當前節點的最大子連通塊
    int sum = 1, res = 0;
    
    // 遍歷與當前節點相鄰的所有節點
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        // 如果j節點沒有被訪問過
        if (!st[j]) {
            int t = dfs(j);     // t為以j為根的子樹大小
            res = max(res, t);  // 更新最大子連通塊的值
            sum += t;           // 子樹大小加上這一子連通塊
        }
    }
    res = max(res, n - sum);    // 利用以u號節點為根的子樹之外的部分更新最大連通塊
    ans = min(ans, res);        // 更新以不同節點為重心的最大連通塊的值
    
    return sum;                 // 返回以當前節點為根的子樹大小
}

int main()
{
    memset(h, -1, sizeof h);    // 初始化鄰接表
    
    cin >> n;
    
    // 注意，此處不能使用while(n --)，這會改變n的值
    for (int i = 0; i < n - 1; i ++ ) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    
    dfs(1); // 從1號節點開始搜索
    
    cout << ans << endl;
    
    return 0;
}

BFS

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int h[N], e[N], ne[N], idx;
int d[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

// 寬搜套路，返回到1～n的最短距離
int bfs()
{
    queue<int> q;
    q.push(1);
    // 一般情況下距離數組初始化為正無窮，但本題中若不能到達則返回-1，所以用-1代表不可達
    memset(d, -1, sizeof d);
    d[1] = 0;
    
    while (q.size()) {
        int t = q.front();
        q.pop();
        
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            // 如果當前點還沒有訪問過
            if (d[j] == -1) {
                d[j] = d[t] + 1;
                q.push(j);
            }
        }
    }
    
    return d[n];
}

int main()
{
    memset(h, -1, sizeof h);
    
    cin >> n >> m;
    while (m -- ) {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    
    cout << bfs() << endl;
    
    return 0;
}