早上好!
我正在开发一种算法来查找无向非加权图中的所有路径。我目前正在使用具有回溯功能的 DFS 算法来尝试执行此操作。这是我当前的代码:
import java.util.*;
public class dfs {
private static Map<Integer, LinkedHashSet<Integer>> map = new HashMap<Integer, LinkedHashSet<Integer>>();
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<Integer> adjacente = map.get(source);
if(adjacente==null) {
adjacente = new LinkedHashSet<Integer>();
map.put(source, adjacente);
}
adjacente.add(destiny);
}
public void addLink(int source, int destiny) {
addEdge(source, destiny);
addEdge(destiny, source);
}
public LinkedList<Integer> adjacentNodes(int last) {
LinkedHashSet<Integer> adjacente = map.get(last);
System.out.println("adjacentes:" + adjacente);
if(adjacente==null) {
return new LinkedList<Integer>();
}
return new LinkedList<Integer>(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<Integer>> paths = new ArrayList<ArrayList<Integer>>();
List<Integer> visited = new ArrayList<Integer>();
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<Integer> visited,
List<ArrayList<Integer>> paths, Integer currentNode) {
if (currentNode.equals(startNode)) {
paths.add(new ArrayList<Integer>(visited));
LinkedList<Integer> nodes = mapa.adjacentNodes(currentNode);
//System.out.println("visited:" + visited);
for (Integer node : nodes) {
//System.out.println("nodes:" + nodes);
List<Integer> temp = new ArrayList<Integer>();
temp.addAll(visited);
temp.add(node);
findAllPaths(mapa, temp, paths, node);
}
}
else {
LinkedList<Integer> nodes = mapa.adjacentNodes(currentNode);
System.out.println("currentNode:" + currentNode);
//System.out.println("nodes:" + nodes);
for (Integer node : nodes) {
if (visited.contains(node)) {
continue;
}
List<Integer> temp = new ArrayList<Integer>();
temp.addAll(visited);
System.out.println("visited:" + visited);
temp.add(node);
findAllPaths(mapa, temp, paths, node);
}
}
}
}
程序在其输入中接收整数。第一个是节点数,第二个是链接数,第三个是起始节点和结束注释,它们是相同的。后面的所有整数代表节点之间的连接。
问题是,该算法正在查找仅访问单个节点一次的所有路径。我想要的是找到仅访问每个连接一次的所有路径的算法。 我知道如何才能做到这一点吗?
最佳答案
你走在正确的轨道上 - 回溯是解决这个问题的好方法。
要获取“仅使用同一条边一次”的所有路径:
在 findAllPaths()
中使用边后 - 从边集中删除它[从该边的每个顶点的 LinkedHashSet
中删除连接] - 并递归调用。
从递归返回后 - 不要忘记“清理环境”并将这条边添加回两个顶点。
您需要确保在修改集合时不会遇到迭代集合的麻烦。 [您不能这样做 - 这样做的结果是意想不到的] - 因此您可能需要发送 LinkedHashSet
的副本 [不带相关边缘] - 而不是原始副本。
关于java - 使用 DFS 查找图中的所有路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9803143/