使用 Java 进行图形循环检测
Graph Cycle Detection with Java
我正在研究 DAG 中的循环检测,我已经使用 DFS 实现了我的算法版本,这是代码;
public class DFS {
public static boolean hasCycle(Graph graph) {
for (Vertex vertex : graph.getVertices()) {
if (detectCycle(graph, vertex)) {
return true;
}
}
return false;
}
private static boolean detectCycle(Graph graph, Vertex root) {
for (Vertex vertex : graph.getVertices()) {
vertex.setBeingVisited(false);
vertex.setVisited(false);
}
return DFS.dfs(graph, root);
}
private static boolean dfs(Graph graph, Vertex root) {
root.setBeingVisited(true);
for (Edge edge : root.getNeighbors()) {
Vertex neighborVertex = edge.getEndPoint();
if (neighborVertex.isBeingVisited()) {
return true;
} else if (!neighborVertex.isVisited()) {
DFS.dfs(graph, neighborVertex);
}
}
root.setVisited(true);
root.setBeingVisited(false);
return false;
}
}
这是测试 class:
public class App {
public static void main(String[] args) {
Vertex a = new Vertex("A");
Vertex b = new Vertex("B");
Vertex c = new Vertex("C");
Vertex d = new Vertex("D");
Vertex e = new Vertex("E");
Edge e1 = new Edge(a, b);
Edge e2 = new Edge(a, c);
a.addNeighbor(e1);
a.addNeighbor(e2);
Edge e3 = new Edge(b, d);
b.addNeighbor(e3);
Edge e4 = new Edge(c, e);
c.addNeighbor(e4);
Edge e5 = new Edge(d, a);
d.addNeighbor(e5);
List<Vertex> vertices = new ArrayList<>();
vertices.add(a);
vertices.add(b);
vertices.add(c);
vertices.add(d);
vertices.add(e);
Graph graph = new Graph(vertices);
System.out.println(DFS.hasCycle(graph));
if (DFS.hasCycle(graph)) {
System.out.println("It does have a cycle!");
} else {
System.out.println("It doesn't have cycle!");
}
}
}
对于这种情况,结果应该打印出该图有一个循环,因为我们正在处理的图是这个:
>b --> d
/ |
a<-------
\
> c --> e
但是我的输出越来越假,就像没有循环一样,我就是找不到我的实现中的错误。有人可以帮忙吗?
您未理解该行的用途:
DFS.dfs(graph, neighborVertex);
如果这个调用returnstrue
,方法也应该returntrue
.
编辑: 应该是这样的:
private static boolean dfs(Graph graph, Vertex root) {
root.setBeingVisited(true);
for (Edge edge : root.getNeighbors()) {
Vertex neighborVertex = edge.getEndPoint();
if (neighborVertex.isBeingVisited()) {
return true;
} else if (!neighborVertex.isVisited() && DFS.dfs(graph, neighborVertex)) {
return true;
}
}
root.setVisited(true);
root.setBeingVisited(false);
return false;
}
我正在研究 DAG 中的循环检测,我已经使用 DFS 实现了我的算法版本,这是代码;
public class DFS {
public static boolean hasCycle(Graph graph) {
for (Vertex vertex : graph.getVertices()) {
if (detectCycle(graph, vertex)) {
return true;
}
}
return false;
}
private static boolean detectCycle(Graph graph, Vertex root) {
for (Vertex vertex : graph.getVertices()) {
vertex.setBeingVisited(false);
vertex.setVisited(false);
}
return DFS.dfs(graph, root);
}
private static boolean dfs(Graph graph, Vertex root) {
root.setBeingVisited(true);
for (Edge edge : root.getNeighbors()) {
Vertex neighborVertex = edge.getEndPoint();
if (neighborVertex.isBeingVisited()) {
return true;
} else if (!neighborVertex.isVisited()) {
DFS.dfs(graph, neighborVertex);
}
}
root.setVisited(true);
root.setBeingVisited(false);
return false;
}
}
这是测试 class:
public class App {
public static void main(String[] args) {
Vertex a = new Vertex("A");
Vertex b = new Vertex("B");
Vertex c = new Vertex("C");
Vertex d = new Vertex("D");
Vertex e = new Vertex("E");
Edge e1 = new Edge(a, b);
Edge e2 = new Edge(a, c);
a.addNeighbor(e1);
a.addNeighbor(e2);
Edge e3 = new Edge(b, d);
b.addNeighbor(e3);
Edge e4 = new Edge(c, e);
c.addNeighbor(e4);
Edge e5 = new Edge(d, a);
d.addNeighbor(e5);
List<Vertex> vertices = new ArrayList<>();
vertices.add(a);
vertices.add(b);
vertices.add(c);
vertices.add(d);
vertices.add(e);
Graph graph = new Graph(vertices);
System.out.println(DFS.hasCycle(graph));
if (DFS.hasCycle(graph)) {
System.out.println("It does have a cycle!");
} else {
System.out.println("It doesn't have cycle!");
}
}
}
对于这种情况,结果应该打印出该图有一个循环,因为我们正在处理的图是这个:
>b --> d
/ |
a<-------
\
> c --> e
但是我的输出越来越假,就像没有循环一样,我就是找不到我的实现中的错误。有人可以帮忙吗?
您未理解该行的用途:
DFS.dfs(graph, neighborVertex);
如果这个调用returnstrue
,方法也应该returntrue
.
编辑: 应该是这样的:
private static boolean dfs(Graph graph, Vertex root) {
root.setBeingVisited(true);
for (Edge edge : root.getNeighbors()) {
Vertex neighborVertex = edge.getEndPoint();
if (neighborVertex.isBeingVisited()) {
return true;
} else if (!neighborVertex.isVisited() && DFS.dfs(graph, neighborVertex)) {
return true;
}
}
root.setVisited(true);
root.setBeingVisited(false);
return false;
}