仅在Graph访问中将C到D之间打印所有可能的路线

Question

处理图形遍历的问题给定开始和结束。 示例如果给定边路路线： （“ A”，“ B”） （“ A”，“ C”） （“广告”） （“公元前”） （“ b”，“ d”）

答案是： （C，B，D） （C，A，D） （C，A，B，D） （c，b，a，d）

我正在使用两种方法和prointretes（来源和目的地）实现此操作。

我创建了AddRoute来添加它们，但是很难找到一个好的解决方案来打印所有独特的路线。

到目前为止，解决方案是将其转换为邻接列表，并在其上运行DFS或BFS。我需要一些帮助为此创建BFS/DFS算法。

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

Answer 1

是的，使用BFS（或DFS）是在顶点之间获取所有简单路径的正确想法。

您只需要对这些算法进行一些修改：BFS使用global 访问标记数据。取而代之的是访问 每个分支本地的数据结构 - 作为递归实现的递归功能的参数。