缺点:当图有环的时候,是准确的
原理:
令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;
}