使用DFS查找图形中的所有路径

早上好！

我正在开发一种算法来查找无向，非加权图形中的所有路径。 我目前正在使用DFS algortihm进行回溯试图做到这一点。 这是我目前的代码：

import java.util.*; public class dfs { private static Map<Integer, LinkedHashSet> map = new HashMap<Integer, LinkedHashSet>(); private int startNode; private int numLinks; public dfs(int startNode, int numLinks) { super(); this.startNode = startNode; this.numLinks = numLinks; } public void addEdge(int source, int destiny) { LinkedHashSet adjacente = map.get(source); if(adjacente==null) { adjacente = new LinkedHashSet(); map.put(source, adjacente); } adjacente.add(destiny); } public void addLink(int source, int destiny) { addEdge(source, destiny); addEdge(destiny, source); } public LinkedList adjacentNodes(int last) { LinkedHashSet adjacente = map.get(last); System.out.println("adjacentes:" + adjacente); if(adjacente==null) { return new LinkedList(); } return new LinkedList(adjacente); } public static void main(String[] args) { Scanner input = new Scanner(System.in); int numVertices = input.nextInt(); int numLinks = input.nextInt(); int startNode = input.nextInt(); int endNode = startNode; dfs mapa = new dfs(startNode, numLinks); for(int i = 0; i<numLinks; i++){ mapa.addLink(input.nextInt(), input.nextInt()); } List<ArrayList> paths = new ArrayList<ArrayList>(); List visited = new ArrayList(); visited.add(startNode); Integer currentNode = 0; Iterator it = map.entrySet().iterator(); while (it.hasNext()) { Map.Entry pairs = (Map.Entry)it.next(); currentNode = (Integer) pairs.getKey(); //System.out.println("Current Node:" + currentNode); mapa.findAllPaths(mapa, visited, paths, currentNode); } } private void findAllPaths(dfs mapa, List visited, List<ArrayList> paths, Integer currentNode) { if (currentNode.equals(startNode)) { paths.add(new ArrayList(visited)); LinkedList nodes = mapa.adjacentNodes(currentNode); //System.out.println("visited:" + visited); for (Integer node : nodes) { //System.out.println("nodes:" + nodes); List temp = new ArrayList(); temp.addAll(visited); temp.add(node); findAllPaths(mapa, temp, paths, node); } } else { LinkedList nodes = mapa.adjacentNodes(currentNode); System.out.println("currentNode:" + currentNode); //System.out.println("nodes:" + nodes); for (Integer node : nodes) { if (visited.contains(node)) { continue; } List temp = new ArrayList(); temp.addAll(visited); System.out.println("visited:" + visited); temp.add(node); findAllPaths(mapa, temp, paths, node); } } } } 

程序接收输入的整数。 第一个是节点数，第二个是链接数，第三个是起始节点和结束注释，它们是相同的。 之后的所有整数表示节点之间的连接。

问题是，该算法只查找访问单个节点一次的所有路径。 我想要的是找到仅访问每个连接一次的所有路径的算法。 关于我如何做到这一点的任何想法？

Answer 1

你走在正确的轨道上 – 回溯是解决问题的一种巧妙方式。

要获取“仅使用相同边缘一次”的所有路径：在findAllPaths()使用边缘后 – 从边缘集中删除它[从此边缘的每个顶点的LinkedHashSet中删除连接] – 并递归调用。

从递归返回后 – 不要忘记“清理环境”并将此边缘添加回两个顶点。

您需要确保在修改时不会遇到迭代收集的麻烦。 [你不能这样做 – 这样做的结果是出乎意料的] – 所以你可能需要发送一个LinkedHashSet的副本[没有相关的边缘] – 而不是原始的。