抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

这篇文章将介绍图论中的拓扑排序。

什么是拓扑排序?

对于任何有向无环图而言,其拓扑排序为其所有结点的一个线性排序(对于同一个有向五环图而言可能存在多个这样的结点排序)。

拓扑排序

  • 入度:指向v的边的个数叫做v的入度。
  • 出度:v指向的点的个数叫做v的出度。

如果一个点的入度是0,那么说明这个点是起点(起点不止一个)。如果一个点的出度为0,那么说明这个点排在最后。

举例说明:

DAG1

如图所示,这是一个有向无环图,其指向顺序为a,(b,c),d,e,则abcdeacbde都是这个图的拓扑排序。

很显然,一个图是有向无环图(DAG)是其可以进行拓扑排序的充要条件。

拓扑排序的实现

DFS和BFS都可以实现拓扑排序。

BFS实现拓扑排序

这种算法也叫做Kahn算法

继续使用上面的例子进行说明

DAG1

BFS实现拓扑排序有两个实现方向,即无前驱的顶点优先、无后继的顶点优先,简单点说就是顺着找或倒着找。两种方法都差不多,在这里只介绍无前驱的定点优先。

无前驱的顶点优先就是顺着找,a的入度为0,则其为起点,a入队;

a出队,a指向了c,c的入度减一,判断其入度是否为零,若为零,则入队,则c入队,b同理也入队;

目前队列中有{c,b},c出队,c指向d,d入度减一,d入度不为零,不入队;

b出队,b指向d,d入度减一,d入度为零,入队;

d出队,d指向e,e入度减一,e入度为零,入队;

e出队,无后续结点,结束。

由上述过程可得拓扑排序为acbde

时间复杂度

假设这个图$G = (V,E)$,则其时间复杂度为$O(E+V)$。

代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int T, n, m, u, v;

int deg[N];
int vis[N];
int dest[N];
vector<int> g[N];
queue<int> q;

bool toposort() {
//将入度为零的点放入队列
for (int i = 1; i <= n; i++) {
if (!deg[i]) {
vis[i] = 1;
q.push(i);
}
}

int num = 0;
while (!q.empty()) {
int now = q.front();
q.pop();
dest[num++] = now;

for (auto to : g[now]) {
if (vis[to]) //判断该节点是否在队列中
continue;
else {
deg[to]--; //入度减一
if (!deg[to]) { //判断入度是否为零
q.push(to); //入队
vis[to] = 1; //标记其在队列中
}
}
}
}
if (num == n)
return true;
else
return false;
}

int main(int argc, char const *argv[]) {
memset(deg, 0, sizeof(deg));
memset(vis, 0, sizeof(vis));
memset(dest, 0, sizeof(dest));

for (int i = 1; i <= N; i++)
g[i].clear();

while (!q.empty())
q.pop();
//以上为初始化

cin >> n >> m;
for (int i = 1; i <= m; i++) {
scanf("%d%d", &u, &v); //读入
g[u].push_back(v);
deg[v]++; //统计入度
}

if (toposort()) {//如果可以生成拓扑排序
for (int i = 0; i < n; i++) //输出结果
printf("%d%c", dest[i], i == n ? '\n' : ' ');
}
else printf("NO\n");

return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
//测试数据
//有向有环图
2 1
1 3
3 4
4 2
//有向无环图
1 2
1 3
3 4
2 4
4 5

DFS实现拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;

int n, u, v;
int c[N]; // 标志数组
vector<int> G[N]; // vector 实现的邻接表
vector<int> topo; // 拓扑排序后的节点

bool dfs(int u) {
c[u] = -1;
for (int v : G[u]) {
if (c[v] < 0)
return false;
else if (!c[v])
if (!dfs(v))
return false;
}
c[u] = 1;
topo.push_back(u);
return true;
}

bool toposort() {
topo.clear();
memset(c, 0, sizeof(c));
for (int u = 0; u < n; u++)
if (!c[u])
if (!dfs(u))
return false;
reverse(topo.begin(), topo.end());
return true;
}

int main(int argc, char const *argv[]) {
return 0;
}

评论