有关拓扑排序

拓扑排序

拓扑排序，是一种按照一定的先后规则，来进行排序。
一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序（来自百度百科）
简单来说，拓扑排序的规则，就像一棵技能树，要想点出某个技能，就要首先点出改技能的前置技能，然后才能将改技能点出。又或者想大家熟悉的大学选课系统一样，你必须先学过前导课程，才能更深入的学习其他过程。

排序实现思想：

首先，我们可以将某种先后关系抽象成一种有向图的关系（如a在b前面，可以构建出一条有向边，由a指向b），而且必须保证该图不存在环路（否则会出现矛盾）。当构建出图以后，可以根据边的关系给点附带度数（对无向图来说，连着n条边的节点有n个度,就是顶点连着一条线段就代表一个度，这里仅对边的终点增加度数）。
图和度数建立完成后，就要开始不断搜索度数为零的点，输出该点并减少该点指向点的度数。不断循环，直至输出所有点拓扑排序完成为止。

排序代码实现

1.暴力寻求

 1 #include<iostream>
 2 #include<stdlib.h>
 3 #include<stdio.h>
 4 #define MAX 100
 5 usingnamespace std;
 6 
 7 void toposort(int map[MAX][MAX],int indegree[MAX],int n)
 8 {
 9     int i,j,k;
10     for(i=0;i<n;i++) //遍历n次
11     {
12         for(j=0;j<n;j++) //找出入度为0的节点
13         {
14             if(indegree[j]==0)
15             {
16                 indegree[j]--;
17                 cout<<j<<endl;
18                 for(k=0;k<n;k++) //删除与该节点关联的边
19                 {
20                     if(map[j][k]==1)
21                     {
22                         indegree[k]--;
23                     }
24                 }
25                 break;
26             }
27         }
28     }
29 }
30 
31 
32 int main(void)
33 {
34     int n,m; //n:关联的边数，m:节点数
35     while(scanf("%d %d",&n,&m)==2&&n!=0)
36     {
37         int i;
38         int x,y;
39         int map[MAX][MAX]; //邻接矩阵
40         int indegree[MAX]; //入度
41         memset(map,0,sizeof(map));
42         memset(indegree,0,sizeof(indegree));
43         for(i=0;i<n;i++)
44         {
45             scanf("%d %d",&x,&y);
46             if(!map[x][y])
47             {
48                 map[x][y]=1;
49                 indegree[y]++;
50             }
51         }
52         toposort(map,indegree,m);
53     }
54     return0;
55 }

View Code

该代码来自于博客：
拓扑排序
这份代码的主要思想就是暴力求解，弱有n个顶点，就暴力搜索n次，每次找到一个度数为零的点，然后暴力搜索该点有关的边，继续暴力。
这份代码写起来简单方便，但是时间会比较慢。

2.（队列+ 邻接矩阵）优化拓扑排序

与前一份代码类似，不过运用了数据结构进行优化。
但是代码长度较前一份长，编写时间也会较长。

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <vector>
 6 #include <queue>
 7 using namespace std;
 8 vector<int> nodes[1010];
 9 int degress[1010];
10 int n;
11 queue<int> dequeue;
12 int cnt=0;
13 int num[1010];
14 void toposort()
15 {
16     while(!dequeue.empty())
17     {
18         int t=dequeue.front();
19         dequeue.pop();
20         num[cnt++]=t;
21         for(int i=0; i<nodes[t].size(); i++)
22         {
23             int h=nodes[t][i];
24             degress[h]--;
25             if(degress[h]==0)
26                 dequeue.push(h);
27         }
28     }
29 }
30 int main()
31 {
32     //int n;
33     cin>>n;
34     int a,b;
35     for(int i=1; i<=n; i++)
36     {
37         int t;
38         while(scanf("%d",&t)&&t)
39         {
40             degress[t]++;
41             nodes[i].push_back(t);
42         }
43     }
44     for(int i=1; i<=n; i++)
45         if(!degress[i])
46             dequeue.push(i);
47     toposort();
48     for(int i=0; i<n; i++)
49     {
50         if(i!=0)
51             cout<<" ";
52         cout<<num[i];
53     }
54     cout<<endl;
55     return 0;
56 }

View Code

此代码用于拓扑排序入门题目：poj2367

3.dfs回溯实现拓扑排序

核心代码：

 1 vector<int>g[N];//邻接表存储  
 2 int vis[N],topo[N],cnt;  
 3 
 4 bool dfs(int u)  
 5 {  
 6     vis[u] = -1;//-1用来表示顶点u正在访问  
 7     for(int i = 0 ; i < g[u].size() ; i ++)  
 8     {  
 9         if(vis[g[u][i]] == -1)//表示这个点进入了两次，肯定出现了环  
10             return false;  
11         else if(vis[g[u][i]] == 0)  
12         {  
13             dfs(g[u][i]);  
14         }  
15     }  
16     vis[u] = 1;  
17     topo[cnt++] = u;//放到结果数组里，输出的时候记得倒序输出，（回溯的原因）  
18     return true;  
19 }  
20 
21 bool toposort(int n)  
22 {  
23     memset(vis,0,sizeof(vis));  
24     for(int i = 1 ; i <= n ; i ++)  
25     {  
26         if(!vis[i])  
27         {  
28             if(!dfs(i)) return false;//huan  
29         }  
30     }  
31     return true;  
32 }

View Code

具体详见博文：Toposort（拓扑排序）——DFS递归回溯版