使用 BFS 打印所有可能的路径 + 不超过 K 边远

Question

I see similar solution is available in All Possible paths K edges far . But I am looking for experts guidance - how to solve each of the following constraints over the common question :

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

Follow-up additional Question:

DFS 或 BFS 在哪种情况下哪个更好，为什么？

Answer 1

我会为您列出一个巧妙的解决方案，但不会实施它。

我们的目标是能够打印路径，而不是浪费时间枚举不希望出现在正确位置的路径。所以你想要一个看起来像这样的数据结构：

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

无论有多少条路径，此数据结构的大小都是多项式的，可以使用标准动态规划技术在多项式时间内生成，从目标（不是源).这将是一个广度优先算法。

现在获取源节点和 k。使用此数据结构，您可以通过数据结构进行深度优先搜索，并在搜索过程中打印路径。这将花费与您打印的数据量成正比的时间。但你永远不会走错路，也不会探索行不通的路。

奖金优化。我描述的算法将起作用。但对于非常大的图和非常短的 k（认为 "path from person A to person B in a large social network"）的特殊情况，它可以得到显着改善。改进是从目标开始往回ceil(k/2)和从源开始并且（通过反转路径结构）向前floor(k/2)。将两者的边缘存储在哈希结构中。现在我们穿过边缘的交叉点，并在两个方向上构建路径。

这个优化总是可以做的。但除非在一个特殊情况下，否则不会有任何改进。

要了解为什么它是一个改进，假设您平均每人有 50 个连接，并且您正在尝试找到从您到总统的长度为 6 的路径。我描述的第一个版本基本上以必须构建整个社交图的大小的数据结构而告终。这实际上是数十亿的东西。但是通过奖金优化，你从你那里画了一个大小为数十万的圆圈，然后从总统那里画了一个同样大小的圆圈，然后与它们相交。因此，预处理步骤只需不到一百万次操作。这比数十亿好多了！

Answer 2

我已经成功创建了我的解决方案代码！请随意讨论并建议改进其复杂性（时间 & space）或一些更好的方法。人们可能会发现它过度设计，但我的观点是......在现实生活中谁输入了两个整数作为 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 String.valueOf(value);
        }
}

如果您喜欢我的努力，请发表评论

使用 BFS 打印所有可能的路径 + 不超过 K 边远

Print all possible paths using BFS + no more than K edges far

java

algorithm

graph-algorithm