精华内容
下载资源
问答
  • 判断有向图是否存在环
    千次阅读
    2021-03-15 02:40:32

    方法一:拓扑排序

    时间复杂度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)

    更多相关内容
  • 判断有向图是否存在环

    万次阅读 多人点赞 2018-09-04 22:36:43
    简介  前面讨论的很多文章里,都是...和无向图比起来,有向图更加多了一种出入度的概念。因为方向的有向性,很多以前在无向图里看起来比较简单的问题在这里会变得更加有意思。   有向图定义  一个常用的有向...

    简介

        前面讨论的很多文章里,都是针对无向图进行的分析。无向图的一个特性就是其中一旦两个节点a和b是相连的,这就意味着有路径从a到b,同时也有从b到a的。它具体对应的矩阵表达方式对应着一个对称矩阵。而这里重点是考察有向图。和无向图比起来,有向图更加多了一种出入度的概念。因为方向的有向性,很多以前在无向图里看起来比较简单的问题在这里会变得更加有意思。

     

    有向图定义

      一个常用的有向图会如下图这样:

      因为每个节点和节点之间对应着一定的方向关系,所以这里用一个箭头来表示从一个节点到另外一个节点的有向关系。在具体保存有向图定义的数据结构里,我们还是可以采用一样的链表组结构。只是因为是有向图,所以加入元素的时候不用考虑对称节点的问题。在实现上其实也更加简化。

      下面是一个关于有向图的简单定义实现:

     

    Java代码 

     收藏代码

    1. public class Digraph {  
    2.     private final int vertices;  
    3.     private int edges;  
    4.     private List<LinkedList<Integer>> adj;  
    5.   
    6.     public Digraph(int vertices) {  
    7.         if(vertices < 0) throw new IllegalArgumentException(  
    8.                 "Number of vertices in a Digraph must be nonnegative");  
    9.         this.vertices = vertices;  
    10.         this.edges = 0;  
    11.         adj = new ArrayList<LinkedList<Integer>>();  
    12.         for(int i = 0; i < vertices; i++) {  
    13.             adj.add(new LinkedList<Integer>());  
    14.         }  
    15.     }  
    16.   
    17.     public void addEdge(int v, int w) {  
    18.         if(v < 0 || v >= vertices)   
    19.             throw new IndexOutOfBoundsException(  
    20.                     "vertex " + v + " not in bound.");  
    21.         if(w < 0 || w >= vertices)   
    22.             throw new IndexOutOfBoundsException(  
    23.                     "vertex " + w + " not in bound.");  
    24.         adj.get(v).add(w);  
    25.         edges++;  
    26.     }  
    27. }  

     这部分代码很简单,无需解释。

     有了这部分定义之后,我们再来考虑后面的几个典型的问题。

     

    环的存在和检测

     和前面无向图的过程有点类似,我们要检测一个图中间是否存在环,肯定也需要通过某种遍历的方式,然后对访问过的元素做标记。如果再次碰到前面访问过的元素,则说明可能存在环。这里,如何来检测环和如果这个环存在的话,我们要返回这个环。在无向图的时候,这个方法确实是很简单可行,我们可以通过广度或者深度优先遍历来解决。在有向图的情况下,前面的办法照搬过来就一定可行吗?

     我们来看下面的一个示例:

     

        在该图中,假设我们从节点1开始去遍历,当按照前面的仅仅是修改marked[] 数组的办法,可能先通过节点2到达节点6,于是就设定了marked[6] = true。如下图:

     

      当再次遍历到节点6的时候,则如下图所示:

      这个时候,如果去看marked[6]的话,它已经被标记为true了。可是,如果按照这个条件,我们就确定这种情况存在环,肯定不行。因为现在的这个情况实际上并不是一个环,它仅仅是访问到了一个前面访问过的节点。在这种情况下,要判断一个环的存在,和取得环所在元素的问题根源在于哪里呢?

      在前面的示例中,我们从节点1到2,然后到6,整个的过程里,这几个点被遍历了,但是光到这一步还没有构成一个环。按照深度优先遍历的过程,这个时候相当于2和6已经遍历完了,要去遍历节点1的另外一个边。实际上,这个时候就算从另外一个边可以遍历到前面的节点2或者6,因为这个时候能访问到2和6的是另外一组有向边了,它们和前面经过的那些有向边是不一定构成环的。

      另外,从环的构成来说。如果我们按照深度优先的顺序访问到了一个环,必然是在逐步递归推进的过程中能访问到自己前面访问过的节点。这里的差别就在于递归推进所重复访问的节点和前面图深度遍历所访问的节点还又所差别。我们以下图来说明一下它们的详细差别:

      假定我们从节点1出发,先访问2这边的边,一直到节点6,这个时候按照深度优先遍历是首先一步步递归进去到节点6。因为节点6没有别的出边,所以就要一步步的按照前面的过程返回。这个过程如下图:

      在前面2,6节点都返回后,这个时候就算后面的节点比如5访问到6了,它们是不构成环的,如下图:

       这个时候的节点2和6,它们和节点3,4, 5之间的差别是,2和6已经不在函数递归的栈里了,因为它们已经从前面的递归里返回了,而3,4,5节点还是在里面。所以到后面遍历到节点7,8之后,我们再次碰到了节点4,就可以确认它们是构成了一个环。如下图:

     所以,这里问题的关键点就是,我们再次碰到的节点4它还没有从前面向前递归的函数返回回来,结果又被遍历的时候给碰上了。这样,按照前面的分析,我们的环检测要点就是,找到一个还在遍历中的节点,同时在遍历的时候它如果再次被访问到了,则表示找到了环。而如果它被访问完了之后返回,则再次碰到它的时候就不是环了。

     从实现的角度来说,相当于对这个节点递归访问前要设置一个对应的值,表示它在一个递归顺序里。然后在它访问退出这个递归后,要将这个值设置回来。一种简单的方式就是设置一个boolean[] onstack这样的数组,每个元素对应这里面的一个值。然后,因为要记录访问过的节点,肯定要用一个boolean[] marked数组。另外,既然还要记录环的结果,肯定还要一个记录前向访问的数组int[] edgeTo。

      按照前面的讨论,可以得到一个检验环并保存环的代码实现:

    Java代码 

     收藏代码

    1. public class DirectedCycle {  
    2.     private boolean[] marked;  
    3.     private int[] edgeTo;  
    4.     private Stack<Integer> cycle;  
    5.     private boolean[] onStack;  
    6.   
    7.     public DirectedCycle(Digraph g) {  
    8.         onStack = new boolean[g.getVertices()];  
    9.         edgeTo = new int[g.getVertices()];  
    10.         marked = new boolean[g.getVertices()];  
    11.         for(int v = 0; v < g.getVertices(); v++) {  
    12.             if(!marked[v]) dfs(g, v);  
    13.         }  
    14.     }  
    15.   
    16.     private void dfs(Digraph g, int v) {  
    17.         onStack[v] = true;  
    18.         marked[v] = true;  
    19.         for(int w : g.adj(v)) {  
    20.             if(hasCycle()) return;  
    21.             if(!marked[w]) {  
    22.                 edgeTo[w] = v;  
    23.                 dfs(g, w);  
    24.             } else if(onStack[w]) {  
    25.                 cycle = new Stack<Integer>();  
    26.                 for(int x = v; x != w; x = edgeTo[x])  
    27.                     cycle.push(x);  
    28.                 cycle.push(w);  
    29.                 cycle.push(v);  
    30.             }  
    31.         }  
    32.         onStack[v] = false;  
    33.     }  
    34. }  

      前面代码的要点在于dfs方法。当我们要访问某个节点v的时候,首先设置它对应的onStack[v] = true。而这个节点被访问结束后,肯定是在它后面遍历的递归都结束了,所以要在for循环之后重新将onStack[v] = false。在找到环的时候,我们根据当前节点v不断回退到某个节点,这个节点刚好就是w。因为这是属于函数递归调用里面的,如果检测到w被遍历过,必然也能够找到w。于是讲这些节点压入栈中。这样整个环就找到了。

     前面代码里引用到的方法hasCycle就很简单,它和返回整个环的代码如下:

    Java代码 

     收藏代码

    1. public boolean hasCycle() {  
    2.         return cycle != null;  
    3.     }  
    4.   
    5.     public Iterable<Integer> cycle {  
    6.         return cycle;  
    7.     }  

      查找和返回有向图里的环需要遍历所有的节点,同时根据每次递归推进的过程中保证覆盖到在同一个递归序列里的元素。这是实现的两个要点。

      这里我们讨论了有向图环的检测和引用,它在后续的问题应用里有很重要的作用。在后续的小节里会继续说明。这里先埋下一个伏笔。

     

    深度优先遍历排序

     我们在对图做一些遍历的时候,有的时候会发现一个和访问树很类似的规律。比如说,访问一棵二叉树的时候,我们访问它的序列关系不同,会产生不同的序列。比如说前序,中序和后序。在访问图的时候,假定以深度优先遍历为例。当我们每次遍历到一个节点的时候就访问它,也可以称其访问序为前序,而如果等它遍历递归后返回的时候再访问它,这就相当于一个后序。以前面的图为例:

      这里,我们如果按照前序的过程来遍历的话,首先就是1, 2, 6。然后是3, 4, 5, 7, 8。这就是典型的深度优先递归访问的步骤。而按照后序的过程来考虑呢,它访问的顺序则如下:6, 2, 8, 7, 5, 4, 3, 1。这里的序列相当于是将每个遍历访问的节点先入栈,然后当遍历到一个没有出边的节点时,这将作为一个返回条件。递归再逐步返回。

     要实现这两种遍历的方法其实很简单,无非就是在深度优先遍历的时候在访问某个节点前或者访问结束后将节点加入到队列里。具体的实现如下:

     

    Java代码 

     收藏代码

    1. public class DepthFirstOrder {  
    2.     private boolean[] marked;  
    3.     private Queue<Integer> pre;  
    4.     private Queue<Integer> post;  
    5.   
    6.     public DepthFirstOrder(Digraph g) {  
    7.         pre = new LinkedList<Integer>();  
    8.         post = new LinkedList<Integer>();  
    9.         marked = new boolean[g.getVertices()];  
    10.   
    11.         for(int v = 0; v < g.getVertices(); v++)  
    12.             if(!marked[v]) dfs(g, v);  
    13.     }  
    14.   
    15.     private void dfs(Digraph g, int v) {  
    16.         pre.add(v);  
    17.         marked[v] = true;  
    18.         for(int w : g.adj(v)) {  
    19.             if(!marked[w])  
    20.                 dfs(g, w);  
    21.         }  
    22.         post.add(v);  
    23.     }  
    24.   
    25.     public Iterable<Integer> pre() {  
    26.         return pre;  
    27.     }  
    28.   
    29.     public Iterable<Integer> post() {  
    30.         return post;  
    31.     }  
    32. }  

      重点就是在dfs方法里。在pre里面添加元素的时候是每次刚第一次访问某个节点时。而在post里面添加元素的时候则表示通过该节点以及它所关联的节点都已经遍历结束了。这两个序列有什么作用呢?在后序一些计算里,还是很有用的。

     

     比如说后序的序列,因为每次我们放入队列的是已经被遍历过的节点,而且通过这个节点已经不可能再访问到别的节点了。这就意味着从这个节点要么是出度为0的节点,要么是通过它所能访问到的节点都已经被访问过了。因为这些节点将作为递归结束的条件返回。所以说它们是优先返回的。也说明这些被返回的节点是可以被其他节点所遍历访问到的。而如果图里面有孤立的节点或者入度为0的节点呢?对于它们,因为没有办法通过其他节点所遍历到,它们被返回的可能性就越晚。这种特性在后面的讨论里有一个很重要的作用。这里先不详细的阐述。

     

    拓扑排序和DAG

     拓扑排序和DAG如果每接触过看起来会觉得很新奇。它们的定义是很紧密相连的。 该怎么来理解它们呢?我们先看看它们的定义。DAG(Directed acyclic graph),表示有向无环图。就是对应一个有向图,但是它里面却没有环。像下面的这些个图,都可以称为DAG:

     

     

        对于这个定义,当我们要检测一个有向图是不是DAG的时候就很简单了。有了前面检测环的方法,直接用那个办法就可以了。现在,拓扑排序又是什么意思呢?

     这个概念结合一些具体的问题来说可能更加好理解一些。在一些任务安排和调度的问题里。不同的问题或者任务之间又一些依赖的关系,有的任务需要在某些任务完成之后才能做。就像一些学校的教学课程安排。设置某一门课程需要依赖于一个前置的课程,只有学生学习了前置课程之后才能取学习该课程。如果将一门课程当做一个节点,从它引出一个指针指向后序依赖它的课程。就可能有一个类似这样的图:

        如果将上图中每个课程用一个数字节点表示,这不正是前面的一个图吗?对于这种图来说,最大的特点就是它们肯定就不能存在环。不然就有逻辑上的错误。因此,前面检测一个图是否为DAG的方法就是看图中是否有环。而拓扑排序则是在确定没有环的情况下,输出一个正常的序列。这个序列表示从一个不依赖任何元素的节点到后序的节点。这些序列正好符合课程安排或者任务调度的逻辑顺序。

      我们已经知道了,对于一个有向图来说,如果它不存在环,则它应该为DAG。现在的问题是怎么找出这个拓扑序列来呢?前面一节里讲到的深度优先排序的过程在这里就起到作用了。实际上,对于深度优先遍历的后序序列,如果我们将它们的顺序完全倒过来,得到的序列就是满足我们要求的序列。对于这部分的证明书上有详细的说明,这里就不再赘述,只是直接搬过来这个结论。

      有了前面这两个结论的支持,要实现拓扑排序就已经比较简单了。就是我们首先判断一下图中间是否存在环,然后如果没有存在的话,则取其中后序遍历序列的相反就可以了。具体的实现如下:

    Java代码 

     收藏代码

    1. public class Topological {  
    2.     private Iterable<Integer> order;  
    3.   
    4.     public Topological(Digraph g) {  
    5.         DIrectedCycle cycleFinder = new DirectedCycle(g);  
    6.         if(!cycleFinder.hasCycle()) {  
    7.             DepthFirstOrder dfs = new DepthFirstOrder(g);  
    8.             order = dfs.reversePost();  
    9.         }  
    10.     }  
    11. }  

     因为这部分代码就是糅合前面几个部分的代码到一块,所以就很简单了。 

     

    另外一种思路

     针对前面的判断DAG以及求拓扑序列的问题。我们如果仔细观察的话,会发现一个这么有意思的现象。就是拓扑序列要求的序列必然是开始于一系列入度为0的节点。如果没有入度为0的节点,则表示这个图不是DAG,这样连遍历都没有必要了。当然,如果只是因为这个图里有入度为0的节点,并不代表这个图就一定是DAG。只是有了这么一个特征之后有一个好处,我们判断图是否为DAG时还是要检查是否存在环。

     但是,一旦判断出图里没有存在环,剩下的给出拓扑排序序列可以更加简化。我们只要去取这些入度为0的节点,然后从这些节点遍历图。然后给出的序列就是拓扑排序的序列。

      现在还要一个问题就是,我们怎么来求这些节点的入度呢?一个简单的办法就是在定义Digraph的时候增加一个数组int[] inDegree。每次我们添加一个边u->v到图里时,inDegree[v]++。剩下的事,你懂的。

     

    总结

     有向图虽然看起来在定义的很多方面和无向图很近似,但是当考虑到它的一些具体特性时。很多原来在无向图里比较简单的问题就变得更加复杂化了。比如说判断环和求图中的环时,需要利用深度优先递归的序列来判断。另外,有向图里前序、后序遍历在判断图是否为DAG以及求图的拓扑排序时很有帮助。里面的详细实现细节值得好好琢磨。这篇文章相对比较长,不过在讨论这些问题的时候能够有点小小的收获和一些想法,也算是挺不错的。

    展开全文
  • 此题是美团2017春招实习生在线笔试题,题目是“如何判断有向图有没有回路”,这里给出两种解法以供参考。解法一:深度遍历假设图以邻接矩阵表示,一条深度遍历路线中如果有结点被第二次访问到,那么有。我们用一个...

    此题是美团2017春招实习生在线笔试题,题目是“如何判断有向图有没有回路”,这里给出两种解法以供参考。

    解法一:深度遍历

    假设图以邻接矩阵表示,一条深度遍历路线中如果有结点被第二次访问到,那么有环。我们用一个变量来标记某结点的访问状态(未访问,访问过,其后结点都被访问过),然后判断每一个结点的深度遍历路线即可。
    因为采用邻接矩阵存储,一般至少需要将矩阵中元素的一半给过一下,由于矩阵元素个数为n^2, 因此时间复杂度就是O(n^2)。如果采用邻接表存储,则只存储了边结点(e条边,无向图是2e条边),加上表头结点为n(也就是顶点个数),因此时间复杂度为O(n+e)
    Java实现如下:

    import java.util.Scanner;
    
    public class test2 {
    	//邻接矩阵
    	static int[][] graph = new int[200][200];
    	//结点个数和边的个数
    	static int vNum,eNum;
    	//标记矩阵,0为当前结点未访问,1为访问过,-1表示当前结点后边的结点都被访问过。
    	static int[] color = new int[200];
    	//是否是DAG(有向无环图)
    	static boolean isDAG = true;
    	
    	//图的深度遍历函数
    	void DFS(int i){
    		System.out.println("正在访问结点"+i);
    		//结点i变为访问过的状态
    		color[i] = 1;
    		for(int j=1;j<=vNum;j++){
    			//如果当前结点有指向的结点
    			if(graph[i][j] != 0){	
    				//并且已经被访问过
    				if(color[j] == 1){
    					isDAG = false;//有环
    					break;
    				}else if(color[j] == -1){
    					//当前结点后边的结点都被访问过,直接跳至下一个结点
    					continue;
    				}else{
    					DFS(j);//否则递归访问
    				}
    			}
    		}
    		//遍历过所有相连的结点后,把本节点标记为-1
    		color[i] = -1;
    	}
    	
    	//创建图,以邻接矩阵表示
    	void create(){
    		Scanner sc = new Scanner(System.in);
    		System.out.println("正在创建图,请输入顶点个数vNum:");
    		vNum = sc.nextInt();
    		System.out.println("请输入边个数eNum:");
    		eNum = sc.nextInt();
    		//初始化邻接矩阵为0(如果3个顶点,顶点分别是1,2,3)
    		for(int i=1;i<=vNum;i++){
    			for(int j=1;j<=vNum;j++){
    				graph[i][j] = 0;
    			}
    		}
    		//输入边的情况
    		System.out.println("请输入边的头和尾:");
    		for(int k=1;k<=eNum;k++){
    			int i = sc.nextInt();
    			int j = sc.nextInt();
    			graph[i][j] = 1;
    		}
    		//初始化color数组为0,表示一开始所有顶点都未被访问过
    		for(int i=1;i<=vNum;i++){
    			color[i] = 0;
    		}
    	}
    	
    	public static void main(String[] args) {
    		test2 t = new test2();
    		t.create();
    		//保证每个节点都遍历到,排除有的结点没有边的情况
    		for(int i=1;i<=vNum;i++){
    			//该结点后边的结点都被访问过了,跳过它
    			if(color[i] == -1){
    				continue;
    			}
    			t.DFS(i);
    			if(!isDAG){
    				System.out.println("有环!");
    				break;
    			}
    		}
    		if(isDAG){
    			System.out.println("没环。。。");
    		}
    	}
    }
    

    测试输入输出如下:

    正在创建图,请输入顶点个数vNum:
    5
    请输入边个数eNum:
    5
    请输入边的头和尾:
    1 2
    2 3
    3 4
    2 5
    5 4
    正在访问结点1
    正在访问结点2
    正在访问结点3
    正在访问结点4
    正在访问结点5
    没环。。。
    

    解法二:拓扑排序

    方法是重复寻找一个入度为0的顶点,将该顶点从图中删除(即放进一个队列里存着,这个队列的顺序就是最后的拓扑排序,具体见程序),并将该结点及其所有的出边从图中删除(即该结点指向的结点的入度减1),最终若图中全为入度为1的点,则这些点至少组成一个回路。
    采用邻接矩阵存储时,遍历二维数组,求各顶点入度的时间复杂度是O(n^2)。 遍历所有结点,找出入度为0的结点的时间复杂度是O(n)。对于n个入度为0的结点,删除他们的出边的复杂度为O(n^2)。 所以总的复杂度为O(n^2)
    对于邻接表,遍历所有边,求各顶点入度的时间复杂度是O(e),即边的个数。遍历所有结点,找出入度为0的结点的时间复杂度是O(n),即顶点的个数。遍历所有边,删除入度为0的结点的出边的复杂度为O(e),即边的个数。所以总的时间复杂度是O(n+e)
    Java实现如下:

    import java.util.Arrays;
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    
    public class test1 {
    	//邻接矩阵
    	static int[][] graph = new int[200][200];
    	//结点个数和边的个数
    	static int vNum,eNum;
    	//记录每个结点的入度,初始化为0
    	static int[] count = new int[200];
    	//用队列保存拓扑序列
    	static Queue<Integer> queue = new LinkedList<>();
    	
    	//拓扑排序
    	void topoSort(){
    		//入度为0的结点的个数,也就是入队个数
    		int number = 0;
    		//暂时存放拓扑序列
    		Queue<Integer> temp = new LinkedList<Integer>();
    		//遍历图中所有结点,找入度为0的结点删除(放进队列)
    		for(int i=1;i<=vNum;i++){
    			if(count[i] == 0){
    				queue.offer(i);
    			}
    		}
    		//删除这些被删除结点的出边(即对应结点入度减一)
    		while(!queue.isEmpty()){
    			int i = queue.peek();
    			temp.offer(queue.poll());
    			number++;
    			for(int j=1;j<=vNum;j++){
    				if(graph[i][j] == 1){
    					count[j] -= 1;
    					//出现了新的入度为0的结点,删除
    					if(count[j] == 0){
    						queue.offer(j);
    					}
    				}
    			}
    		}
    		if(number != vNum){
    			System.out.println("最后存在入度为1的结点,这个有向图是有回路的。");
    		}else{
    			System.out.println("这个有向图不存在回路,拓扑序列为:" + temp.toString());
    		}
    	}
    	
    	//创建图,以邻接矩阵表示
    	void create(){
    		Scanner sc = new Scanner(System.in);
    		System.out.println("正在创建图,请输入顶点个数vNum:");
    		vNum = sc.nextInt();
    		System.out.println("请输入边个数eNum:");
    		eNum = sc.nextInt();
    		//初始化邻接矩阵为0(如果3个顶点,顶点分别是1,2,3)
    		for(int i=1;i<=vNum;i++){
    			for(int j=1;j<=vNum;j++){
    				graph[i][j] = 0;
    			}
    		}
    		//输入边的情况
    		System.out.println("请输入边的头和尾:");
    		for(int k=1;k<=eNum;k++){
    			int i = sc.nextInt();
    			int j = sc.nextInt();
    			graph[i][j] = 1;
    		}
    		//计算每个结点的入度
    		Arrays.fill(count, 0);//先初始化为0
    		for(int i=1;i<=vNum;i++){
    			for(int j=1;j<=vNum;j++){
    				if(graph[i][j] == 1){
    					count[j] = count[j] + 1;
    				}
    			}
    		}
    	}
    	
    	public static void main(String[] args) {
    		test1 t = new test1();
    		t.create();
    		t.topoSort();
    	}
    }
    
    
    展开全文
  • 第一次写博客,不太会用,话不多说 直接上代码 详细可以看注释,无向图判断是否存在环比有向图相对复杂一点 ,需要判断访问的节点的临接表中的节点与父节点是否相同。 /** * @Description:判断无向图是否 深度...
  • DFS判断有向图是否存在环

    千次阅读 2020-11-02 20:50:19
    dfs深搜如果遇到被标记成1的点,就说明有环。 #include <iostream> using namespace std; const int N = 1010; int g[N][N], n, m, st[N], flag = 1; void dfs(int k) { st[k] = 1; for(int i = 1; i <=...

    st数组记录每个点的状态:0表示没访问过,1表示访问过,2表示与该点相邻的点都被访问过。

    dfs深搜如果遇到被标记成1的点,就说明有环。

    #include <iostream>
    using namespace std;
    const int N = 1010;
    int g[N][N], n, m, st[N], flag = 1;
    
    void dfs(int k) {
    	st[k] = 1;
    	for(int i = 1; i <= n; i++) {
    		if(g[k][i]) { //和k点相邻
    			if(st[i] == 1) {
    				flag = 0;
    				break;
    			}
    			if(st[i] == 2) //直接跳过这个点
    				continue; 
    			dfs(i);
    		}
    	}
    	st[k] = 2;
    }
    int main() {
    	cin>>n>>m;
    	while(m--) {
    		int x, y;
    		cin>>x>>y;
    		g[x][y] = 1;
    	}
    	for(int i = 1; i <= n; i++)
    		if(!st[i])
    			dfs(i);
    
    	if(!flag) cout<<"yes"<<endl;
    	else cout<<"no"<<endl;
    	return 0;
    }
    
    展开全文
  • 本文主要针对如何判断有向图/无向图中是否存在环的问题进行简单的论述。一 无向图1.利用DFS进行判断利用DFS判断有向图是否存在环,是最为常用的一种方法,虽然这种方法很常用,但可参考的代码的实现比较少,下面对...
  • DFS 判断有向图是否存在环 vis :DFS 遍历的结果 trace:也是遍历的结果,需要对结果进行分析,找到重复值时,判断重复值的索引位置,依次进行遍历,输出结果 程序 ## graph = { "a": ["b", "c"], "b": ["a", "d"]...
  • #无向图判断环是否存在 def dfs(u,fa): for i in range(v): n=g[u][i]#n为图中的顶点数 # print(u,n,fa,i,'') if n in vertex:#判断n是否属于图的顶点 if n==fa: continue if visit[n]==0: visit[n]=1 if ...
  • 两种方式判断有向图是否-python实现 1. DFS判断有向图是否 假设图以邻接矩阵表示,一条深度遍历路线中如果有结点被第二次访问到,那么有。我们用一个变量来标记某结点的访问状态(未访问,访问过,其后...
  • 图——判断有向图是否

    千次阅读 2020-12-04 09:38:55
    1. 判断有向图是否 给定有向图,检查该图是否包含循环。如果给定图包含至少一个循环,则函数应返回true,否则返回false。 1.1. 方法一:DFS 1.1.1. 思路 对一个图进行DFS, 则DFS的路径可以生成一个棵树。 ...
  • 判断有向图是否存在环,用邻接表做存储结构
  • vector < int > v [ MAX_N ] ; int n , m , sum [ MAX_N ] ; bool topo ( ) { int num = 0 ; queue < int > q ; //queue,vector,greater<int> >q;...//无 else return false ; }
  • } else { System.out.println("这个有向图存在回路,拓扑序列为:" + temp.toString()); } } //创建图,以邻接矩阵表示 void create() { Scanner sc = new Scanner(System.in); System.out.println("正在创建图,...
  • 求拓扑序列是宽度优先搜索的经典应用,拓扑序列通俗的讲就是所有的边都是从前指向后的,不存在后指向前的,也就保证了中不存在环。所以有向无环一定存在拓扑序列,也称为拓扑。因为边都是从前指向后的,所以...
  • 如果学习x课程前必须先学习y课程,学习y课程前必须先学习z课程,学习z课程前必须先学习x课程,那么一定是有问题了...1.1检测有向环的API设计 在API中添加onStack[]布尔数组,索引为的顶点,当我们深度搜索的时: ...
  • 代码】leetcode207.课程表(判断有向图是否
  • 判断向图是否存在环

    千次阅读 2021-05-09 21:58:41
    判断向图是否存在环 并查集 遍历所有边,对于遍历到边的两个端点,如果本身已经连通(在此前遍历到,并属于一个祖先),则说明存在一个环。 利用树的性质 对于无向图来说,如果边数为点数-1则一定能重构为树形,...
  • *利用并查集判断向图是否有环 */ public class Solution { public int[] parent;//记录并查集元素父节点 public int depth[];//记录并查集每个元素的深度 //初始化操作 public Solution(int nums) { ...
  • 给定二维数组,每个数组中表示两个节点相邻,判断图是否存在环。存在则返回false。已知节点总数和二位数组。 2, [[1,0]] true 2, [[1,0],[0,1]] false 解体思路:通过深度优先搜索的方法从每个节点开始分别对图...
  • 有向图是否存在环 LeetCode题目:207. Course Schedule 题目链接:https://leetcode.com/problems/course-schedule/ 题目大意:         现在你总共有 n 门课需要选,记为 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 58,250
精华内容 23,300
热门标签
关键字:

判断有向图是否存在环