图的遍历

常见的图的遍历方式:

1. DFS：时间复杂度 $O(N+M)$
2. BFS：时间复杂度 $O(N+M)$

DFS(u) // u 图中的一个顶点。
    访问 u
    在 u 上打访问标记
   
    for v in u 的相邻节点
        if v 未被访问 then
            DFS(v)
        end
    end
end

BFS(u)
    访问 u
    u 标记访问
    u 入队

    while 队列不为空
        h <- 队头出队
        for v in h 的相邻节点
            if v 未被访问 then
                v 入队
                v 标记访问
            end
        end
    end
end

图的 DFS 遍历——树的重心

题目描述

给定一颗树，树中包含  $n$  个结点（编号  $1\sim n$）和  $n-1$  条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

输入格式

第一行包含整数  $n$，表示树的结点数。

接下来  $n-1$  行，每行包含两个整数  $a$  和  $b$，表示点  $a$  和点  $b$  之间存在一条边。

输出格式

输出一个整数  $m$，表示将重心删除后，剩余各个连通块中点数的最大值。

数据范围

$1\le n\le {10}^5$

输入样例

9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6

输出样例

4

参考代码

// 使用vector存储图
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int n;
int ans = N;
int st[N];

vector<vector<int>> g(N);

int dfs(int u) { // 返回以u为根的子树的节点数目
    st[u] = 1;

    int size = 0, sum = 1;
    for (int i = 0; i < g[u].size(); i++) {
        int j = g[u][i];
        if (!st[j]) {
            int s = dfs(j);
            size = max(size, s);
            sum += s;
        }
    }
    size = max(size, n - sum);
    ans = min(ans, size);

    return sum;
}

int main() {
    cin >> n;

    for (int i = 1; i <= n - 1; i++) {
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(1);

    cout << ans << endl;

    return 0;
}

// 使用邻接表存储图
#include <bits/stdc++.h>

using namespace std;

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

int h[N], e[M], ne[M], idx;
int n;
int ans = N;
int st[N];

void init() {
    memset(h, -1, sizeof h);
    idx = 0;
}

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

int dfs(int u) { // 返回以u为根的子树的节点数目
    st[u] = 1;

    int size = 0, sum = 1;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (!st[j]) {
            int s = dfs(j);
            size = max(size, s);
            sum += s;
        }
    }
    size = max(size, n - sum);
    ans = min(ans, size);

    return sum;
}

int main() {
    init();

    cin >> n;

    for (int i = 1; i <= n - 1; i++) {
        int a, b; cin >> a >> b;
        add(a, b);
        add(b, a);
    }

    dfs(1);

    cout << ans << endl;

    return 0;
}

图的 BFS 遍历——图中点的层次

题目描述

给定一个  $n$  个点  $m$  条边的有向图，图中可能存在重边和自环。

所有边的长度都是 $1$，点的编号为  $1\sim n$。

请你求出  $1$  号点到  $n$  号点的最短距离，如果从  $1$  号点无法走到  $n$  号点，输出  $-1$。

输入格式

第一行包含两个整数  $n$  和  $m$。

接下来  $m$  行，每行包含两个整数  $a$  和  $b$，表示存在一条从  $a$  走到  $b$  的长度为  $1$  的边。

输出格式

输出一个整数，表示  $1$  号点到  $n$  号点的最短距离。

数据范围

$1\le n,m\le {10}^5$

输入样例

4 5
1 2
2 3
3 4
1 3
1 4

输出样例

1

参考代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx;
int q[N];
int d[N];
int n, m;

void init() {
    memset(h, -1, sizeof h);
    idx= 0;
}

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

int bfs() {
    int hh = 0, tt = -1;
    q[++tt] = 1;

    memset(d, -1, sizeof d);
    d[1] = 0;

    while (hh <= tt) {
        int t = q[hh++];
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (d[j] == -1) {
                q[++tt] = j;
                d[j] = d[t] + 1;
            }
        }
    }

    return d[n];
}

int main() {
    init();

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b; cin >> a >> b;
        add(a, b);
    }

    cout << bfs() << endl;

    return 0;
}

利用图的遍历求连通分量的个数

问题描述

警察抓到了 $n$ 个罪犯，警察根据经验知道他们属于不同的犯罪团伙，却不能判断有多少个团伙，但是通过审讯，知道其中的一些罪犯之间相互认识。已知同一犯罪团伙的成员之间直接或间接认识，一个犯罪团伙有可能只有一个人。请你根据已知罪犯之间的关系，确定犯罪团伙的数量。罪犯的编号 $1\sim n$

输入描述

第一行输入一个整数 $n(n<1000)$，表示罪犯的数量。

第二行输入一个整数 $m(m<5000)$，表示已知不同罪犯之间存在 $m$ 对关系。

之后 $m$，每行输入两个数 $i$ 和 $j$，表示罪犯 $i$ 和罪犯 $j$ 认识。

输出描述

一个整数，表示犯罪团伙的数量。

输入样例

11
8
1 2
4 5
3 4
1 3
5 6
7 10
5 10
8 9

输出样例

3

问题分析

从子图中的任意顶点出发，可以将子图中的顶点逐一遍历并进行标记，子图遍历结束即找到一个连通分量。再从下一个未标记顶点出发进行遍历，依次类推。直到所有顶点都被遍历。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1010, M = 5 * N;
int h[N], e[M], ne[M], idx;
int st[N];
int n, m;

void init() {
    memset(h, -1, sizeof h);
    idx = 0;
}

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

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

int main() {
    init();
   
    cin >> n >> m;
    int a, b;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }

    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (!st[i]) {
            cnt++;
            dfs(i);
        }
    }

    cout << cnt << endl;

    return 0;
}