如何判断有向图中是否存在环路?

如何判断有向图中是否存在环路?输入的格式是有向图的边,而不是邻接矩阵,又该怎么做呢?用Java或者C#可以实现么?

0

2个回答

http://blog.sina.com.cn/s/blog_4513dde60100o6uk.html
这种有向图的表示法使用字典(Dictionary)和列表(List)。例如一个如下的有向图
这里往下看

0

你可以把有向图的边转换为字典或者邻接矩阵

0
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
判断有向图中是否存在环
方法概要:rnnodeset_dst[i][k][ ]表示i节点经过K跳可达节点集合;rn步骤1:从0跳(节点自身)开始根据邻接矩阵逐跳添加节点:即如果节点i经过k-1跳可达节点m,且m存在到n的有向边;则i经过k跳可达n(注意处理i到n的其他更短路径),将n添加到nodeset_dst[i][k][ ]数组中;并将nodeset_map[i][n]低4bit置1,表示n在i的可达目的节点集合中,
python判断在有向图中,是否存在环
 记录学习python的过程nnnimport numpynfrom numpy import *ndef dfs(v):n vis[v] = -1n flag = 0n for i in range(n):n # print(v,i)n # print (a[v][i],'---', vis[i] )n if a[v][i] != 0 ...
java 求一个有向图中的环路问题
java 求有向图中的环路问题,打印出所有的环路,用深度遍历搜索做的
Python 判断 有向图 是否有环
import numpynfrom numpy import *ndef dfs( v ):n vis[v] = -1n flag = 0n for i in range(n):n # print (a[v][i],'---', vis[i] )n if a[v][i] != 0 and vis[i] != -1:n dfs(i
用dfs判断一个有向图是否有环
解决这个问题的算法的思路是对一个节点u进行dfs,判断是否能从u回到自己这个节点,即是否存在从u到u的回路。 我们可以用一个color数组代表每个结点的状态,-1代表还没被访问,0代表正在被访问,1代表访问结束如果一个状态为“0”的结点,与他相连的结点状态也为“0”的话就代表有环,这个可以用dfs实现#include n#include n#include nnusing namespace st
用深度遍历dfs判断一个有向图是否有环
这里有一个无向图的深度遍历算法,无向图 深度优先遍历 c语言实现, 有向图的DFS遍历跟这个算法一样。 n利用DFS判断一个有向图是否有环的思路是:对一个节点v进行深度遍历,判断是否能从v到达自己这个节点,即是否存在从v到v的环路。 n在图的深度遍历中,我们将图中每个节点设置为三个状态:-1,0,1,分别表示还没发现的节点;已经发现但是还没处理完的节点;已经处理完的节点。对应上述思路,假设我们正在处
判断有向图是否有环
要想对一副有向图进行拓扑排序,必须要保证有向图是无环的,那么我们如何判断图是否含有环呢?我们可以使用深度优先搜索来遍历图,并创建一个数组来标记顶点是否已经在递归栈中,这样,当一个顶点指向的顶点已经在递归栈中,说明存在一个环,使用一个数组来记录当前遍历节点的上一个节点,这样就能得到这个环中的所有节点了。 n有向环的API npublic calss DirectedCycle n ...
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路
假设以邻接矩阵作为图的存储结构,编写算法判别在给定的有向图中是否存在一个简单有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)。(注:图中不存在顶点到自己的弧)
并查集——检查图中是否有环
题目链接:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1645n题意:每次输入一对数字,(两个数字不相等,不输入重复对),当有若干个数字对中含有的数字种类和总的数字的对数相等时候,爆炸,这时拒绝输入这一对数字,当输入单个-1时输出拒绝的次数
判断有向图是否存在环的2种方法(深度遍历,拓扑排序)
此题是美团2017春招实习生在线笔试题,题目是“如何判断有向图有没有回路”,这里给出两种解法以供参考。解法一:深度遍历假设图以邻接矩阵表示,一条深度遍历路线中如果有结点被第二次访问到,那么有环。我们用一个变量来标记某结点的访问状态(未访问,访问过,其后结点都被访问过),然后判断每一个结点的深度遍历路线即可。 rn因为采用邻接矩阵存储,一般至少需要将矩阵中元素的一半给过一下,由于矩阵元素个数为n^2,因
判断无向图/有向图中是否存在环
本文主要针对如何判断有向图/无向图中是否存在环的问题进行简单的论述。nn一 无向图nn1.利用DFS进行判断nn利用DFS判断有向图是否存在环,是最为常用的一种方法,虽然这种方法很常用,但可参考的代码的实现比较少,下面对这种方法及其实现进行详细的阐述。nn首先,利用DFS判断无向图中是否换的原理是:若在深度优先搜索的过程中遇到回边(即指向已经访问过的顶点的边),则必定存在环。nn所以说,是否存在环...
拓扑排序判断有向图是否成环
    对一个有向图的节点进行拓扑排序,可以用来判断该有向图是否成环,有环则无拓扑序列,无环则有。    #include <cstdio>n#include <cstring>n#include<iostream>n#include <queue>nusing namespace std;nconst int maxn = 1e5 + 7;nnin...
BFS为啥无法判断有向图是否有环以及DFS如何判断?
-
有向图中是否存在环
判别在用邻接表存储的有向图中是否存在环路。
有向图闭环检测值java代码实现
本文有向图闭环检测算法和实现由文章《如何检测节点网络中是否存在闭环之java实现》中的无向图闭环检测算法的基础上修改得到,其中修改点如下:n1.修改了数据结构,在原来无向图闭环检测算法的数据结构的基础上,增加了"isFrozen"和"isRoot"属性;其中"isFrozen"属性用于员无向图闭环检测算法中,在多父节点的场景下,由于相同的子节点要遍历两次而造成闭环检测判断的逻辑性错……
判断有向图是否有环及拓扑排序
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。n一个较大的工程往往被划分成许多子工程,我们把这些子工程称作活动(activity)。在整个工
python判断无向图环是否存在
 暂时是一个手动设置无向图中的边,用一个二维数组表示,后面会改进为用户自己定义无向图的边。nn学习python的新手,若大佬有解决的办法,希望不吝赐教nnn#无向图判断环是否存在ndef dfs(u,fa):n for i in range(v):n n=g[u][i]#n为图中的顶点数n # print(u,n,fa,i,'')n if n in ...
判断给定有向图是否存在回路 swustoj
判断给定有向图是否存在回路 1000(ms) 10000(kb) 1465 / 3415Tags: 图判断给定有向图是否存在回路。输入第一行为图中顶点的个数n; 第二行为途中弧度条数e;n第二行为顶点信息;接着e行为e条弧依附的两个顶点。输出该图是否存在回路,是输出yes;,不是输出no。样例输入4n4nA B C DnA BnA CnB DnC D样例输出no#include<iostre...
有向图_拓扑排序_AOE关键路径_判断图中是否存在环
目录nn0.图——判环nn0.1.1无向图判断是否存在环nn0.1.2有向图判断是否存在环nn0.2无向图判环nn0.3有向图判环nn1.有向图的拓扑排序nn2.关键路径nn 2.1.邻接链表存储AOE网nn 2.1.1拓扑排序: bool TopologicalOrder():nn2.1.2关键路径:bool CriticalPath()nn求关键路径的完整代码与测试用例:nn无向图、有向图判环...
有向图与无向图判断有环
最近开始认真学习算法,用的是Sedgewick的《Algorithms》.很多内容都与数据结构相同,不同的是对算法的内容更多的讲解.我会经常记录自己学习算法时遇到的困难和如何解决困难.n在学习拓扑排序的时候遇到了判断存在环的问题.而判断环问题又分为有向图与无向图,我会分别对无向图和有向图判断环问题进行阐述,然后比较他们之间的不同.n首先介绍一下无向图,无向图的边没有方向,或者说每一条无向图的边都是双
Java版查找并打印有向图中的所有环路径
最近想写一个识别线程死锁的算法,在网上找了半天没有合适的代码,自己写了个查找有向图中的环的代码(可以将死锁的资源依赖建模成含环的有向图)。本代码经过充分测试,内部有详细说明,最近自己的积分不够用,特标高价拿出来分享,可以放心下载。
对有向图的环的判定,并且输出图中所有的路径 C++算法
说明:我们选择的图是有向图,图的存储方式是邻接矩阵,使用C++语言,基于vs2010平台rn算法思想:逐个对图中的出度不为0的点进行遍历。假如是先对图A节点进行遍历:首先,将A节点所连接的点存储在数组vect1中,然后对A节点进栈,并对A节点的连接点进行深度优先。当节点的出度为0时,出栈,出栈的时候判断该节点是不是在vec1中的元素,如果是则为环,若不是则不是环。rnrnrn 代码:rn#incl
关于一个图中是否存在负环(更新版)
负环的判断nnn第一次写博客,表示心里很慌nn我第一次接触负环的判断是在一道差分约束的题目里:点击打开链接nn以下为假算法nn说实话,这道题目其实是比较裸的判负环,但是很多人就卡在负环上,有的人会用dijkstra算法(因为dij的原理是贪心,当有负权环的时候它的贪心策略就不成立了,所以不行),有的人用SPFA,但是用的BFS,于是。。。光荣的TLE了,原因就在于在判断以及之后的退出上DFS比BF...
Matlab 有向有环图 所有回路非回路查询 最大环路查询
1.查看拓扑结构 mat文件为邻接矩阵n%%n% ShuanHolmes@outlook.comn% 有向图绘制 拓扑情况n%%n%close all;nclear;nclc;nn% load('wMatTree.mat');n% load('woutMat.mat');nload('wMatWsparity.mat');nnW = full(W);nW = W';n% W = [W Wout'
判断给定有向图是否存在回路
判断给定有向图是否存在回路。输入第一行为图中顶点的个数n; 第二行为途中弧度条数e; 第二行为顶点信息;接着e行为e条弧依附的两个顶点。输出该图是否存在回路,是输出yes;,不是输出no。样例输入4 4A B C D A B A C B D C D样例输出no#include<iostream>nusing namespace std;n#define maxsize 100nint ...
有向图中有向环检测
背景假如有三个存在优先级的任务x、y及z,x要在y之前完成,y要在z之前完成,而z又要在x之前完成,那该问题一定是无解的。寻找有向图中是否存在有向环是判定一个任务优先级问题的前提边的类型从某个点开始的深度搜索过程中遇到了后向边,可作为找到有向环的标志代码实现private boolean[] onStack = new boolean[V];public void dfs(int s) {
并查集(判断环路)
并查集是非常常用的一种数据结构,用于把数据按照规则整理成集合,集合最终呈现为树状结构,以根节点作为不同集合的区分标志,实现方面主要涉及查找和合并,代码如下nnn//查找nint find(int x)n{n int r=x;n while(pre[r]!=r)n r=pre[r];//找到他的前导结点n int i=x,j;n while(i!=r)//路径压缩算法n...
有向图检测环——普通方法、着色法
Detect Cycle in a Directed Graphnnnn未优化nn n给定有向图如上,环是[1,3,4]。 n思路:分别对每个点进行深度遍历,在遍历的过程中,一旦发现当前要存入的元素已经在祖先数组中时,就发现环了,此时打印。当没有打印结果时就代表没有环。nnfrom collections import defaultdictnd = defaultdict(list)#默认值为l...
DFS应用——遍历有向图+判断有向图是否有圈
【0】README0.1) 本文总结于 数据结构与算法分析, 源代码均为原创, 旨在 理解 “DFS应用——遍历有向图+判断有向图是否有圈” 的idea 并用源代码加以实现 ; n0.2) 判断有向图是否有圈的rule—— 一个有向图是无圈图当且仅当它没有背向边,背向边定义,参见: http://blog.csdn.net/pacosonswjtu/article/details/49967255
(c++)数据结构与算法之图:Dijkstra、Floyd算法、判断有向图回路
//带权有向图的最短路径算法:Dijkstra、Floyd(结果和输出分开)n//判断在给定有向图中是否存在一个有向回路nn#includen#include n#define MAXE 100n#define MAXV 15n#define MAXWEIGHT 1000n#define INF 1000nusing namespace std;nclass graphn{nprivate:n
判断一个有向图中是否存在回路,并进行输出(拓扑算法)
判断一个有向图中是否存在回路,并进行输出(拓扑算法)
数据结构实验之图论十:判断给定图是否存在合法拓扑序列---bfs判断又向图的无环问题
Problem Descriptionrnrn给定一个有向图,判断该有向图是否存在一个合法的拓扑序列。rnInputrnrn输入包含多组,每组格式如下。rn第一行包含两个整数n,m,分别代表该有向图的顶点数和边数。(nrn后面m行每行两个整数a b,表示从a到b有一条有向边。rnrnOutputrnrn若给定有向图存在合法拓扑序列,则输出YES;否则输出NO。rnrnExample Inputrn
深度优先搜索输出有向图中的所有环(JAVA)
如图:求出有向图的所有环。rn[img]http://dl.iteye.com/upload/attachment/0076/2311/5f987942-21b0-33b0-b0df-e9b62b9d7c65.gif[/img]rnrn[code="java"]import java.util.ArrayList;rnimport java.util.Arrays;rnpublic class T...
java实现寻找有向图的的闭环
最近在公司与遇到一个需求,将所有服务关系的依赖中找出闭环依赖,大概意思就是把有向图的闭环路径找出来,我用深度优先搜索(DFS)进行实现,现将代码贡献出来供大家参考:nnpublic class DsfCycle {nn /**n * 限制node最大数n */n private static int MAX_NODE_COUNT = 100; nn /**n ...
有向图的边存在判断
假设有向图G采用邻接矩阵存储,判断图G中是否存在边。输入第一行第一个整数n表示顶点的个数(顶点编号为0到n-1),第二行表示顶点i和j,接下来是为一个n*n大小的整数矩阵,表示图的邻接关系。数字为0表示不邻接,1表示不邻接。输出yes(存在),no(不存在)。样例输入5 0 2 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0样例输出no#incl...
有向图中两个结点之间是否存在一条路径
给定有向图,设计一个算法,找出两个结点之间是否存在一条路径rnrnrnpublic enum Statern{rnUnvisited,Visited,Visiting;rn}rnpublic  static boolean search(Graph g,Node start ,NLinkedListrn{rn//当作队列使用rnLinkedList q=new LinkedList();rnfor
邻接表 有向图 是否有环 C实现 (dfs - 反向边)
有向图 利用 有无反向边 判断有无环
有向图两顶点间是否存在路径
1.     试基于图的深度优先搜索策略编写一程序,判别以邻接表方式存储的有向图中是否存在有顶点Vi到Vj顶点的路径(i≠j)。rn rn#includernusingnamespacestd;rnconstintN = 100;rn#includernvectorint>data[N];rnboolflag[N];rnboolres= rntrue;rnvoiddfs(intstart,inte
判断list是否存在环
给出如下结构:nstruct noden{nstruct *next;n};ntypedef stuct node Node;n nbool getCycle(){nNode* temp1 = head;//(假设head就是这个链表的头)nNode* temp2 = head;nwhile(head->next!=NULL)n{ntemp1 = temp1->next;/
easy sssp(spfa判断负环)
easy sssp描述: n输入数据给出一个有N(2 <= N <= 1,000)个节点,M(M <= 100,000)条边的带权有向图. n要求你写一个程序, 判断这个有向图中是否存在负权回路. 如果从一个点沿着某条路径出发, 又回到了自己, 而且所经过的边上的权和小于0, 就说这条路是一个负权回路. n如果存在负权回路, 只输出一行-1; n如果不存在负权回路, 再求出一个点S(1 <= S
文章热词 机器学习教程 Objective-C培训 交互设计视频教程 颜色模型 设计制作学习
相关热词 mysql关联查询两次本表 native底部 react extjs glyph 图标 乌班图中如何退出python java学习 存在的问题