我听说有两种方法可以在图表中找到一个循环：
保留一组布尔值来跟踪您之前是否访问过节点。如果你用完了新的节点（无需击中已经存在的节点），那么只需回溯并尝试其他分支即可。
有人可以解释什么是后沿的图表，以及上述两种方法之间的区别。
谢谢。
更新： 这是两种情况下检测周期的代码。图是一个简单的类，它为了简单起见将所有的图节点表示为唯一的数字，每个节点都有它的相邻节点（g.getAdjacentNodes（int））：
public class Graph { private int [] [] nodes; //所有节点;例如int [] [] nodes = {{1,2,3}，{3,2,1,5,6} ...}; public int [] getAdjacentNodes（int v）{ return nodes [v]; //图中顶点的数量 public int vSize（）{ return nodes.length; } }检测Java代码在无向图中循环：
public class DFSCycle { private boolean marked [ ]。 private int s; 私人图形g; private boolean hasCycle; // s - 起始节点 public DFSCycle（Graph g，int s）{ this.g = g; this.s = s; marked = new boolean [g.vSize（）]; findCycle（g，s，s）; } public boolean hasCycle（）{ return hasCycle; public void findCycle（Graph g，int v，int u）{ marked [v] = true; for（int w：g.getAdjacentNodes（v））{ if（！marked [w]）{ marked [w] = true; findCycle（g，w，v）; } else if（v！= u）{ hasCycle = true; return; } } } }用于检测有向图中的周期的Java代码：
public class DFSDirectedCycle { 私有布尔标记[]; private boolean onStack []; private int s; 私人图形g; private boolean hasCycle; public DFSDirectedCycle（图g，int s）{ this.s = s this.g = g; marked = new boolean [g.vSize（）]; onStack = new boolean [g.vSize（）]; findCycle（g，s）; } public boolean hasCycle（）{ return hasCycle; public void findCycle（Graph g，int v）{ marked [v] = true; onStack [v] = true; for（int w：g.adjacentNodes（v））{ if（！marked [w]）{ findCycle（g，w）; } else if（onStack [w]）{ hasCycle = true; return; } } onStack [v] = false; } }解决方案
回答我的问题：
当且仅当存在后沿时，图形才有循环。后边是从节点到它自己的边（自循环），或者是由DFS生成的一个循环中的树的一个祖先。
意思是一样的。但是，此方法仅适用于无向图。
该算法对于有向图不起作用的原因是在有向图2中，到同一个顶点的不同路径不会形成一个循环。例如：A - > B，B - > C，A - > C - 不会形成循环，而在无向的循环中：A - B，B - C，C - p>
在无向图中查找循环
无向图有循环如果深度优先搜索（DFS）找到指向已经访问过的顶点（后沿）的边。
在有向图中查找循环
除了访问的顶点之外，我们还需要跟踪DFS遍历函数的递归堆栈中当前的顶点。如果我们到达一个已经在递归栈中的顶点，那么树中就有一个循环。
更新： 工作代码位于上述问题部分。
Note that a graph is represented as an adjacency list.
I've heard of 2 approaches to find a cycle in a graph:
Keep an array of boolean values to keep track of whether you visited a node before. If you run out of new nodes to go to (without hitting a node you have already been), then just backtrack and try a different branch.
The one from Cormen's CLRS or Skiena: For depth-first search in undirected graphs, there are two types of edges, tree and back. The graph has a cycle if and only if there exists a back edge.
Can somebody explain what are the back edges of a graph and what's the diffirence between the above 2 methods.
Thanks.
Update: Here's the code to detect cycles in both cases. Graph is a simple class that represents all graph-nodes as unique numbers for simplicity, each node has its adjacent neighboring nodes (g.getAdjacentNodes(int)):
public class Graph { private int[][] nodes; // all nodes; e.g. int[][] nodes = {{1,2,3}, {3,2,1,5,6}...}; public int[] getAdjacentNodes(int v) { return nodes[v]; } // number of vertices in a graph public int vSize() { return nodes.length; } }Java code to detect cycles in an undirected graph:
public class DFSCycle { private boolean marked[]; private int s; private Graph g; private boolean hasCycle; // s - starting node public DFSCycle(Graph g, int s) { this.g = g; this.s = s; marked = new boolean[g.vSize()]; findCycle(g,s,s); } public boolean hasCycle() { return hasCycle; } public void findCycle(Graph g, int v, int u) { marked[v] = true; for (int w : g.getAdjacentNodes(v)) { if(!marked[w]) { marked[w] = true; findCycle(g,w,v); } else if (v != u) { hasCycle = true; return; } } } }Java code to detect cycles in a directed graph:
public class DFSDirectedCycle { private boolean marked[]; private boolean onStack[]; private int s; private Graph g; private boolean hasCycle; public DFSDirectedCycle(Graph g, int s) { this.s = s this.g = g; marked = new boolean[g.vSize()]; onStack = new boolean[g.vSize()]; findCycle(g,s); } public boolean hasCycle() { return hasCycle; } public void findCycle(Graph g, int v) { marked[v] = true; onStack[v] = true; for (int w : g.adjacentNodes(v)) { if(!marked[w]) { findCycle(g,w); } else if (onStack[w]) { hasCycle = true; return; } } onStack[v] = false; } }解决方案
Answering my question:
The graph has a cycle if and only if there exists a back edge. A back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS forming a cycle.
Both approaches above actually mean the same. However, this method can be applied only to undirected graphs.
The reason why this algorithm doesn't work for directed graphs is that in a directed graph 2 different paths to the same vertex don't make a cycle. For example: A-->B, B-->C, A-->C - don't make a cycle whereas in undirected ones: A--B, B--C, C--A does.
Find a cycle in undirected graphs
An undirected graph has a cycle if and only if a depth-first search (DFS) finds an edge that points to an already-visited vertex (a back edge).
Find a cycle in directed graphs
In addition to visited vertices we need to keep track of vertices currently in recursion stack of function for DFS traversal. If we reach a vertex that is already in the recursion stack, then there is a cycle in the tree.
Update: Working code is in the question section above.
更多推荐
使用DFS检测图中的周期：2种不同的方法,有什么不同
发布评论