Acwing 树与图的遍历、拓扑排序

1.深度优先遍历(DFS)

树和图的存储

首先，树是一种特殊的图（无环连通图）。所以，这里只说图的存储即可
图分为两种，有向图和无向图

• 有向图中2个点之间的边是有方向的，比如a -> b，则只能从a点走到b点，无法从b点走到a点。
• 无向图中2个点之间的边是没有方向的，比如a - b，则可以从a走到b，也可以从b走到a。

通常，我们可以将无向图看成有向图，比如上面，对a到b之间的边，我们可以建立两条边，分别是a到b的和b到a的。所以，我们只需要考虑，有向图如何存储即可。有两种存储方式：

• 邻接矩阵：用一个二维数组来存，比如g[a,b]存储的就是a到b的边。邻接矩阵无法存储重复边，比如a到b之间有2条边，则存不了。（用的较少，因为这种方式比较浪费空间，对于有n个点的图，需要$n^2$的空间，这种存储方式适合存储稠密图）；
• 邻接表：使用单链表来存。对于有n个点的图，我们开n个单链表，每个节点一个单链表。单链表上存的是该节点的邻接点（用的较多）

Acwing 846.树的重心

输入样例：

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

输出样例：

4

题意：如下图，删除节点1后，剩下三个连通块，最大连通块中点的数量为4；删除节点2后最大连通块点数为6；删除4后最大连通块点数为5…，以此类推，最后得到这些数当中的最小值为4，该节点即为重心。

实现思路：用深度优先遍历

• 图采用邻接表存储，设置数组h[],h[i]存储节点i的第一个相邻点（字节点）的下标，初始值为-1.以此构成每个h[i]都指向一条链表
• 图的深度优先遍历：设置一个数组st[i],表示节点i是否被访问过，每个节点仅被访问一次i。访问每个节点，然后访问这个节点所连的未被访问的点，再以这个点为对象递归向下访问其连接的未访问的点。这里给出DFS的板子：

int dfs(int u) {
    st[u] = true; // 标记当前节点已被访问
   
    for (int i = h[u]; i != -1; i = ne[i]) { // 遍历当前节点的所有相邻节点
        int j = e[i]; // 获得邻接的子节点
        if (!st[j]) { // 如果子节点未被访问过
           dfs(j); // 递归处理子节点
        }
    }
}

• 如何求某个节点删除后的最大连通块中的点数？要以当前节点，分向下、向上两部分来计算比较
• • 求当前节点向下的最大连通块中节点数：遍历访问当前节点的每个字数，记录该节点的子树中具有最多的节点数res。同时记录当前节点及其所有子树的节点数sum(初始化为1即包含当前节点）
• • 求当前节点向上的连通块中节点数：即总结点数n - sum;
• • 然后两者中取最大值:res = max(res,n - sum),即为删除当前节点后最大连通块的节点数
• 最后比较各删除节点的最大连通块的节点数，取最小值：ans = min(ans,res),即为重心删除后的最大连通块的节点数。
  注意：e[] 和 ne[] 设置为 2 * N 是为了处理无向图的双向边，确保邻接表可以容纳所有边的双向信息。

具体实现代码（详解版）：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e5 + 10;
const int M = 2 * N;//无向图

bool st[N]; // 判断当前节点是否已被访问
int h[N], e[M], ne[M], idx; // 实现邻接表

int n; // 节点总数
int ans = N; // 存储最终结果，初始化为一个很大的值

// 插入节点，构造邻接表，头插法
void add(int a, int b) { // a 与 b 之间建立一条边
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

// 返回当前节点及其子树的节点总数
int dfs(int u) {
    st[u] = true; // 标记当前节点已被访问

    int sum = 1, res = 0; // sum 表示当前节点及其子树的节点总数，初始化为1即当前节点
    // res 表示删除该节点后最大连通块的节点数
    for (int i = h[u]; i != -1; i = ne[i]) { // 遍历当前节点的所有相邻节点
        int j = e[i]; // 获得邻接的子节点
        if (!st[j]) { // 如果子节点未被访问过
            int s = dfs(j); // 递归处理子节点，获得该子树的节点数
            res = max(res, s); // 更新当前节点下最大连通块的大小
            sum += s; // 累加子树节点数
        }
    }
    res = max(res, n - sum); // 与剩余的树部分比较，取最大连通块
    ans = min(ans, res); // 记录所有节点中的最优结果
    
    return sum; // 返回当前节点及其子树的总节点数
}

int main() {
    cin >> n;
    memset(h, -1, sizeof h); // 初始化邻接表，初始值设为 -1

    for (int i = 0; i < n - 1; i++) { // 构建 n-1 条边
        int a, b;
        cin >> a >> b;
        add(a, b); // 添加无向图的边
        add(b, a);
    }
    
    dfs(1); // 从节点 1 开始进行深度优先遍历
    cout << ans << endl; // 输出最小的最大连通块的大小
    return 0;
}

2.宽度优先遍历(BFS）

Acwing 847.图中点的层次

实现思路：权值都为1，可以使用广度优先遍历，具有最短路的特性

• 依旧使用邻接表的方式存储图；
• 设置一个队列q[]，初始1号节点入队，队列不为空的时候就持续操作，每次处理完一个节点，就入队；
• 设置一个数组d[],表示当前节点与1号节点的距离，初始化为-1，等于-1时表示当前节点还未被处理，每次处理完一个节点就+1；

具体实现代码（详解版）：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10; // 最大节点数量

int q[N], d[N]; // q[] 队列用于 BFS，d[] 存储节点到 1 号节点的最短距离
int e[N], h[N], ne[N], idx; // 邻接表：e[] 存储边的终点，h[] 存储每个节点的第一条边，ne[] 存储下一条边的索引
int n, m; // n 是节点数，m 是边数

// 在节点 a 和 b 之间添加边
void add(int a, int b) {
    e[idx] = b;     // e[] 存储边终点
    ne[idx] = h[a]; // ne[] 存储下一条边的索引，指向上一条边
    h[a] = idx++;   // h[] 更新，表示 a 的第一条边的索引是 idx
}

// 返回从节点 1 到节点 n 的最短路径距离
int bfs() {
    // 初始化 d[] 数组，所有节点的距离设为 -1，表示未访问
    memset(d, -1, sizeof d);
    
    int hh = 0, tt = 0; // hh 是队列头，tt 是队列尾
    q[0] = 1; // 将 1 号节点放入队列
    d[1] = 0; // 1 号节点到自身的距离为 0
    
    // 开始 BFS
    while (hh <= tt) { // 当队列非空时，继续遍历
        int t = q[hh++]; // 取出队头元素 t
        
        // 遍历 t 节点的所有相邻节点
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i]; // 获取 t 节点的相邻节点 j
            
            if (d[j] == -1) { // 如果 j 节点未被访问过
                d[j] = d[t] + 1; // 更新 j 节点的距离：从 t 到 j 增加 1
                q[++tt] = j; // 将 j 节点加入队列
            }
        }
    }
    
    // 返回节点 1 到节点 n 的最短距离
    return d[n];
}

int main() {
    cin >> n >> m; 
    memset(h, -1, sizeof h); // 初始化邻接表 h[]，初始值为 -1，表示无边
    
    // 读取 m 条边，并在图中添加
    while (m--) {
        int a, b;
        cin >> a >> b; // 输入边的两个端点 a 和 b
        add(a, b); // 在邻接表中添加 a -> b 的边
    }
    
    // 输出从 1 号节点到 n 号节点的最短路径长度
    cout << bfs() << endl;
    
    return 0;
}

3. 宽度优先遍历的应用-拓扑序列

• 什么是拓扑序？将一个图的很懂节点，排成一个序列，使得图中的所有边，都是从前面的节点，指向后面的节点。则这样一个节点的排序，称为一个拓扑序；

• 若图中有环，则一定不存在拓扑序

• 可以证明，一个有向无环图，至少存在一个入度为0的点，即一定存在一个拓扑序列。有向无环图，又被称为拓扑图
  对于每个节点，存在2个属性，入度和出度

• 入度：即有多少条边指向自己；

• 出度：即有多少条边从自己这个节点出去
  我们每次以入度为0的点为突破口进行处理，每次得到一个新的入读为0的点，继续处理；

Acwing 848.有向图的拓扑排序

实现思路：拓扑排序是一种用于有向无环图（DAG）的排序方法，通常用于解决依赖关系问题（如任务调度）。算法的基本思路是找到所有入度为 0 的节点，将它们加入队列，依次处理这些节点，并逐步减少它们指向的节点的入度。如果最后所有节点都被处理了，则拓扑排序成功；否则图中存在环，无法进行拓扑排序。

• 依旧使用邻接表存储图；
• 设置一个数组d[]，表示当前节点的入度，每次添加边就要更新；
• 设置一个队列，将入度为0的点入队，初始遍历所有节点将入度为0的点加入队列；
• 然后队列不为空的时候取出队头元素，枚举队头元素的所有出边，然后删除，则指向节点的入度减1，假如指向的节点入度刚好减为0了，则入队。然后继续处理；
• 通过检查队列中是否处理了所有节点（tt == n - 1），来判断图中是否存在拓扑序列

具体实现代码（详解版）：

#include <iostream>
#include <cstring> // 包含memset函数，用于初始化数组

using namespace std;

const int N = 1e5 + 10; // 定义数组的最大长度，保证足够存储数据

int q[N], d[N], h[N], e[N], ne[N], idx; // 定义需要的数组
// q[N] 存储拓扑排序结果的队列
// d[N] 存储每个节点的入度
// h[N] 是邻接表头节点数组，表示某个节点指向的第一条边的编号
// e[N] 表示边的终点，即 e[i] 表示第 i 条边指向的终点节点
// ne[N] 表示下一个边的编号，构成邻接表的链表
// idx 用于记录当前边的编号索引

int n, m; 

// 添加一条从节点 a 到节点 b 的有向边
void add(int a, int b){
    e[idx] = b;        // e[idx] 存储边的终点为 b
    ne[idx] = h[a];    // ne[idx] 存储下一条边的编号为 h[a]
    h[a] = idx ++;     // 更新节点 a 的头节点为当前边的编号，然后自增 idx
}

// 拓扑排序函数，返回是否存在拓扑排序
bool topsort(){
    int hh = 0, tt = -1; // hh 和 tt 分别表示队列的头和尾
    // 初始化队列：将所有入度为 0 的节点入队
    for (int i = 1; i <= n; i++) {
        if (!d[i]) q[++tt] = i; // 如果节点 i 的入度为 0，将其加入队列
    }
    
    // 处理队列中的节点
    while (hh <= tt) { // 当队列不为空时
        int t = q[hh++]; // 从队列中取出队首节点 t
        // 遍历节点 t 的所有出边
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];  // j 是当前边的终点节点
            d[j]--;        // 对终点节点 j 的入度减 1
            if (!d[j]) q[++tt] = j; // 如果节点 j 的入度变为 0，则将其加入队列
        }
    }
    
    // 如果处理了 n 个节点，说明存在拓扑序列
    return tt == n - 1; // 返回 true 表示拓扑排序成功，false 表示有环
}

int main(){
    cin >> n >> m; 
    memset(h, -1, sizeof h); // 初始化邻接表头节点数组，-1 表示没有出边
    
    while (m--) {
        int a, b;
        cin >> a >> b; // 输入一条从 a 到 b 的有向边
        add(a, b);     // 将边添加到邻接表中
        d[b]++;        // 增加节点 b 的入度
    }
    
    // 调用拓扑排序函数，如果返回 true，则输出拓扑排序结果
    if (topsort()) {
        // 输出拓扑排序结果
        for (int i = 0; i < n; i++) cout << q[i] << ' ';
        cout << endl; // 换行
    } else {
        // 如果没有拓扑排序（图中有环），输出 -1
        cout << -1;
    }
    
    return 0; // 程序结束
}

以上就是树与图的遍历还有拓扑排序。

原文地址：https://blog.csdn.net/qq_43060884/article/details/142458518

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！