0%

关于topological sort(拓扑排序)的一点感悟

拓扑排序,从某种意义上说,我们在小学的时候,就早早已经接触了。例如:现在有四个数,a,b,c,d,其中a>c, a>d, c>d, d>b,问从大到小排列着四个数。答案显然,就是a,c,d,b。这就是最简单的拓扑排序了。

【定义,理解】

事实上,一个有向无环图G[V,E](简称DAG),将其排成一个线性序列,使得所有边的方向都一致,这一过程就是拓扑排序。(粗略定义)

他不见了。

首先,我们一开头题目为例子。如图a所示,
我们大小关系用边的方向来表示(a>d表示为a→d)。

我们移动点的位置,使得他们呈一条线排列,而且他们的边的方向都统一向右,显然,即如图b所示,

他不见了。

所以,排序后结果就是a,c,d,b。

【基本思路】

那么,我们应该如何让实现这一过程呢?

首先,我们多尝试几个例子,将其变成如图b的线性图后,发现:每个线性图的第一个点,入度都为0。证明:假设第一个点u的入读大于0,即有另外一个点s指向它,那么点s一定排在u前,与u是第一个点的条件矛盾,所以命题成立。

根据上述性质,我们只要找到入度为0的点v1(步骤1)。它就是拓扑排序后所得到的序列的第一个点v1。那么,如何让找到下一个点v2呢?

由于点v1的位置已经确定,无论它指向谁,都唔会对后面的序列产生影响,为了简便,我们将与v1相关联的边删去。不难发现,只要再重复上述步骤1,就可以得到点v2了。(步骤2)

综上所述,

① 找到入度为0的点vi,并加入序列尾部,执行步骤2;

② 删除与vi相关联的边,执行步骤3;

③ 若序列未满,则重复步骤1,否则退出。

【O(n*e)算法】

由于我们每次都要枚举每一个点,找到入度为0的点,然后搜索每一条边,若与之相关则删除,一共执行n次,故算法为O(n*e)。

程序如下:

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
//时间复杂度O(n^2) 
#include <cstdio>

#define maxn 5005

bool A[maxn][maxn], n;
int num[maxn];
int m;

int find_() {
for (int i=0; i!=n; ++i)
if (num[i] == 0)
return i;
}

void solve() {
for (int t=0; t!=n; ++t) {
int r = find_();
num[r] = -1;//标记已经寻找过
printf("%d ", r);
for (int j=0; j!=n; ++j)
if (A[r][j] == 1) {
A[r][j] = 0;
num[j] --;
}
}

printf("\n");
}

int main() {
freopen("topological sort.in","r",stdin);
freopen("topological sort.out","w",stdout);

scanf("%d%d",&n, &m);
for (int i=0; i!=m; ++i) {
int u=0, s=0;
scanf("%d%d",&u, &s);

if (A[s][u] == 1) {
printf("No answer");
return 0;
}//判断环
if (!(A[u][s] == 1)) {
A[u][s] = 1;
num[s] ++;//判断重边
}
}//读入,使用邻接矩阵储存,用数组(队列或优先队列)储存点的入度

solve();

/*fclose(stdin);
fclose(stdout);*/
return 0;
}

【优化,O(n+e)算法】

由于我们知道,当我们确定某一个点vi时,需要删除与之相关的边,然后与之相关的点的入度都减1,那么下一个入度为0的点,一定是删除边前入度为1的点,即该点一定是与vi相邻的。因此,我们可以再搜索边时,寻找入度为0(删边后)的点,将其储存在队列中。那么在搜索入度为0的点时,直接用队列中的元素。(程序见附录)

在搜索边的方面,我们一般是判断每个点与vi是否相连,再进行下去,但会造成对于不必要的边的搜索。其实,我们用邻接表的方法,可以轻松解决这一问题(请教老师关于邻接表的实现方法)。

【应用】

拓扑排序应用极其广泛。特别是在工业生产方面,通过拓扑排序,我们可以得到每个生产任务的先后顺序,从而达到生产效率最大化的效果。

在数学方面,拓扑学这一数学学科,也在慢慢地展现其独特的魅力。

而在OI方面,拓扑排序可以将一个图转化成一条序列,在某些方面,会起到意想不到的效果

【附录】

Poj2367

2367 – Genealogical tree

其实本题就是一道裸题,注意输入输出即可。,

程序如下(有瑕疵,请帮助找错,谢谢):

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
#include <cstdio>
#include <queue>
using namespace std;

#define maxn 105

int A[maxn][maxn], n;
int num[maxn];
queue <int > pos;

void solve() {
for (int i=1; i<=n; i++)
if (num[i] == 0) {
pos.push(i);
break;
}

for (int t=0; t!=n; ++t) {
int res=pos.front();
pos.pop();
printf("%d ", res);

for (int u=1; u<=n; u++)
if (A[res][u] == 1 && (--num[u]) == 0){
pos.push(u);
//printf("*%d* ", u);
}
}

printf("\n");
}

int main() {
scanf("%d", &n);
for (int i=1; i<=n; i++) {
int x=0;
for (; ;) {
scanf("%d", &x);
if (x==0) break;
else {
A[i][x] = 1;
num[x] ++;
}
}
}

solve();

system("pause");
return 0;
}

喜欢的,赞一个哦哦!!^–^

Topological sort, to some extant, we have met it in primary school.For example, there are four numbers,a b c d, and a>c ,a>d,

Thank you so much.