java - 使用java在图中查找路径算法

Question

我必须在 java 中为一个学校项目实现一个搜索算法。在这个算法中，我需要在一个无向图中找到一条仅通过每个链接一次并在起始节点结束的路径。我正在尝试使用带回溯的 DFS 来解决这个问题，但我在实现它时遇到了麻烦。这是我的代码:

import java.util.*;

public class Graph {

    private Map<Integer, LinkedHashSet<Integer>> map = 
        new HashMap<Integer, LinkedHashSet<Integer>>();
    private int startNode;
    private int numLinks;



    public Graph(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;

    Graph mapa = new Graph(startNode, numLinks);

    for(int i = 0; i<numLinks; i++){
        mapa.addLink(input.nextInt(), input.nextInt());

    }

    List<ArrayList<Integer>> paths = new ArrayList<ArrayList<Integer>>();
    Integer currentNode = startNode;
    List<Integer> visited = new ArrayList<Integer>();
    visited.add(startNode);
    mapa.findAllPaths(mapa, visited, paths, currentNode);

    for(ArrayList<Integer> path : paths){
        for (Integer node : path) {
            System.out.print(node);
            System.out.print(" ");
        }
        System.out.println();
    }

}

private void findAllPaths(Graph mapa, List<Integer> visited,
        List<ArrayList<Integer>> paths, Integer currentNode) {


    if (currentNode.equals(startNode)) { 
        paths.add(new ArrayList<Integer>(visited));
        return;
    }

    else {
        LinkedList<Integer> nodes = mapa.adjacentNodes(currentNode);    
        for (Integer node : nodes) {
            if (visited.contains(node)) {
                continue;
            } 
            List<Integer> temp = new ArrayList<Integer>();
            temp.addAll(visited);
            temp.add(node);          
            findAllPaths(mapa, temp, paths, node);
        }
    }

} 

}

程序应该在他的输入上接收整数，其中第一个是节点数，第二个是链接数，第三个是起始节点(也是结束节点)，所有后面的整数表示节点之间的链接。

最终的目标是打印一行整数。这个整数代表我访问每个节点以完成路径的顺序。目前测试，它只打印一个整数，代表第一个节点。

我认为我的问题要么是填充图表，要么是填充相邻列表。有人可以帮助我吗？

Answer 1

问题是当您调用 mapa.findAllPaths(mapa, visited, paths, currentNode); 时，您实际上并没有找到所有路径。您只找到一条路径(即当前节点)并返回:

private void findAllPaths(Graph mapa, List<Integer> visited,
        List<ArrayList<Integer>> paths, Integer currentNode) {

    if (currentNode.equals(startNode)) { 
        paths.add(new ArrayList<Integer>(visited));
        return;// <--- WRONG!!!
    } else {
        // The else is never executed!
    }
} 

您应该有一个循环或递归调用 findAllPaths 直到找到所有路径。