-
2022-02-28 22:09:10
使用深度优先遍历,若从有向图上的某个顶点u出发,在 DFS(u)结束之前出现一条从顶点v到u的边,由于v在生成树上是u的子孙,则图中必定存在包含u和v的环,因此深度优先遍历可以检测一个有向图是否有环。
拓扑排序时,当某顶点不为任何边的头时才能加入序列,存在环时环中的顶点一直是某条边的头
不能加入拓扑序列。也就是说,还存在无法找到下一个可以加入拓扑序列的顶点,则说明此图存在回路。关键路径能否判断一个图有环,则存在一些争议。关键路径本身虽然不允许有环,但求家关键路径的算法本身无法判断是否有环,判断是否有环是求关键路径拓扑排序。
所以这个问题的答案主要取决于你从哪个角度出发看问题
(ps:求最短路径是允许图有环的。)
更多相关内容 -
Python 判断 有向图 是否有环的实例讲解
2020-09-20 20:11:27下面小编就为大家分享一篇Python 判断 有向图 是否有环的实例讲解,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧 -
判断有向图是否有环
2021-03-15 02:40:32方法一:拓扑排序时间复杂度O(n^2)比较常用的是用拓扑排序来判断有向图中是否存在环。什么是拓扑排序呢?我们先定义一条u到v的边e=,u生成拓扑序列的算法就叫拓扑排序啦~算法流程描述while(节点个数次(N)循环)1.找出...方法一:拓扑排序
时间复杂度O(n^2)
比较常用的是用拓扑排序来判断有向图中是否存在环。
什么是拓扑排序呢?
我们先定义一条u到v的边e=,u
生成拓扑序列的算法就叫拓扑排序啦~
算法流程描述
while(节点个数次(N)循环)
1.找出入度为0的节点u(节点个数次(N)循环)
2.删去这个节点u和从这个节点出发相连的边(,....,),更新这些边连的点(v1,v2,v3....vn)的入度信息。
3.直到找不到入度为0的点(要是图里节点删完了(循环了N次)就是没环,还剩节点就有环)。
代码
#include
#include
using namespace std;
#define MAXN 1000
int n, m;
vector G[MAXN];
vector topo;//存拓扑排序的序列
void read_graph()
{
cin >> n >> m;;
int u, v;//不带边权的图
for (int e = 0; e < m; e++) {//有多少条边
cin >> u >> v;
G[u].push_back(v);//有向图
}
}
bool topoSort()
{
int indgree[MAXN] = { 0 };//入度信息
int visit[MAXN] = { 0 };
for (int i = 0; i < n; i++) {//初始化入度信息
for (int j = 0; j < G[i].size(); j++) {
indgree[G[i][j]]++;
}
}
int control=0;
while (control < n) {
int u = 0,i;
//找到入度为0的点
for (i=0; i < n; i++) {
if (!visit[i] && indgree[i] == 0) {
u = i;
break;
}
}
if (i == n) {//找不到入度为0的点退出循环
return false;
}
visit[u] = 1;//标记访问过
topo.push_back(u);
for (int j = 0; j < G[u].size(); j++) {//更新入度信息
indgree[G[u][j]]--;
}
control++;
}
return true;//control=n 说明n个点都存入拓扑排序里,是无环的
}
int main()
{
read_graph();
for (int i = 0; i < n; i++) {
cout << i<
for (int j = 0; j < G[i].size(); j++) {
cout << G[i][j] << " ";
}
cout << endl;
}
if (topoSort()) {
for (int i = 0; i < topo.size(); i++) {
cout << topo[i] << " ";
}
}
else {
cout << "there exist circle" << endl;
}
}
上面这个复杂度要O(n^2)
看到用栈可以简化到O(n+e); //链接
其实就是在找入度为0点的步骤那里做优化:
把入度为0的点入栈;
当栈不为空时,更新栈顶节点连接顶点的入度信息,如果为0入栈
个人理解:和BFS的模板格式有点像,一层一层的搜索,这里用栈替代了上面代码的visit数组,因为只对栈里的元素做操作,自然是未访问过的
DFS
时间复杂度O(V+E)
用两个bool数组visited[]和recStack[]来记录对节点 的访问和入栈
- isCyclicUnit(int v) ----以v起点是否有环
- isCycle(int n) ----遍历n 个节点,调用isCyclicUnit(i)
-
判断给定的图是不是有向无环图实例代码
2020-09-05 09:19:15判断给定的图是不是是有向无环图,方法是应用拓扑排序,代码如下 -
有向图找环的java程序
2020-05-03 10:58:15有向图寻找环,java语言,文件读入为两个节点之间进行连接的数据,输出为长度为3到7的收尾相连的链,多次使用arraylist运行速度较慢。 -
Java判断无向图中是否存在环
2020-12-21 17:00:23第一次写博客,不太会用,话不多说 直接上代码 详细可以看注释,无向图判断是否存在环比有向图相对复杂一点 ,需要判断访问的节点的临接表中的节点与父节点是否相同。 /** * @Description:判断无向图是否有环 深度... -
判断无向图/有向图中是否存在环
2021-01-15 02:38:00利用DFS进行判断利用DFS判断有向图是否存在环,是最为常用的一种方法,虽然这种方法很常用,但可参考的代码的实现比较少,下面对这种方法及其实现进行详细的阐述。首先,利用DFS判断无向图中是否换的原理是:若在...本文主要针对如何判断有向图/无向图中是否存在环的问题进行简单的论述。
一 无向图
1.利用DFS进行判断
利用DFS判断有向图是否存在环,是最为常用的一种方法,虽然这种方法很常用,但可参考的代码的实现比较少,下面对这种方法及其实现进行详细的阐述。
首先,利用DFS判断无向图中是否换的原理是:若在深度优先搜索的过程中遇到回边(即指向已经访问过的顶点的边),则必定存在环。
所以说,是否存在环的关键在于是否存在满足条件的“回边”,那么如何判断回边呢?
(1)首先,对图中的所有顶点定义三种状态:顶点未被访问过、顶点刚开始被访问、顶点被访问过并且其所有邻接点也被访问过。这三种状态,在visited数组中分别用0、1、2来表示。那么,存在环的情况可以定义为:在遍历过程中,发现某个顶点的一条边指向状态1的顶点,此时就存在环。状态2可以理解为其生成树上的所有的子孙节点都已经访问完。
(2)此外,我们要定义一个father数组,用以存储在DFS过程中顶点的父顶点(或者说是生成树上的父节点)。其主要作用是为了区分邻接点中环中的顶点和遍历过程中的父节点 (单纯的用visited数组无法区分)。
整个过程的实现代码如下:
#define MAX_NUM 100
#define INF 0x7fffffff
/*DFS判断无向图中是否有环*/
class Graph
{
public:
int vertexNum;//顶点个数
int arcNum;//弧的个数
int vertex[MAX_NUM];//顶点表
int arc[MAX_NUM][MAX_NUM];//弧信息表
};
int visited[MAX_NUM];//顶点访问表
int father[MAX_NUM];//父节点表
void DFS(int v,Graph G)
{
visited[v] = 1;
for(int i = 0 ; i < G.vertexNum; i++)
{
if(i != v && G.arc[v][i] != INF)//邻接矩阵中节点v的邻接点
{
if(visited[i] == 1 && father[v] != i)//vi不是父节点,而且还访问过(而且为状态1,说明不是回溯过来的顶点),说明存在环(判断i不是v的父节点)
{
cout<
int temp = v;
while(temp != i)
{
cout<
temp = father[temp];
}
cout<
}
else
if(visited[i] == 0)
{
father[i] = v;//更新father数组
DFS(i,G);
}
}
}
visited[v] = 2;//遍历完所有的邻接点才变为状态2
}
void DFSTraverse(Graph G)
{
memset(visited,0,sizeof(visited));
memset(father,-1,sizeof(father));
for(int i = 0 ; i < G.vertexNum; i++)
if(!visited[i])
DFS(i,G);
}
由此可见,visited数组相对于一般的情况,增加了个状态2,主要是为了防止在回溯过程中进行误判。所以才能仅用father数组和状态1判断存在环。
状态2可以理解为其生成树上的所有的子孙节点都已经访问完。
由于使用的是邻接矩阵来存储,所以该算法的时间复杂度为O(n^2),空间复杂度为O(n)。
2.其他方法本文不再详述。
二 有向图
1.拓扑排序
关于拓扑排序,资料很多,本文不再详述其原理,只给出其实现代码,代码如下:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define MAX_NUM 100
#define INF 0x7fffffff
/*拓扑排序*/
int indegree[MAX_NUM];//用以表示每个顶点的入度
bool visited[MAX_NUM];//用以表示该顶点是否入栈
class Graph
{
public:
int vertexNum;//顶点个数
int arcNum;//弧的个数
int vertex[MAX_NUM];//顶点表
int arc[MAX_NUM][MAX_NUM]= {{0,1,1},{INF,0,1},{INF,INF,0}}; //弧信息表
};
void Initindegree(Graph G)//初始化入度数组
{
memset(indegree,0,sizeof(indegree));
for(int i = 0; i < G.vertexNum; i++)
for(int j = 0; j < G.vertexNum; j++)
{
if(i != j && G.arc[i][j] != INF)
indegree[j]++;//注意此处增加的是顶点vj的入度
}
memset(visited,0,sizeof(visited));
}
bool TuoPu(Graph G)
{
stack s;
int cnt = 0;//用于记录拓扑序列中节点的个数
for(int i = 0 ; i < G.vertexNum; i++)
if(indegree[i] == 0)
{
s.push(i);
visited[i] = true;//修改入栈顶点的入栈标记数组
}
while(!s.empty())
{
int v = s.top();
cnt++;//顶点出栈得到时候,计数器加1
s.pop();
for(int i = 0; i < G.vertexNum; i++)
{
if(v != i && G.arc[v][i] != INF && visited[i] == false)//将所有顶点v的未入栈的邻接点的入度都减去1
{
indegree[i]--;
if(indegree[i] == 0)//如果减1后入度为0了,此时需要将该邻接点入栈,且修改入栈标记数组
{
visited[i] = true;
s.push(i);
}
}
}
}
return cnt == G.vertexNum ? true : false;
}
int main()
{
Graph G;
G.vertexNum = 3;
Initindegree(G);
cout<
}
2.利用改进的DFS
对于有向图的话,如果直接应用一般的DFS的话,会出现误判的情况,一个典型的例子是:A->B,A->C->B,我们用DFS来处理这个图,我们会得出它有环,但实际上并没有。然而,本文中所说的无向图的DFS判断算法完全可以直接应用到有向图中来,即上述代码可以直接应用到有向图中来。所以说上述的DFS算法(或称为为改进的DFS算法)既适用于无向图,也适用于有向图。其对应的原理适用于这两种图,即只要我们在遍历过程中,只要发现一个顶点不是当前节点的父节点,同时他还被访问过了(状态为1),那么就可以认为此处存在环。(通常在DFS中一个顶点的未被访问的邻接点,相当于生成树中的该顶点的子孙节点)
-
两种方式判断有向图是否有环-python实现
2019-09-27 20:40:31两种方式判断有向图是否有环-python实现 1. DFS判断有向图是否有环 假设图以邻接矩阵表示,一条深度遍历路线中如果有结点被第二次访问到,那么有环。我们用一个变量来标记某结点的访问状态(未访问,访问过,其后...1. DFS判断有向图是否有环
假设图以邻接矩阵表示,一条深度遍历路线中如果有结点被第二次访问到,那么有环。我们用一个变量来标记某结点的访问状态(未访问,访问过,其后结点都被访问过),然后判断每一个结点的深度遍历路线即可。
def dfs(G,i,color): r = len(G) color[i] = -1 have_circle = 0 for j in range(r): # 遍历当前节点i的所有邻居节点 if G[i][j] != 0: if color[j] == -1: have_circle = 1 elif color[j] == 0: have_circle = dfs(G,j,color) color[i] = 1 return have_circle def findcircle(G): # color = 0 该节点暂未访问 # color = -1 该节点访问了一次 # color = 1 该节点的所有孩子节点都已访问,就不会再对它做DFS了 r = len(G) color = [0] * r have_circle = 1 for i in range(r): # 遍历所有的节点 if color[i] == 0: have_circle = dfs(G,i,color) if have_circle == 0: break return have_circle G = [[0,1,0],[0,0,1],[1,0,0]] #这里的1说明行index对应的节点指向列index对应的节点,对角线处为0 # G = [[0,0,0,1,0],[1,0,0,0,0],[0,0,0,1,1],[0,0,0,0,0],[0,1,0,0,0]] have_circle = findcircle(G) print(have_circle)
2. 拓扑排序判断环
拓扑排序方法是重复寻找一个入度为0的顶点,将该顶点从图中删除(即放进一个队列里存着,这个队列的顺序就是最后的拓扑排序),并将该结点及其所有的出边从图中删除(即该结点指向的结点的入度减1,因为下面代码中有入度的都为1,所以直接赋值为0 即可),最终若图中全为入度为1的点,则这些点至少组成一个回路,或者最后的队列中节点个数不为中的个数,也说明有环。
def findcircle(G): node_set = set() r = len(G) have_in_zero = True while have_in_zero: have_in_zero = False for i in range(r): if i not in node_set and not any([row[i] for row in G]): node_set.add(i) G[i] = [0] * r have_in_zero = True break return False if len(node_set)==r else True G = [[0,1,0],[0,0,1],[1,0,0]] # G = [[0,0,0,1,0],[1,0,0,0,0],[0,0,0,1,1],[0,0,0,0,0],[0,1,0,0,0]] have_circle = findcircle(G) print(have_circle)
-
判断有向图是否存在环的2种方法(深度遍历,拓扑排序)
2017-09-16 11:01:22此题是美团2017春招实习生在线笔试题,题目是“如何判断有向图有没有回路”,这里给出两种解法以供参考。解法一:深度遍历假设图以邻接矩阵表示,一条深度遍历路线中如果有结点被第二次访问到,那么有环。我们用一个... -
python判断无向图环是否存在的示例
2020-09-18 10:11:07今天小编就为大家分享一篇python判断无向图环是否存在的示例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧 -
python DFS 判断有向图是否有环
2021-11-12 11:29:22DFS 判断有向图是否存在环 vis :DFS 遍历的结果 trace:也是遍历的结果,需要对结果进行分析,找到重复值时,判断重复值的索引位置,依次进行遍历,输出结果 程序 ## graph = { "a": ["b", "c"], "b": ["a", "d"]... -
图——判断有向图中是否有环
2020-12-04 09:38:551. 判断有向图中是否有环 给定有向图,检查该图是否包含循环。如果给定图包含至少一个循环,则函数应返回true,否则返回false。 1.1. 方法一:DFS 1.1.1. 思路 对一个图进行DFS, 则DFS的路径可以生成一个棵树。 ... -
Java 判断有向图是否有环 拓扑排序
2020-03-13 22:32:27拓扑排序,先从入度为0的顶点入手,之后若产生入度为0的顶点就不断加入队列 import java.util.*; public class Demo1{ public static void ... } } } /*方法一:遍历所有顶点,是否出度和入度都为0 * for(int i=1;i -
简单方法判断邻接矩阵的有向图是否有环
2020-04-06 10:09:20简单方法判断邻接矩阵的有向图是否有环求解思路实现代码如有不同见解,欢迎讨论 求解思路 1.统计所有节点的出度及其前序节点,初始化一个空的访问集合; 2.将出度为零的节点放入访问集合... * 判断有向图是否有环 ... -
无向图判断是否有环
2021-03-15 17:35:25//深度优先遍历图,当某个节点的子节点已经访问过,且该节点不是其父节点,肯定存在环#include #include #include using namespace std;bool dfs(vector >&graph, vector&visited,int father,int &... -
判断有向图中是否存在环
2009-06-28 15:30:30判断有向图中是否存在环,用邻接表做存储结构 -
拓扑排序判断有向图中是否有环
2022-02-24 14:10:31拓扑排序是对一个有向图构造拓扑序列,解决工程是否能顺利进行的问题。构造时有222种结果: 此图全部顶点被输出:说明说明图中无「环」存在, 是 AOV 网(有向无环图) 没有输出全部顶点:说明图中有「环」存在,... -
判断有向图是否存在环
2018-09-04 22:36:43简介 前面讨论的很多文章里,都是...和无向图比起来,有向图更加多了一种出入度的概念。因为方向的有向性,很多以前在无向图里看起来比较简单的问题在这里会变得更加有意思。 有向图定义 一个常用的有向... -
判断有向图中的回路
2013-12-24 13:31:55数据结构的作业…拓扑排序 判断有向图中的环并打印 -
java用广度优先的方法来判断有向图是否有环
2017-08-16 22:56:08今天师兄做笔试题,我也跟着看,碰到了一个要构建有向图并判断节点是否有环的题。 另一位师兄说这个题可以用并查集做,并且做出来了,我用并查集试了试做不出来。。 我觉得这题大概是要用有向图做,考察有... -
用dfs判断一个有向图是否有环1
2022-08-08 23:15:31我们可以用一个color数组代表每个结点的状态,-1代表还没被访问,0代表正在被访问,1代表访问结束如果一个状态为“0”的结点,与他相连的结点状态也为“0”的话 -
用拓扑排序检测有向图中是否有环
2021-09-02 10:26:13提示:由于拓扑排序的检测方式不涉及到边权或点权,所以拓扑序列中的正环和负环都能够被检测出来。检测可达负环可以用Bellman-Ford或者SPFA。 算法主要步骤 1. 记录每个结点的入度,设置一个队列,专门存放入度为0... -
DFS判断有向图是否存在环
2020-04-09 22:52:08DFS判断有向图是否存在环 对一个节点有三种情况,还未访问,正在访问,访问结束 我们用0,1,-1,正在访问表示还在递归中未出来,如果相连节点都正在访问 说明在DFS过程中一条道路上访问了两次同一个节点,这说明有环... -
两种方法判断有向图是否有环【DFS】【拓扑排序】
2018-11-20 16:49:36方法1:DFS判断有向图是否有环 对一个节点u进行DFS,判断是否能从u回到自己这个节点,即是否存在u到u的回路。 color数组代表每个节点的状态 -1代表还没访问,0代表正在被访问,1代表访问结束 如果一个状态为0的节点...