使用BFS打印所有可能的路径+最多不超过K个边缘

Question

我看到All Possible paths K edges far中提供了类似的解决方案。但我正在寻找专家指导-如何解决每个以下是对常见问题的限制：

a)It should be a clever BFS solution 
b)The signature should be at least **printAllGraphPaths( Node source, Node target,....)** [not integer] 
c)Source and target should be internal nodes [not like source having zero in-degree and target with zero out-degree]

d）节点虽然可以是不同的实例，但是可以具有相同的值`

e)Result can't be more than K edges. 
f)Same node can be visited multiple times (eg. Node(2) )

g）可以有周期

给定source = 1＆target = 3，然后printAllPossiblePaths：

    1 -> 2 -> 3    
    1 -> 5 -> 3
    1 -> 5 -> 2 -> 3   
    1 -> 6 -> 5 -> 2 -> 3
    1 -> 6 -> 5 -> 3

  for duplicate node 5 there will be three more extra paths
    1 -> 5 -> 2 -> 5 -> 3 
    1 -> 2 -> 5 -> 3
    1 -> 6 -> 5 -> 2 -> 5 -> 3

后续补充问题：

1. 在哪种情况下以及为什么使用DFS或BFS更好？

Answer 1

我将为您提供一个明智的解决方案，但不实施。

目标是能够打印路径，但不会在枚举不需要在正确位置的路径时浪费时间。因此，您需要一个看起来像这样的数据结构：

by node
    by length of remaining path
        list of nodes you could go to to get to the desired target.

无论有多少路径，此数据结构的大小都是多项式，可以使用以target（不是源）开头的标准动态编程技术在多项式时间内生成。这将是广度优先的算法。

现在您获取源节点和k。使用此数据结构，您可以对数据结构进行深度优先搜索，并随心所欲地打印路径。这将花费与打印多少数据成比例的时间。但是，您绝不会走错路，探索不可行的道路。

奖金优化。我描述的算法将起作用。但是对于非常大的图和非常短的k（想想“在大型社交网络中从人A到人B的路径”）的特殊情况，可以大大改善。改进是从目标开始并返回ceil(k/2)，然后从源开始并（通过反转路径结构）然后向前floor(k/2)。将两者的边缘存储在哈希结构中。现在我们穿过条纹的交点，并在两个方向上构建路径。

此优化始终可以完成。但是除非是一种特殊情况，否则不会有所改善。

要了解为什么这是一种改进，请假设您每人的平均连接数为50，并且您正在尝试找到从您到总统的长度为6的路径。我描述的第一个版本基本上是必须构造一个整个社交图大小的数据结构。从字面上看，这是数十亿的事情。但是，通过奖金优化，您可以绘制一个圆圈，该圆圈的大小成千上万，与总统的大小相同，然后相交。因此，预处理步骤需要少于一百万次操作。这比数十亿要好得多！

Answer 2

我已经成功创建了我的解决方案代码！随时讨论并建议提高其复杂性（时间和空间）或一些更好的方法。人们可能会发现它过度设计，但我的意思是...在现实生活中，谁输入了两个int作为src和dest？我也需要坚固的节点：

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Queue;

public class AllPathsAdhocSrcDestNodes{

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

    public List<List<Integer>> bfs(Graph g, Node src,Node dest,int m){
        int depth =0; List<Integer> tempPath = null;

        Queue<Node> q = new ArrayDeque<>();
        src.path.add(src.value);
        q.add(src);

        while(!q.isEmpty()){ 

            Node u = q.poll();                
            depth = u.depth;  

            if (depth > m)
                continue;

            if(u.value == dest.value && depth <= m){
                allPaths.add(u.path);
            } 

            List<Node> neighbours =  g.adjMap.get(u);
            for(int k=0;k<neighbours.size();k++){
              Node v = neighbours.get(k);
              tempPath = new ArrayList<>(u.path);
              tempPath.add(v.value);
              q.add(new Node(v.value,u.depth+1,tempPath));

            }

        }
        return allPaths;
    }

   /*------------------------ Driver program ---------------------------------*/     
        public static void main(String[] args){
        // List of graph nodes & edges as per diagram
            Node[] n = { new Node(0),new Node(1),new Node(2),new Node(3),new Node(4),new Node(5),new Node(6),new Node(7) };


            Edge[] e = {
                            new Edge(n[0], n[6]), 
                            new Edge(n[0], n[1]), 
                            new Edge(n[1], n[6]),
                            new Edge(n[1], n[5]), 
                            new Edge(n[1], n[2]), 
                            new Edge(n[2], n[3]),
                            new Edge(n[3], n[4]), 
                            new Edge(n[5], n[2]), 
                            new Edge(n[5], n[3]),
                            new Edge(n[5], n[4]), 
                            new Edge(n[6], n[5]), 
                            new Edge(n[7], n[6]),
                            new Edge(n[7], n[1])
                        };



        // construct graph : Graph acc to CLRS is G(V,E) nothing else
          Graph g = new Graph(Arrays.asList(n),Arrays.asList(e));

        //inputs
          Node src = n[1], dest = n[3];
          int m = 4;

        // Do modified BFS traversal from source vertex src
          AllPathsAdhocSrcDestNodes tester = new AllPathsAdhocSrcDestNodes();
          System.out.println(tester.bfs(g, src, dest,m));
    }


    public static void printQ(Queue<Node> q,int k){
        System.out.println(k+"queue:"+q);
    }
}

class Edge{
    Node source, dest;

    public Edge(Node source, Node dest) {
        this.source = source;
        this.dest = dest;
    }
}

class Graph{
    List<Node> vertices;
    List<Edge> edges;
    HashMap<Node,List<Node>> adjMap = null;

    Graph(List<Node> vertices,List<Edge> edges)
    {
        this.vertices=vertices;
        this.edges=edges;

        int N = vertices.size();

        adjMap = new HashMap<>(N);
        for (int i = 0; i < N; i++) {
            adjMap.put(vertices.get(i), new ArrayList<>());
        }

        // add edges to the directed graph
        for (int i = 0; i < edges.size(); i++){            
            Node src = edges.get(i).source;
            Node dest = edges.get(i).dest;

            adjMap.get(src).add(dest);
        }
    }
}

class Node{
        int value;
        int depth;
        List<Integer> path = new ArrayList<>(); //path from root till this node just for printing we dont need List<Node>

        public Node(int value) {
            this.value = value;
        }

        public Node(int value,int depth,List<Integer> tempPath) {
            this.value = value;
            this.depth = depth;
            this.path = tempPath;
        }

        @Override
        public boolean equals(Object obj){
            if(obj == null || !(getClass()==obj.getClass()) ||  this.value != ((Node)obj).value )
                return false;
            else
                return true;
        }
        @Override
        public int hashCode(){
            return this.value;
        }
        public String toString() {
            return Arrays.asList(value).toString();
        }
}

如果您喜欢我的努力，请放弃评论