BFS 借助队列
- 入队 所有
入度==0
的点
- 当队列非空时, 出队 队头元素
t
- 枚举
t
的所有邻边结点p
, 判断当t
出队后结点 p
的入度是否==0,若是则将结点p
入队
- 重复
2, 3
直到队列为空
- 队列为空时, 如果所有元素均入队, 则存在拓扑排序, 反之不存在拓扑排序
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, M = 1e5 + 10;
int n, m;
int d[N]; // 入度
int q[N]; // 辅助队列
// 邻接表存储图
struct Node
{
int id;
Node* next;
Node (int _id): id(_id), next(NULL) {}
}*head[N];
// 头插法添加 a到b 的边
void add(int a, int b)
{
auto p = new Node(b);
p->next = head[a];
head[a] = p;
}
// 拓扑排序
bool topsort()
{
// tt 指向队列的最后一个元素
int hh = 0, tt = -1;
// 入度为 0 的点入队
for (int i = 1; i <= n; i ++ )
if (!d[i])
q[++ tt] = i;
// 当队列非空时
while (hh <= tt)
{
int t = q[hh ++]; // 队头出队
// 枚举 t 的所有出度结点
for (auto p = head[t]; p; p = p->next)
{
// 这里一定是--在前!!!!!
if (-- d[p->id] == 0) // 如果将 t 删除之后, 其邻边结点的入度为0
q[++ tt] = p->id;// 则将邻边结点入队
}
}
// 如果所有点都入队了, 说明存在拓扑序列, 否则不存在拓扑序列。
return tt == n - 1;
}
int main()
{
cin >> n >> m;
// 将结点a->b存到图中去
while (m -- )
{
int a, b;
cin >> a >> b;
d[b] ++; // 入度++
add(a, b);
}
if (!topsort()) cout << "-1" << endl;
else
{
for (int i = 0; i < n; i ++)
cout << q[i] << " ";
}
return 0;
}
DFS 借助函数栈: 在回溯之前输出, 则为拓扑排序的逆序
- 无环则存在拓扑排序
- 有环则dfs必会遍历到
处在递归当中
的结点
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, M = 1e5 + 10;
int n, m;
int st[N]; // 0为未遍历, 1为递归当中, 2为已遍历完
int res[N], top = 0;
// 邻接表存储图
struct Node
{
int id;
Node* next;
Node (int _id): id(_id), next(NULL) {}
}*head[N];
// 头插法添加 a到b 的边
void add(int a, int b)
{
auto p = new Node(b);
p->next = head[a];
head[a] = p;
}
bool dfs(int t)
{
st[t] = 1; // 在递归当中
// 枚举 t 的所有邻接结点
for (auto p = head[t]; p; p = p->next)
{
int id = p->id;
// 该邻接结点未遍历, 则直接dfs
if (st[id] == 0)
{
// 在dfs的过程中遇见了环(遇到了在递归当中的结点)
if(!dfs(id)) return false;
}
// 出口: 该邻接结点在递归当中
else if (st[id] == 1) return false;
}
// 回溯状态
res[top ++] = t;
st[t] = 2;
return true;
}
// 拓扑排序
bool topsort()
{
// dfs要遍历所有的结点 注意id范围: 1~n
for (int i = 1; i <= n; i ++ )
if (!st[i] && !dfs(i)) // 未访问则直接dfs
return false; // 存在环
return true;
}
int main()
{
cin >> n >> m;
// 将边a->b存到图中去
while (m -- )
{
int a, b;
cin >> a >> b;
add(a, b);
}
if (!topsort()) cout << "-1" << endl;
else
{
for (int i = n - 1; i >= 0; i --)
cout << res[i] << " ";
}
return 0;
}