拓扑排序

一.概念

　　由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

二.拓扑排序方法如下:
　　(1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.
　　(2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.
　　(3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止.

三.算法实现

　　1.普通实现

 1 #include<iostream>
 2  #include<stdlib.h>
 3  #include<stdio.h>
 4  #define MAX 100
 5  using namespace 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      //while(1);
55      return 0;
56  }
57  
58  
59  //http://www.cnblogs.com/dolphin0520/archive/2011/04/16/2017737.html

递归实现：

int c[maxn];
 int topo[maxn],t;
 
 bool dfs(int u)
 {
    c[u]=-1;//正在访问该顶点
    for(int v=0; v<n; v++)
    {
        if(G[u][v]==1)
        {
             if(c[v]<0) return false;//存在环   
             //c[v]=-1代表正在访问该定点（即递归调用dfs(u)正在帧栈中，尚未返回）
             else if(!c[v] && !dfs(v))   return false;   
             //（c[v]==0 && dfs(v)==false即当前顶点没有后继顶点时
 
        }
    }
 
    c[u]=1;      //访问结束
    topo[--t]=u;
    return true;
 }
 
 bool toposort()
 {
     t=n;    
     memset(c,0,sizeof(c));
         
     for(int u=0; u<n; u++)    
         if(!c[u]) 
             if(!dfs())  
                 return false;    
     return ture;
 }