java - 使用DFS和Java进行寻路

我正在开发一个搜索算法来查找图中的路径。在这个算法中，我需要在一个无向的，非加权的图中找到所有的路径，这个图只经过一次图连接。它必须在同一个节点中开始和结束。目前，我的程序所做的，是找到所有的路径，通过每个节点只有一次。我需要的是连接而不是节点。
这是我的代码：

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 int getNumLinks(){
        return 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 adj) {
        LinkedHashSet<Integer> adjacente = map.get(adj);
        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++){
        int inicio = input.nextInt();
        int fim = input.nextInt();
        mapa.addLink(inicio, fim);

    }

    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();

        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);

        for (Integer node : nodes) {

            List<Integer> temp = new ArrayList<Integer>();
            temp.addAll(visited);
            temp.add(node);
            System.out.println("temp:" + temp);

            findAllPaths(mapa, temp, paths, node);
        }
    }
    else {
        LinkedList<Integer> nodes = mapa.adjacentNodes(currentNode);
        System.out.println("currentNode:" + currentNode);

        List<Integer> inseridos = new ArrayList<Integer>();

        for (Integer node : nodes) {
            if (visited.contains(node)) {
                continue;
            }
            List<Integer> temp = new ArrayList<Integer>();
            inseridos.add(currentNode);
            temp.addAll(visited);
            System.out.println("visited:" + visited);

            temp.add(node);

            findAllPaths(mapa, temp, paths, node);
        }
    }
}
}

程序接收输入的整数。第一个是节点数，第二个是链接数，第三个是开始节点和结束注释，它们是相同的后面的所有整数表示节点之间的连接。
例如：程序接收“1 2 3 4 5 6”1是节点数，2是链路数，3是起始节点，34是从节点3到节点4的连接，56是从节点5到6的连接。
现在，我认为以下代码：

if (visited.contains(node)) {
 continue;
}

使程序不经过每个节点一次以上。我需要帮助转换我的程序，使其只通过每个连接一次，而不是通过每个节点一次。
我能怎么做吗？

最佳答案

我想你是说边缘而不是联系。这样，您需要找到包含所有边的所有循环（在同一节点中开始和结束的路径）。
通过每一条边一次的循环称为欧拉路径。你可以看到一个解决方案here。

关于java - 使用DFS和Java进行寻路，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9812675/