Qjbtiger's Home
0%

关于topological sort（拓扑排序）的一点感悟

Posted on Edited on In Views: Valine:

拓扑排序，从某种意义上说，我们在小学的时候，就早早已经接触了。例如：现在有四个数，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.