Java检测循环有向图
Java检测循环有向图
提问于 2016-04-24 19:07:49
目前，我正试图编写一个过程来检查有向图是否是循环的，是否是。我不知道我做错了什么(很可能我做错了所有事情，所以请StackOverflow，让我看看我的愚蠢！)我会感谢任何帮助，因为我已经到了一个地步，我不知道什么可能是问题。
输入是一个邻接列表，如：
0: 2 4
1: 2 4
2: 3 4
3: 4
4: 0 1 2 3(0指示2和4；1指示2和4等等)
其思想是，我检查所检查的节点是否为“灰色”(部分探索)。如果是的话，它必须是一个后边，因此是一个循环图。黑边总是被探索或交叉边缘，所以这不应该触发循环消息。我的目标是做深度优先搜索
如果A->B和B->A，这不应该触发关于循环的消息(但是A-> B，B->C，C->A应该)。
hasCycle调用hasCycleInSubgraph，后者通过图形的Adjency列表递归地调用自己。
class qs {
private ArrayList<Integer>[] adjList;
private Stack<Integer> stack;
private ArrayList<Integer> whiteHat;
private ArrayList<Integer> greyHat;
private ArrayList<Integer> blackHat;
public qs(ArrayList<Integer>[] graph) {
this.adjList = graph;
this.stack = new Stack();
this.whiteHat = new ArrayList<Integer>();
this.greyHat = new ArrayList<Integer>();
this.blackHat = new ArrayList<Integer>();
for (Integer h = 0; h < adjList.length; h++) {
whiteHat.add(h);
}
}
public boolean hasCycle() {
for (Integer i = 0; i < adjList.length; i++) {
// System.out.print("Local root is: ");
// System.out.println(i);
whiteHat.remove(i);
greyHat.add(i);
if (hasCycleInSubgraph(i) == true) {
return true;
}
greyHat.remove(i);
blackHat.add(i);
}
return false;
}
public boolean hasCycleInSubgraph(Integer inp) {
if (blackHat.contains(inp)) {
return false;
}
for (Integer branch : adjList[inp]) {
// System.out.print("Adj is: ");
// System.out.println(branch);
if ( greyHat.contains(branch) && !inp.equals(branch) ) {
return true;
}
whiteHat.remove(branch);
greyHat.add(branch);
if ( hasCycleInSubgraph(branch) == true ) {
return true;
}
greyHat.remove(branch);
blackHat.add(branch);
}
return false;
}
}回答 1
Stack Overflow用户
回答已采纳
发布于 2016-04-24 19:55:36
你太复杂了:一个循环可以通过深度优先搜索来检测:从任何一个给定的节点，步行到每个连接的节点；如果你回到一个已经访问过的节点，你就有了一个循环。
class qs {
private final ArrayList<Integer>[] graph;
qs(ArrayList<Integer>[] graph) {
this.graph = graph;
}
boolean hasCycle() {
List<Integer> visited = new ArrayList<>();
for (int i = 0; i < graph.length; ++i) {
if (hasCycle(i, visited)) {
return true;
}
}
}
private boolean hasCycle(int node, List<Integer> visited) {
if (visited.contains(node)) {
return true;
}
visited.add(node);
for (Integer nextNode : graph[node]) {
if (hasCycle(nextNode, visited)) {
return true;
}
}
visited.remove(visited.length() - 1);
return false;
}
}如果要检测周期超过给定长度，只需检查递归的深度：
if (visited.contains(node) && visited.size() > 2) {请注意，除了堆栈中的内容之外，这不需要保留任何状态。依赖可变状态使得代码线程--不安全(例如，两个调用hasCycle的线程同时会互相干扰)，因此应该避免--即使您现在不希望代码以多线程的方式使用，它也避免了问题的发生。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/36827641
复制相关文章
相似问题
腾讯云开发者
