查找有向图中的所有循环，包括后边
Find all Cycles in the Directed Graph including back edges
给定下面的 图 ，找到从顶点 1 回到 1 的所有可能路径，包括后边。
结果：
[1,2,3,2,1]
[1,2,1]
[1,2,3,1]
我试过用DFS只能得到一个周期[1,2,3,2,1]。我不知道如何跟踪后缘。
代码:
private static void dfsNow(Node vertex, HashMap<String, List<Node>> adjList,
HashSet<String> visited, HashSet<String> candidates,
ArrayList<String> res) {
candidates.add(vertex.v);
res.add(vertex.v);
for(Node adj : adjList.get(vertex.v)) {
if(candidates.contains(adj.v)) {
res.add(adj.v);
System.out.println(vertex.v+":"+adj.v);
} else {
//adj.setParent(vertex); // build the trace back
dfsNow( adj, adjList,visited,candidates,res);
}
}
candidates.remove(vertex.v);
visited.add(vertex.v);
}
你离答案很近了。
为了检测图中的环，您需要使用深度优先搜索算法。没错。
但是您的解决方案中有几处需要改进：
- 对于此任务，您不需要 边。因为您可以仅使用 顶点 来建模 有向图 。 边 在处理加权图（即每条边都与一个值相关联）并且需要解决例如使用 Dijkstra 或 Bellman–Ford 的最短路径问题时很有用算法。那么你真的需要边来模拟顶点之间的连接。但是在这个任务中，边是冗余的，每个顶点可以指向其他顶点。
- 邻接表 不能是单独的数据结构。相反，每个 顶点 都必须知道它的 邻居 。 IE。每个 顶点 必须包含对 相邻顶点.
集合的引用
- 由于图可以包含多个循环，结果需要用嵌套集合表示。喜欢列表列表
List<List<Vertex>>.
contains() 在 List 上进行的检查非常昂贵（O(n) 在最坏的情况下), 并且不是能够关联元素的列表。 Map 是一个更好的选择，因为 map 允许在恒定时间内检索值并将多个键与相同的值相关联（即当一组顶点点与单个顶点连接时的模型案例）。
请注意，循环 [1,2,3,2,1] 无效，因为有 多个顶点 访问了两次 。它是两个循环 1-2 和 2-3 的组合。如果您需要发现图形中的所有循环，则必须一次只检测一个循环，否则尝试恢复循环路径可能会失败，因为引用彼此指向一个。只是因为在您的解决方案中只能跟踪一条路径，所以您没有 运行 遇到第二个循环 2->3->2 的麻烦。 IE。循环中的所有顶点（除了一个）必须是唯一的，这将允许维护多条路径。
在下面的实现中，我特意提供了一种能够检测包含特定顶点的循环的方法，以及一种获取所有循环的方法仅由唯一顶点组成.这样您就可以通过更改它们来玩耍，并确保 map 永远不会包含循环的最后一段。 IE。只有条目 2->3 会被添加到映射中，但条目 3->2 不会，否则你会创建一个无限循环。
下图的实现仅使用 顶点。深度优先搜索算法实现迭代（虽然递归实现更容易，但递归在Java中有局限性，尤其是在处理大型数据集和迭代方法时性能更高）。
public class CyclicGraph {
private Map<Integer, Vertex> vertexById = new HashMap<>();
public void addVertex(int vertexId, int... neighbours) {
// vertexById.putIfAbsent(vertexId, new Vertex(vertexId));
// Vertex current = vertexById.get(vertexId); // does the same as the line below with one important distinction - new Vertex will be instantiated by `computeIfAbsent` only entry is not present
Vertex current = vertexById.computeIfAbsent(vertexId, Vertex::new); // adding a vertex
for (int next : neighbours) {
Vertex neighbour = vertexById.computeIfAbsent(next, Vertex::new); // retrieving neighbour
current.addNeighbour(neighbour); // adding neighbour
}
}
public List<List<Vertex>> getCyclesContainingVertex(int targetId) {
Vertex target = vertexById.get(targetId);
if (vertexById.get(targetId) == null) {
return Collections.emptyList();
}
List<List<Vertex>> cycles = new ArrayList<>();
Deque<Vertex> stack = new ArrayDeque<>();
Set<Vertex> seen = new HashSet<>();
Map<Vertex, Vertex> paths = new HashMap<>();
stack.add(target);
while (!stack.isEmpty()) {
Vertex current = stack.pop();
seen.add(current);
for (Vertex neighbour : current.getNeighbours()) {
if (seen.contains(neighbour) && neighbour.equals(target)) { // the cycle was found
// build cycle, don't add vertex to the stack and don't add new entry to the paths (it can prevent other cycles containing neighbour vertex from being detected)
cycles.add(buildCycle(paths, neighbour, current));
} else if (!seen.contains(neighbour)) {
stack.add(neighbour);
paths.put(neighbour, current);
seen.add(neighbour);
}
}
}
return cycles;
}
public List<List<Vertex>> getAllCycles() {
List<List<Vertex>> cycles = new ArrayList<>();
Deque<Vertex> stack = new ArrayDeque<>();
Set<Vertex> seen = new HashSet<>();
for (Vertex next : vertexById.values()) {
if (seen.contains(next)) continue;
Map<Vertex, Vertex> paths = new HashMap<>();
stack.add(next);
while (!stack.isEmpty()) {
Vertex current = stack.pop();
seen.add(current);
for (Vertex neighbour : current.getNeighbours()) {
if (seen.contains(neighbour)) { // the cycle was found
// build cycle, don't add vertex to the stack and don't add new entry to the paths (it can prevent other cycles containing neighbour vertex from being detected)
cycles.add(buildCycle(paths, neighbour, current));
} else {
stack.add(neighbour);
paths.put(neighbour, current);
seen.add(neighbour);
}
}
}
}
return cycles;
}
private List<Vertex> buildCycle(Map<Vertex, Vertex> paths, Vertex start, Vertex end) {
Deque<Vertex> cycle = new ArrayDeque<>();
Vertex current = end;
while (current != null && !current.equals(start)) {
cycle.addFirst(current);
current = paths.get(current);
}
cycle.addFirst(start);
return new ArrayList<>(cycle);
}
public void clear() {
this.vertexById.clear();
}
private class Vertex {
private int id;
private Set<Vertex> neighbours = new HashSet<>();
public Vertex(int id) {
this.id = id;
}
public boolean addNeighbour(Vertex vert) {
return neighbours.add(vert);
}
// getters, hashCode/equeals, toString()
}
}
演示中使用的更详细的图表示例以及问题中提供的图表。
main() - 演示
public static void main(String[] args) {
CyclicGraph graph = new CyclicGraph();
System.out.println("Graph described in the question (only cycles that include vertex 1):");
graph.addVertex(1, 2);
graph.addVertex(2, 1, 3);
graph.addVertex(3, 1, 2);
for (List<Vertex> cycle : graph.getCyclesContainingVertex(1)) {
System.out.println(cycle);
}
graph.clear();
System.out.println("\nMore elaborate Graph (all cycles):");
graph.addVertex(1, 2);
graph.addVertex(2, 1, 5);
graph.addVertex(3, 1, 2);
graph.addVertex(4, 1, 3);
graph.addVertex(5, 3, 4);
for (List<Vertex> cycle : graph.getAllCycles()) {
System.out.println(cycle);
}
}
输出
Graph described in the question (cycles that lead to 1):
[Vertex{ 1 }, Vertex{ 2 }] // 1 is reachable from 2
[Vertex{ 1 }, Vertex{ 2 }, Vertex{ 3 }] // 1 is reachable from 3
More elaborate Graph (all cycles):
[Vertex{ 1 }, Vertex{ 2 }] // 1 is reachable from 2
[Vertex{ 2 }, Vertex{ 5 }, Vertex{ 3 }] // 2 is reachable from 3
[Vertex{ 1 }, Vertex{ 2 }, Vertex{ 5 }, Vertex{ 3 }] // 1 is reachable from 3
[Vertex{ 3 }, Vertex{ 1 }, Vertex{ 2 }, Vertex{ 5 }, Vertex{ 4 }] // 3 is reachable from 4
[Vertex{ 1 }, Vertex{ 2 }, Vertex{ 5 }, Vertex{ 4 }] // 1 is reachable from 4
给定下面的 图 ，找到从顶点 1 回到 1 的所有可能路径，包括后边。
结果：
[1,2,3,2,1]
[1,2,1]
[1,2,3,1]
我试过用DFS只能得到一个周期[1,2,3,2,1]。我不知道如何跟踪后缘。
代码:
private static void dfsNow(Node vertex, HashMap<String, List<Node>> adjList,
HashSet<String> visited, HashSet<String> candidates,
ArrayList<String> res) {
candidates.add(vertex.v);
res.add(vertex.v);
for(Node adj : adjList.get(vertex.v)) {
if(candidates.contains(adj.v)) {
res.add(adj.v);
System.out.println(vertex.v+":"+adj.v);
} else {
//adj.setParent(vertex); // build the trace back
dfsNow( adj, adjList,visited,candidates,res);
}
}
candidates.remove(vertex.v);
visited.add(vertex.v);
}
你离答案很近了。
为了检测图中的环，您需要使用深度优先搜索算法。没错。
但是您的解决方案中有几处需要改进：
- 对于此任务，您不需要 边。因为您可以仅使用 顶点 来建模 有向图 。 边 在处理加权图（即每条边都与一个值相关联）并且需要解决例如使用 Dijkstra 或 Bellman–Ford 的最短路径问题时很有用算法。那么你真的需要边来模拟顶点之间的连接。但是在这个任务中，边是冗余的，每个顶点可以指向其他顶点。
- 邻接表 不能是单独的数据结构。相反，每个 顶点 都必须知道它的 邻居 。 IE。每个 顶点 必须包含对 相邻顶点. 集合的引用
- 由于图可以包含多个循环，结果需要用嵌套集合表示。喜欢列表列表
List<List<Vertex>>. contains()在List上进行的检查非常昂贵（O(n) 在最坏的情况下), 并且不是能够关联元素的列表。Map是一个更好的选择，因为 map 允许在恒定时间内检索值并将多个键与相同的值相关联（即当一组顶点点与单个顶点连接时的模型案例）。
请注意，循环 [1,2,3,2,1] 无效，因为有 多个顶点 访问了两次 。它是两个循环 1-2 和 2-3 的组合。如果您需要发现图形中的所有循环，则必须一次只检测一个循环，否则尝试恢复循环路径可能会失败，因为引用彼此指向一个。只是因为在您的解决方案中只能跟踪一条路径，所以您没有 运行 遇到第二个循环 2->3->2 的麻烦。 IE。循环中的所有顶点（除了一个）必须是唯一的，这将允许维护多条路径。
在下面的实现中，我特意提供了一种能够检测包含特定顶点的循环的方法，以及一种获取所有循环的方法仅由唯一顶点组成.这样您就可以通过更改它们来玩耍，并确保 map 永远不会包含循环的最后一段。 IE。只有条目 2->3 会被添加到映射中，但条目 3->2 不会，否则你会创建一个无限循环。
下图的实现仅使用 顶点。深度优先搜索算法实现迭代（虽然递归实现更容易，但递归在Java中有局限性，尤其是在处理大型数据集和迭代方法时性能更高）。
public class CyclicGraph {
private Map<Integer, Vertex> vertexById = new HashMap<>();
public void addVertex(int vertexId, int... neighbours) {
// vertexById.putIfAbsent(vertexId, new Vertex(vertexId));
// Vertex current = vertexById.get(vertexId); // does the same as the line below with one important distinction - new Vertex will be instantiated by `computeIfAbsent` only entry is not present
Vertex current = vertexById.computeIfAbsent(vertexId, Vertex::new); // adding a vertex
for (int next : neighbours) {
Vertex neighbour = vertexById.computeIfAbsent(next, Vertex::new); // retrieving neighbour
current.addNeighbour(neighbour); // adding neighbour
}
}
public List<List<Vertex>> getCyclesContainingVertex(int targetId) {
Vertex target = vertexById.get(targetId);
if (vertexById.get(targetId) == null) {
return Collections.emptyList();
}
List<List<Vertex>> cycles = new ArrayList<>();
Deque<Vertex> stack = new ArrayDeque<>();
Set<Vertex> seen = new HashSet<>();
Map<Vertex, Vertex> paths = new HashMap<>();
stack.add(target);
while (!stack.isEmpty()) {
Vertex current = stack.pop();
seen.add(current);
for (Vertex neighbour : current.getNeighbours()) {
if (seen.contains(neighbour) && neighbour.equals(target)) { // the cycle was found
// build cycle, don't add vertex to the stack and don't add new entry to the paths (it can prevent other cycles containing neighbour vertex from being detected)
cycles.add(buildCycle(paths, neighbour, current));
} else if (!seen.contains(neighbour)) {
stack.add(neighbour);
paths.put(neighbour, current);
seen.add(neighbour);
}
}
}
return cycles;
}
public List<List<Vertex>> getAllCycles() {
List<List<Vertex>> cycles = new ArrayList<>();
Deque<Vertex> stack = new ArrayDeque<>();
Set<Vertex> seen = new HashSet<>();
for (Vertex next : vertexById.values()) {
if (seen.contains(next)) continue;
Map<Vertex, Vertex> paths = new HashMap<>();
stack.add(next);
while (!stack.isEmpty()) {
Vertex current = stack.pop();
seen.add(current);
for (Vertex neighbour : current.getNeighbours()) {
if (seen.contains(neighbour)) { // the cycle was found
// build cycle, don't add vertex to the stack and don't add new entry to the paths (it can prevent other cycles containing neighbour vertex from being detected)
cycles.add(buildCycle(paths, neighbour, current));
} else {
stack.add(neighbour);
paths.put(neighbour, current);
seen.add(neighbour);
}
}
}
}
return cycles;
}
private List<Vertex> buildCycle(Map<Vertex, Vertex> paths, Vertex start, Vertex end) {
Deque<Vertex> cycle = new ArrayDeque<>();
Vertex current = end;
while (current != null && !current.equals(start)) {
cycle.addFirst(current);
current = paths.get(current);
}
cycle.addFirst(start);
return new ArrayList<>(cycle);
}
public void clear() {
this.vertexById.clear();
}
private class Vertex {
private int id;
private Set<Vertex> neighbours = new HashSet<>();
public Vertex(int id) {
this.id = id;
}
public boolean addNeighbour(Vertex vert) {
return neighbours.add(vert);
}
// getters, hashCode/equeals, toString()
}
}
演示中使用的更详细的图表示例以及问题中提供的图表。
main() - 演示
public static void main(String[] args) {
CyclicGraph graph = new CyclicGraph();
System.out.println("Graph described in the question (only cycles that include vertex 1):");
graph.addVertex(1, 2);
graph.addVertex(2, 1, 3);
graph.addVertex(3, 1, 2);
for (List<Vertex> cycle : graph.getCyclesContainingVertex(1)) {
System.out.println(cycle);
}
graph.clear();
System.out.println("\nMore elaborate Graph (all cycles):");
graph.addVertex(1, 2);
graph.addVertex(2, 1, 5);
graph.addVertex(3, 1, 2);
graph.addVertex(4, 1, 3);
graph.addVertex(5, 3, 4);
for (List<Vertex> cycle : graph.getAllCycles()) {
System.out.println(cycle);
}
}
输出
Graph described in the question (cycles that lead to 1):
[Vertex{ 1 }, Vertex{ 2 }] // 1 is reachable from 2
[Vertex{ 1 }, Vertex{ 2 }, Vertex{ 3 }] // 1 is reachable from 3
More elaborate Graph (all cycles):
[Vertex{ 1 }, Vertex{ 2 }] // 1 is reachable from 2
[Vertex{ 2 }, Vertex{ 5 }, Vertex{ 3 }] // 2 is reachable from 3
[Vertex{ 1 }, Vertex{ 2 }, Vertex{ 5 }, Vertex{ 3 }] // 1 is reachable from 3
[Vertex{ 3 }, Vertex{ 1 }, Vertex{ 2 }, Vertex{ 5 }, Vertex{ 4 }] // 3 is reachable from 4
[Vertex{ 1 }, Vertex{ 2 }, Vertex{ 5 }, Vertex{ 4 }] // 1 is reachable from 4