算法导论中的拓扑排序,觉得算法导论真的好强,这是利用DFS,记录各点完成访问的时刻(完成时间),用DFS遍历一次整个图,得出各结点的完成时间,然后按完成时间倒序排列就得到了图的拓扑序列,相比按结点的入度的贪心法的拓扑排序,我觉得DFS的拓扑比较好写

 

 

原理:

令f[u] , f[v]为 dag图上的任一结点u,v的完成时刻

若存在有向边<u,v> ,则 f[v] < f[u]    : u----->v  则 f[v] < f[u]

 

所以按完成时刻倒序排列即可

 

 

#include<iostream>

using namespace std;

 

int timef = 0;

 

int n ;

int a[1000][1000];// 图的邻接矩阵

 

int f[1000];  //完成时间

 

int vis[1000];  //1代表 被发现 2代表 已完成

 

 

 

void DFS(int u)

{

       vis[u] = 1;   //记录发现时刻

 

       for(int v=1; v<=n; v++) //adj(u)   //O(E)

              if(a[u][v] && vis[v]==0)

               DFS(v);

 

       Vis[u] = 2;  //记录完成时刻

       timef++;

       f[u] = timef;

}

 

void DFS_main()   //O(V+E)

{

       timef = 0;

 

       for(int i=1; i<=n; i++)             /// O(V)

       {

              if(vis[i] == 0)

                     DFS(i);

       }

}

 

 

void Topological_sort()      //O(V+E)

{

       int tp[1000];            ////存放拓扑序列1..V

       DFS_main();

 

       for(int i=1; i<=n; i++)   //按finish的时间倒序存放在tp序列tp中

        tp[n-f[i]+1] = i;

      

       for(int i=1; i<=n; i++)

              cout<<tp[i]<<" ";

       cout<<endl;

}

 

 

 

int main()

{

       memset(vis,0,sizeof(vis));

       cin>>n;

       for(int i=1; i<=n; i++)

              for(int j=1; j<=n; j++)

                     cin>>a[i][j];

      

       Topological_sort();

 

 

       system("pause");

       return 0;

}