Java实现无向图两点间所有无重复节点路径的算法求助

需求为输出无向图中指定起点到终点、所有节点仅访问一次的全部可能路径，核心实现两个方法：

• addRoutes：添加图的边，构建邻接表（该方法已完成，可正常存储边结构）
• printRoutes：接收起点start和终点des参数，输出两点间所有符合节点不重复要求的路径

测试用例 #

使用如下边集合构建无向图：

("A","B")
("A","C")
("A","D")
("B","C")
("B","D")

查询C到D的所有符合要求的路径，正确结果为：

• (C,B,D)
• (C,A,D)
• (C,A,B,D)
• (C,B,A,D)

现有代码问题 #

当前已基于邻接表编写了部分BFS实现的printRoutes方法，但存在逻辑错误，无法正确输出所有唯一路径，未完成的Java代码如下：

public class Graph{
    List<List<String>> edges= new ArrayList<>();
    Map<String, Set<String>> adjList= new HashMap<>();

     void addRoutes(String start, String des) {
         List<String> temp1 = new ArrayList<>();
         temp1.add(start);
         temp1.add(des);
        edges.add(temp1);
        adjList.putIfAbsent(start, new HashSet<>());
        adjList.putIfAbsent(des, new HashSet<>());
        adjList.get(start).add(des);
        adjList.get(des).add(start);
    }
        void printRoutes(String start, String des) {
     Set<String> visited = new HashSet<>();
     // Mark the current node as visited and enqueue it

     // Create a queue for BFS
     Queue<List<String> > queue = new LinkedList<>();
     // Path vector to store the current path
     List<String> path = new ArrayList<>();
     path.add(start);
     queue.offer(path);

     while (!queue.isEmpty()) {
         path = queue.poll();
         String last = path.get(path.size() -1);
         if (last == des) {
             int size = path.size();
             for(String v : path) {
                 System.out.print(v + " ");
             }
         }
         Set<String> lastNode = adjList.get(last);
         for (String neig : adjList.get(start)) {
             if (!visited.contains(neig)) {
                 List<String> newpath = new ArrayList(path);
                 visited.add(start);
                 queue.offer(newpath);
             }

         }
     }
}
    public static void main(String[] args) {
        Graph g = new Graph();
        g.addRoutes("A","B");
        g.addRoutes("A","C");
        g.addRoutes("A","D");
        g.addRoutes("B","C");
        g.addRoutes("B","D");
        System.out.println(g.edges);
        System.out.println(g.adjList);
    }
}

1. 全局共用一个visited集合，BFS中不同路径的访问状态互相干扰，会漏掉合法分支
2. 遍历邻接节点时错误取了起点start的邻接表，没有取当前路径最后一个节点的邻接表
3. 构造新路径时没有把邻接节点加入新路径，路径长度不会增长
4. 字符串相等判断用了==而非equals，终点命中逻辑失效
5. 无向图找无重复节点路径不需要全局访问标记，直接判断节点是否在当前路径即可，避免跨分支状态污染

DFS版本（逻辑更简洁，推荐使用） #

void printRoutes(String start, String des) {
    List<String> path = new ArrayList<>();
    path.add(start);
    dfs(start, des, path);
}

private void dfs(String current, String des, List<String> currentPath) {
    // 到达终点，输出当前路径
    if (current.equals(des)) {
        System.out.println(currentPath);
        return;
    }
    // 遍历当前节点所有邻接节点
    for (String neighbor : adjList.get(current)) {
        // 节点不在当前路径中才继续遍历，避免重复访问
        if (!currentPath.contains(neighbor)) {
            currentPath.add(neighbor);
            dfs(neighbor, des, currentPath);
            // 回溯，移除当前节点尝试其他分支
            currentPath.remove(currentPath.size() - 1);
        }
    }
}

BFS版本 #

void printRoutes(String start, String des) {
    Queue<List<String>> queue = new LinkedList<>();
    List<String> initialPath = new ArrayList<>();
    initialPath.add(start);
    queue.offer(initialPath);

    while (!queue.isEmpty()) {
        List<String> currentPath = queue.poll();
        String lastNode = currentPath.get(currentPath.size() - 1);
        // 到达终点输出路径
        if (lastNode.equals(des)) {
            System.out.println(currentPath);
            continue;
        }
        // 遍历路径最后一个节点的邻接节点
        for (String neighbor : adjList.get(lastNode)) {
            // 邻接节点不在当前路径中才生成新路径入队
            if (!currentPath.contains(neighbor)) {
                List<String> newPath = new ArrayList<>(currentPath);
                newPath.add(neighbor);
                queue.offer(newPath);
            }
        }
    }
}

两个版本运行后均能输出符合预期的结果：

[C, A, D]
[C, B, D]
[C, A, B, D]
[C, B, A, D]

内容的提问来源于stack exchange，提问作者jesjolly