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

有向图的拓扑排序-BFS求解

article 2025/3/3 2:25:03

有向图的拓扑排序-BFS求解

题目描述

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 -1。

若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x, y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。

输入格式

第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 x 和 y，表示点 x 和点 y 之间存在一条有向边 (x, y)。

输出格式

共一行，如果存在拓扑序列，则输出拓扑序列。
否则输出 -1。

数据范围

1 ≤ n, m ≤ 10^5

输入样例

复制

输出样例

复制

1 2 3

解题思路

解题思路：

我们首先要记录每个结点的入度，即每个结点有几条边指向它，然后找出所有入度为0的结点，将其放入队列，那么从这个结点开始，将它指向其他结点的边删去。如果删去这条边后，原本有这个结点指向的那个结点入度为0（即只有开始这个结点指向它），那么就将其入队。直到遍历到最后一个结点，如果尾指针不等于n，就说明没有经过所有点，那么这条路径就不符合拓扑排序。再重复上述操作，直到所有入度为0的点都枚举完都没找到，那么这个无向图就没有拓扑排序。

一篇很清楚的笔记。

在这里插入图片描述

代码实现

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int h[N], e[N], ne[N];
int q[N], d[N];
int n, m, idx;
void add(int a, int b)
{
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx++;
}
bool topsort()
{
	int hh = 0, tt = 0;
		
	for (int i = 1; i <= n; i++)
	{
		if (d[i] == 0)
		{
			q[tt++] = i; //找到没有被其他结点指向的元素,将其入队
		}
	}
 
	while (hh <= tt)
	{
		int k = q[hh++];
		for (int i = h[k]; i != -1; i = ne[i])
		{
			int j = e[i];
			d[j]--;   //删去由k指向j的这条边
			if (d[j] == 0) //如果发现该节点入度为0，即没有其他结点指向他了，就将其入队
				q[tt++] = j;
		}
	}
	return tt == n; //如果tt=n就表示每个结点都走到了，就是一个拓扑排序
}
int main()
{
	cin >> n >> m;
	memset(h, -1, sizeof h);
	while (m--)
	{
		int a, b;
		cin >> a >> b;
		add(a, b);
		d[b]++; //入度，即记录b这个结点有几条边指向他
	}
	if (topsort())
	{
		for (int i = 0; i < n; i++)
		{
			cout << q[i] << " ";
		}
	}
	else
		cout << "-1" << endl;
	return 0;
}

代码思路总结

该题是一个典型的拓扑排序问题，用于求解有向无环图（DAG）的拓扑序列。拓扑排序的核心思想是通过 BFS（广度优先搜索） 或 DFS（深度优先搜索） 来实现。本题使用的是 BFS 方法，具体实现基于 Kahn 算法。

1. 图的表示

使用邻接表存储图：
- h[N]：h[i] 表示节点 i 的第一条边的索引。
- e[N]：e[i] 表示第 i 条边的终点。
- ne[N]：ne[i] 表示第 i 条边的下一条边的索引。
- idx：用于给每条边分配一个唯一的索引。
使用数组 d[N] 记录每个节点的入度（即有多少条边指向该节点）。

2. 插入边

add(int a, int b) 函数用于将一条从节点 a 指向节点 b 的边插入到邻接表中。
使用头插法将新边插入到邻接表中：
- e[idx] = b：记录边的终点。
- ne[idx] = h[a]：将新边的下一条边指向 h[a]。
- h[a] = idx++：更新 h[a] 为当前边的索引，并递增 idx。

3. 拓扑排序实现

初始化：
- 使用队列 q[N] 存储入度为 0 的节点。
- 遍历所有节点，将入度为 0 的节点加入队列。
BFS 过程：
- 从队列中取出队头节点 k，将其加入拓扑序列。
- 遍历从 k 出发的所有边，减少邻接节点 j 的入度。
- 如果邻接节点 j 的入度变为 0，则将其加入队列。
判断是否存在拓扑序列：
- 如果最终队列中的节点数等于 n，则说明图中没有环，拓扑序列存在。
- 否则，说明图中存在环，无法构造拓扑序列。

4. 主函数

读取输入的节点数 n 和边数 m。
初始化邻接表 h 为 -1，表示所有节点的第一条边初始为空。
读取每条边并调用 add 函数插入到邻接表中，同时更新节点的入度。
调用 topsort() 函数判断是否存在拓扑序列：
- 如果存在，输出拓扑序列。
- 否则，输出 -1。

5. 复杂度分析

时间复杂度：O(n + m)，其中 n 是节点数，m 是边数。每个节点和每条边都只会被访问一次。
空间复杂度：O(n + m)，用于存储邻接表和队列。

6. 代码细节

入队条件：
- 只有入度为 0 的节点才会被加入队列。
队列的实现：
- 使用数组 q[N] 模拟队列，hh 表示队头，tt 表示队尾。
拓扑序列的存储：
- 队列 q 中存储的节点顺序就是拓扑序列。

7. 示例运行

输入：

复制

执行过程：

初始化：
- 邻接表：
  - h[1] 指向边 (1, 2) 和 (1, 3)。
  - h[2] 指向边 (2, 3)。
  - h[3] 为空。
- 入度数组：
  - d[1] = 0，d[2] = 1，d[3] = 2。
将入度为 0 的节点 1 加入队列。
处理队列：
- 取出节点 1，加入拓扑序列。
- 减少节点 2 和 3 的入度：
  - d[2] = 0，将 2 加入队列。
  - d[3] = 1。
- 取出节点 2，加入拓扑序列。
- 减少节点 3 的入度：
  - d[3] = 0，将 3 加入队列。
- 取出节点 3，加入拓扑序列。
最终拓扑序列为 1 2 3。