判断有向图 环是否存在环的2种方法（深度遍历

来源：蜘蛛抓取(WebSpider) 时间：2018-06-21 07:59 标签： java 有向图 环
//有向图判断是否有环
#include &iostream&
#include &list&
#include &vector&
#include &algorithm&
#define TRUE
#define FALSE 0
typedef struct{
int vexs[10];
int edges[10][10];
void CreateGraphM(MGraph *G){
int N1,N2;
int i,j,k;
cout&&"Enter the number of vertexs and edges: "&&
cin&&(G-&n)&&(G-&e);
for(i=0;i&k;i++)
cin&&(G-&vexs[i]);
for(i=0;i&G-&n;i++)
for(j=0;j&G-&n;j++)
G-&edges[i][j]=0;
cout&&"EDGES: "&&
for(k=0;k&G-&e;k++){
cin&&N1&&N2;
G-&edges[N1-1][N2-1]=1;
typedef struct{
int visited[10];
int finishing_time[10];
int discovery_time[10];
}DFS_DATA;
void DFSM(MGraph *G,int index,DFS_DATA *DATA){
DATA-&times++;
DATA-&discovery_time[index]=DATA-&
DATA-&visited[index]=1;
for(int i=0;i&G-&n;i++)
if(G-&edges[index][i]==1 && DATA-&visited[i]==0){
DFSM(G,i,DATA);
DATA-&finishing_time[index]=DATA-&
DATA-&times++;
void DFS(MGraph *G,DFS_DATA *DATA){
for(int i=0;i&G-&n;i++){
DATA-&visited[i]=0;
for(int i=0;i&G-&n;i++){
DATA-&finishing_time[i]=0;
DATA-&discovery_time[i]=0;
DATA-&times=0;
for(int i=0;i&G-&n;i++){
if(DATA-&visited[i]==0)
DFSM(G,i,DATA);
vector&int& Topological_Sort(MGraph *G){
DFS_DATA *DATA = new DFS_DATA;
vector&int& RESULT;
vector&int&
DFS(G,DATA);
for(int i=0;i&G-&n;i++)
tmp.push_back(DATA-&finishing_time[i]);
sort(tmp.begin(),tmp.end());
for(int i=G-&n-1;i&=0;i--)
for(int j=0;j&G-&n;j++)
if(DATA-&finishing_time[j]==tmp[i]){
RESULT.push_back(j);
delete DATA;
return RESULT;
int Acyclic(MGraph *G){
vector&int& CHECK;
CHECK = Topological_Sort(G);
for(int i=1;i&G-&n;i++)
for(int j=0;j&i;j++){
if(G-&edges[CHECK[i]][CHECK[j]]==1)
int main()
MGraph *G = new MG
CreateGraphM(G);
if(Acyclic(G)==1)
cout&&"There is Acyclic"&&
cout&&"There is NO Acyclic"&&
先用DFS对图G拓扑排序 然后看 拓扑排序的结果有没冲突& 就是 后面的顶点 要是有对前面顶点的边& 有冲突 就表示有环
浏览: 8909 次
来自: 上海
(window.slotbydup=window.slotbydup || []).push({
id: '4773203',
container: s,
size: '200,200',
display: 'inlay-fix'判断有向图是否存在环、环的个数、环的元素
判断有向图是否有环有三种方法：拓扑排序、深度遍历+回溯、深度遍历 + 判断后退边
这里使用&拓扑排序&和&深度遍历 + 回溯判断是不是环。使用&深度遍历 + 判断后退边找出环个数 以及环中元素
1、拓扑排序
思想：找入度为0的顶点，输出顶点，删除出边。循环到无顶点输出。
若：输出所有顶点，则课拓扑排序，无环；反之，则不能拓扑排序，有环
使用：可以使用拓扑排序为有向无环图每一个结点进行编号，拓扑排序输出的顺序可以为编号顺序
2、深度遍历 + 回溯
思想：用回溯法,遍历时，如果遇到了之前访问过的结点，则图中存在环。
结果测试：
3、深度遍历 + 判断后退边
思想：用DFS（深度优先遍历）,判断是否有后退边，若有，则存在环
具体来说，在遍历顶点的每一条边时，判断一下这个边的顶点是不是在栈中，如果在栈中，说明之前已经访问过了，这里再次访问，说明有环存在
判断后退边时，借助一个栈和一个数组
栈：即可以用来输出环
数组：inStack判断是否在栈中
结果测试：
没有更多推荐了，
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！如何判断一个有向图中是否存在一个环，并求出这个环？
[问题点数：20分，结帖人BinaryTreeEx]
本版专家分：609
CSDN今日推荐
本版专家分：0
2007年12月 专题开发/技术/项目大版内专家分月排行榜第一2007年6月 专题开发/技术/项目大版内专家分月排行榜第一2007年5月 专题开发/技术/项目大版内专家分月排行榜第一
2007年10月 专题开发/技术/项目大版内专家分月排行榜第二
结帖率 96.15%
本版专家分：609
本版专家分：0
本版专家分：0
本版专家分：0
本版专家分：609
本版专家分：2768
2002年1月 专题开发/技术/项目大版内专家分月排行榜第二
本版专家分：0
本版专家分：0
本版专家分：0
本版专家分：0
本版专家分：0
本版专家分：0
本版专家分：609
本版专家分：101
本版专家分：0
本版专家分：1
本版专家分：101
本版专家分：101
本版专家分：2768
2002年1月 专题开发/技术/项目大版内专家分月排行榜第二
本版专家分：609
本版专家分：2768
2002年1月 专题开发/技术/项目大版内专家分月排行榜第二
本版专家分：0
本版专家分：0
本版专家分：1475
本版专家分：0
结帖率 80%
本版专家分：19
本版专家分：0
本版专家分：0
本版专家分：0
本版专家分：0
本版专家分：0
匿名用户不能发表回复！|【算法求助】如何快速判断有向图中是否有负环？_noip吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：22,505贴子：
【算法求助】如何快速判断有向图中是否有负环？收藏
蒟蒻刚做了一道差分约束系统的题，其中n=100000, m=300000如果直接用SPFA求最短路，对于无解的情况我们必须在某个点入队n次后才能判断出来，明显TLE蒟蒻本打算在网上查资料研究，但找到的算法都是没有比O(nm)更优的（有一个DFS型SPFA，宣称能很好解决负环问题，但蒟蒻感情上不能接受这种算法——蒟蒻用DFS型SPFA做过实验，在绝大多数情况下要比朴素SPFA慢10倍）。神犇们是怎么解决这个问题的？
用递归的Spfa即可。SCOI2011 糖果就是这样的题，随便搜个题解就懂了
其实我想知道有没有O(n+m)的基于遍历的算法找出负环
回3.1楼：我最开始也想过这种方法，但被我们同学举出反例了：图中红边为DFS树；如果从4走到5了，若x=5，y=3，那么sum[5]-sum[3]+w(5-&3)表示的是什么呢？
将dis[]初始化为0，从每个点开始，只搜dis[u]+w[u][v]&dis[v]的v点，这样路径上一定是负权，如果碰到之前访问过的了，那肯定是负权回路。
楼上好方法
可以增加一个数组cnt，记录每个节点所在的路径被改短的次数，如果cnt[i]&n-1（n为节点个数），就说明有多余的节点路径优化，就能证明存在负环（从Dijstra算法发展来的）
登录百度帐号百度题库旨在为考生提供高效的智能备考服务，全面覆盖中小学财会类、建筑工程、职业资格、医卫类、计算机类等领域。拥有优质丰富的学习资料和备考全阶段的高效服务，助您不断前行！
京ICP证号&&
京网文[3号&&
Copyright (C) 2018 Baidu

我要回帖

更多关于 java 有向图 环 的文章

 

随机推荐