当前位置：首页 > java >正文

ch09 课堂参考代码

java 2025/7/1 22:31:48

ch09 拓扑排序与基环树

拓扑排序

在一些场景中，需要完成一系列事情，这些事情之间有顺序关系或者依赖关系，在做一件事情之前必须先做另一件事，例如课程学习的先后顺序，这类问题可以抽象为图论中的拓扑排序问题。
拓扑排序要解决的问题是给一个有向无环图（Directed Acyclic Graph，缩写是 DAG）的所有结点排序。
排序规则是如果图中存在一条边 $u\to v$ ，则结点 u 必须排在 v 之前。
相关概念：
- 入度：以结点 v 为终点的边的数量称为 v 的入度。也就是“连进来的边”的数量。
- 出度：以结点 u 为起点的边的数量称为 u 的出度。也就是“连出去的边”的数量。
拓扑排序步骤：
- 找到所有入度为 0 的结点，显然这些结点应该排在前面（具体谁先谁后没有关系）。用一个容器（队列）储存当前我们找到的入度为 0 的结点。
- 每次取出一个入度为 0 的结点 $u$ ，此时 $u$ 就是拓扑序列中的下一个结点。
- 对于 $u$ 的每一条出边 $u\to v$ ， $v$ 的入度 -1（相当于删除 $u$ 、删除 $u$ 的出边，因为只关心入度，所以入度 -1 即可，不用真的执行删边操作）。
- 如果 $v$ 的入度 -1 后变为了 0，那么将 v 放进容器（队列）中。
- 重复上述操作，直到队列为空。
拓扑排序无解的判断：如果队列空了，但是还有点未进入队列，即这些点的入度都 > 0，说明图不是 DAG，不存在拓扑排序。
拓扑排序结果不唯一的判断：如果同时有多个入度为 0 的结点，前面说到具体谁先谁后没有关系，那么拓扑排序有多种可能的结果。具体的判断就是如果某一时刻队列里的元素个数 > 1，可以判定拓扑排序结果不唯一。

代码：

void topo(int n) {queue<int> que;for (int i = 1; i <= n; i++) {if (in[i] == 0) que.push(i);}while (!que.empty()) { // while循环次数（入队次数），<n说明无解if (que.size() > 1) { } // 满足if说明拓扑排序不唯一int u = que.front(); // u是拓扑序列的下一个结点，要输出拓扑序列则在这里输出uque.pop();// 删除以结点u为起点的边，也就是边的终点入度-1for (int i = 0; i < G[u].size(); i++) {int v = G[u][i];in[v]--;if (in[v] == 0) {que.push(v);}}}
}

基环树

无向边的基环树

n 个点的树有 n - 1 条边，再添加一条边则必然会出现一个环，除了环之外，其余部分是若干棵子树。
这种 n 个点 n 条边的连通无向图，称为“基环树”，可以把环看作基环树广义的“根结点”。
若干棵基环树组成的森林，称为“基环树森林”。显然基环树森林必然也是 n 个点 n 条边，但 n 个点 n 条边的无向图不一定是基环树森林。
对于基环树（森林）的处理，分为环外和环内两部分。
- 环外部分
  - 与结点 u 相连的边的条数称为该结点的“度”或“度数”。
  - 环外最外围的结点度数是 1，从度数为 1 的结点开始，用类似拓扑排序的方法，环外的结点逐步入队，环内的结点无法入队，以此找出所有环外的结点。
  - 代码：
```
vector<int> G[N];
int deg[N];
bool vis[N];
void topo(int n) {queue<int> que;for (int i = 1; i <= n; i++) {if (deg[i] == 1) que.push(i); // deg[i]表示结点i的度数}while (!que.empty()) {int u = que.front();que.pop();vis[u] = true; // 标记结点u是环外的点for (int v : G[u]) {deg[v]--;if (deg[v] == 1) que.push(v);}}
}
```
- 环内部分
  - 经过 topo() 的处理后，vis[u] == false 的结点 u 就是环中的点。
  - 如果需要遍历一个环中的点，从环中一个点出发，搜索其连通的所有 vis[] 为 false 的点即可。

有向边的基环树

有向图中，也有类似概念，如果每个结点有且仅有一条出边（即出度为 1），并且是弱连通的（即换成无向边后是连通的），称为“基环内向树”。可以尝试自己举一些例子画出来看看，环外的点都指向环的方向，好像以“基环”为中心，有向内收缩的趋势，所以叫“内向”。
若干棵基环内向树组成的森林，称为“基环内向树森林”。
同理，如果每个结点有且仅有一条入边（即入度为 1），则是“基环外向树”或“基环外向树森林”。
常常把“基环内向树”和“基环外向树”也简称为“基环树”。
只需要学习如何处理“基环内向树”，对于“基环外向树”把所有边换个方向也就转换为“基环内向树”问题。

对于基环内向树（森林）的处理，同样分为环外和环内两部分。

环外部分同样用拓扑排序，入度为 0 的结点入队。

// 因为只有一条出边，可以不用vector存图，nxt[u]记录u的出边终点即可
int nxt[N], in[N]; // in[u]表示u的入度
bool vis[N];
void topo(int n) {queue<int> que;for (int i = 1; i <= n; i++) {if (in[i] == 0) que.push(i); // 入度为0的结点入队}while (!que.empty()) {int u = que.front();que.pop();vis[u] = true; // 标记结点u是环外的点int v = nxt[u];in[v]--;if (in[v] == 0) que.push(v);}
}

环内部分也类似无向边的基环树，先找到环内一个点，从这个点出发去搜索。因为每个点只有一条出边，用循环写也很方便，一直往前走，直到回到本身，就走完了整个环。

int res = 0; // 记录换/内向基环数的个数
for (int i = 1; i <= n; ++i) {if (vis[i]) continue; // 跳过环外的点和走过的点int p = i, cnt = 0; // 如果需要计算环的长度，记录中 cnt 中while (!vis[p]) vis[p] = 1, p = nxt[p], ++cnt;++res;
}