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

Question

早上好！

我正在开发一种算法，以查找无向图而不是加权图中的所有路径。我目前正在使用具有回溯功能的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);
        }
    }

}

}

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

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

Answer 1

您处在正确的轨道上-回溯是解决此问题的一种好方法。

要获得所有“仅使用同一条边缘一次”的路径：在中使用一条边缘后findAllPaths()-从一组边缘中将其删除[从LinkedHashSet该边缘的每个顶点的连接中删除连接]-并递归调用。

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

您将需要确保在修改集合时不会遇到迭代集合的麻烦。[您无法执行此操作-这样做的结果是意外的]-因此您可能需要发送LinkedHashSets
的副本[没有相关的边缘]-而不是原始副本。