关于拓扑排序

在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（Topological sorting）。

  • 每个顶点出现且只出现一次；
  • 若A在序列中排在B的前面，则在图中不存在从B到A的路径。

也可以定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得如果存在一条从顶点A到顶点B的路径，那么在排序中B出现在A的后面。

在一个有向图中，对所有的节点进行排序，要求没有一个节点指向它前面的节点。

先统计所有节点的入度，对于入度为0的节点就可以分离出来，然后把这个节点指向的节点的入度减一。

一直做改操作，直到所有的节点都被分离出来。

如果最后不存在入度为0的节点，那就说明有环，不存在拓扑排序，也就是很多题目的无解的情况。

C语言实现

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<stdio.h>

// 最大顶点数
#define N 10

// 简单实现栈  
void initstack(int*stack,int*n)  
{  
    for(int i=0;i<*n+1;i++)  
        stack[i]=-1;  
    *n=0;
}  
void push(int*stack,int *n,int elem)  
{  
    stack[*n]=elem;  
    (*n)++;       
}  
int pop(int*stack,int *n)  
{  
    int temp;  
    (*n)--;  
    temp=stack[*n] ;  
    stack[*n]=-1;  
    return temp;     
}  
int isempty(int*stack,int *n)  
{  
    if(*n)  
       return 0;  
    return 1;      
}  

// 拓扑排序函数
// 二维数组第二维给出大小  archnum边数
void Topologicalsort(int matrix[][N], int vexnum)  
{  
    //入度矩阵   
    int indegree[N]={0};
    //存放最后的拓扑排序 的序列  
    int sortorder[N]={0}; 
    int sortordercurse=0;  
    int stack[N+1];  
    int curse=N+1;  
    initstack(stack,&curse);  
    //用来指示入度为0的顶点个数 
    int count=0; 
    for(int j=0;j<vexnum;j++){  
        for(int i=0;i<vexnum;i++)
            indegree[j]+=matrix[i][j];  
        if(!(indegree[j]))  
            //入度为0的顶点入栈     
            push(stack,&curse,j); 
    } 
    while(!(isempty(stack,&curse))) {  
    int tp;  
    tp=pop(stack,&curse);  
    sortorder[sortordercurse++]=tp;   
    count++;  
    for(int i=0;i<vexnum;i++){  
            if((indegree[i]==1)&&(matrix[tp][i]==1))  
            push(stack,&curse,i);  
            //对出栈的顶点所指向的顶点减一 ，并且将入度为0的顶点入栈。   
            indegree[i]-=matrix[tp][i];
        }
    }
    // 如果
    if(count==vexnum){  
        printf("\n\n拓扑排序结果为:");  
        for(int i=0;i<sortordercurse;i++)  
            printf(" V%d ",sortorder[i]+1);}  
    else{
        printf("\n\n拓扑排序不存在\n");}                           
} 

/**
 * 如果图有环就不能拓扑排序
 * 拓扑排序:
 * 某个集合上的一个偏序得到的该集合上的一个全序的操作
 */
int main()  
{  
    /**
     * 
     * 文件输入 略
     * 参考第四题
     * 
     */

    // 顶点数
    int vexnum = 7;
    // 构建邻接矩阵
    int matrix[N][N]={{0,1,1,1,0,0,0},  
                    {0,0,0,0,1,0,0},  
                    {0,0,0,0,1,1,0},  
                    {0,0,0,0,0,1,0},  
                    {0,0,0,0,0,0,1},  
                    {0,0,0,0,0,0,1}};
    //打印矩阵   
    for(int i=0;i<N;i++){  
        for(int j=0;j<N;j++)  
            printf(" %d ",matrix[i][j]);  
            printf("\n");
        }
    Topologicalsort(matrix, 7);
    printf("\n\n");
    return 0;  
}