博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
拓扑排序的实现DFS
阅读量:5056 次
发布时间:2019-06-12

本文共 947 字,大约阅读时间需要 3 分钟。

缺点:当图有环的时候,是准确的

原理:

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;

}

转载于:https://www.cnblogs.com/zhanglanyun/archive/2012/05/01/2477945.html

你可能感兴趣的文章
web.xml配置详解
查看>>
geolocation
查看>>
【2008-6】【拼正方形】
查看>>
java 类装载和初始化顺序
查看>>
[UWP 自定义控件]了解模板化控件(8):ItemsControl
查看>>
ecshop偶尔读不出来配置文件
查看>>
sort对二维字符数组排序(转)
查看>>
shiro的sessionManager类继承结构及主要类方法
查看>>
linux常用命令大全
查看>>
Group_Concat函数示例
查看>>
ZOJ 3209 Treasure Map (DLX精确覆盖)
查看>>
使用python实现简单爬虫
查看>>
hbuilder mui调用系统裁剪图片、头像裁剪-Android
查看>>
Nuxt使用iconfont矢量图标
查看>>
IE6图片透明问题
查看>>
40个Android问题
查看>>
项目质量管理三角形
查看>>
获取32位随机码(uuid)的方法
查看>>
linux内核 同步
查看>>
wamp2.4.4 如何配置虚拟主机及反向代理(解决跨域问题)
查看>>