如何显示 Bfs 的路径？

Question

所以我正在尝试制作 BFS 算法，并且能够计算出每 2 个节点之间的最短路径距离。但是每个节点（即节点 A）的邻居不仅是节点，它还是作为键的节点字典和每两个节点参与的匹配哈希集。现在，我不知道如何在 BFS 时存储路径正在工作...这是 returns 每个节点的邻居

的邻接函数

    Dictionary<string, Dictionary<string, HashSet<string>>> dic= new Dictionary<string, Dictionary < string,, HashSet < string >>>;

  public IEnumerable<KeyValuePair<string, HashSet<string>>> adjacentto(string v)
    {
        return dic[v];
    }

这是我的 BFS 函数：

    private Dictionary<string, int> dist = new Dictionary<string, int>();
    public void BFSDegree(Graph g, string s, string p)
    {
        Queue<string> q = new Queue<string>();

        dist.Add(s, 0);
        q.Enqueue(s);

        while (q.Count() != 0)
        {
            string j = q.Dequeue();
            //count = 0;
            foreach (KeyValuePair<string, HashSet<string>> h in g.adjacentto(j))
            {
                    if (!dist.ContainsKey(h.Key))
                    {
                        q.Enqueue(h.Key);
                        dist.Add(h.Key, 1 + dist[j]);


                    }

                    if (j == p)
                    {
                        Console.WriteLine("             " + dist[j]);                            
                        return;

                    }
                }


            }


        }

所以，我需要的是查看路径并读取哈希集的值，例如节点 A 和节点 B 在 3 场比赛中一起比赛，第 1 场、第 2 场、第 7 场，所以这应该是小路。所以我要打印到控制台“路径是匹配 1、匹配 2 或匹配 7”。如果我有 2 个节点没有一起参加比赛但他们都以节点 A 为主角2 个单独的匹配项，因此路径应该通过这 2 个匹配项中的任何一个。我如何在操作 BFS 时跟踪路径并存储路径？这是我从中读取图表的文件。

这就是我构建图表的方式

这就是我想要实现的

我通过使用 BFS 实现了第一个目标（学位）。但是现在我不知道如何实现 "chain" 或路径。链条只不过是路径中的电影数量，所以我认为如果我能够在 BFS 工作时保存路径（显示路径），我将能够实现链条。所以我的问题是最后一个目标如何保存路径并显示它。

Answer 1

为了找到从一个节点到另一个节点的最短路径，您可以跟踪每个节点的 parents。例如下图，当我运行 bfs 从 0 到 9 时，我跟踪每个节点到达并分配一个 parent。一旦分配了 parent，我就不会重新分配。因此，例如，如果我想找到从 0 到 9 的路径和长度，我只需回溯即 9-7-3-1-0 所以从 9 的 parent 开始并检查 7 的 parent 等等，直到你开始节点。然后我们可以很容易地得到长度。

至于查询，当你做类似 C/E 的事情时，你可以先运行 bfs 检查路径 "which should be 2 going from C-A-E" 当然可能还有其他路径，但我猜最短路径最适合您想要的东西？无论如何，假设我们选择路径 C-A-E 我们可以更新 Rel。按边数，因此 Rel = 2 然后 Chain 将是

//Nodes -> [C, A, E] 
//Parents ->[C, C, A]
Start from E // which is destination
Get movies of parent // parent is A, returns Movies 2
move to parent // now we are checking A
Get movies of parent // parent is C, returns Movies 1 Movies 7
break;

一到达源头就中断，反之亦然最后你有电影 2,1 和 7

一个parent只是一个节点的前身。例如，当你运行 Bfs 如果你从 0 到 1 那么 0 是 parent of 1

这是一个实现，希望能帮助您更好地理解它。

private Map<Integer, List<Integer>> _adjacencyList;
private Map<Integer, String> _movies; // will store neighbors here
private Queue<Integer> queue;
private int [] visited;

public BaconNumber(int V){// v here is number of vertices
    _adjacencyList = new HashMap<Integer, List<Integer>>();
    _movies = new HashMap<Integer, String>();
    queue = new LinkedList<Integer>();
    visited = new int[V];
    for(int i = 0; i < V; i++){
        _adjacencyList.put(i, new LinkedList<Integer>());// add a linkedlist             for each vertex
        visited[i] = -1;
    }
}

在这里放电影

private void fillNeighbors(){
    //0 = A, 1 = B, 2 = C, 3 = D, 4 = E
    _movies.put(0, "Z Movie 0 | B Movie 1 Movie 2 Movie 7 | C Movie 1 Movie 7 | D Movie 2 Movie 7 | E Movie 2");
    _movies.put(1, "A Movie 1 Movie 2 Movie 7 | C Movie 1 Movie 7 | D Movie 2 Movie 7 | E Movie 2");
    _movies.put(2, "A Movie 1 Movie 7 | B Movie 1 Movie 7 | D Movie 7");
    _movies.put(3, "E Movie 2 | A Movie 2 Movie 7 | B Movie 2 Movie 7 | C Movie 7");
    _movies.put(4, "D Movie 2 | A Movie 2 | B Movie 2 | F Movie 3 | G Movie 3");
}

获取电影。这需要两个参数。一个用于我们从何处获取电影，另一个用于我们正在寻找的节点。请注意，我将第二个参数转换为一个字母，所以它看起来像你所拥有的

public String getMovies(int s, int v){
    String result = "";
    // just getting corresponding character
    int rem = v % 26;
    char l = (char)((int)'A' + rem);
    //System.out.println("this is char "+l);
    String movie = _movies.get(s);
    String [] tokens = movie.split("\|");
    for(int i = 0; i < tokens.length; i++){
        String next = tokens[i];
        if(next.contains(String.valueOf(l))){
            result = next;
            break;
        }
    }
    return result;
}

现在是查询部分

String query(int source, int dest){
    List<Integer> nodes = new LinkedList<Integer>();
    int i, element;
    visited[source] = source;
    queue.add(source);
    while(!queue.isEmpty()){
        element = queue.remove();
        i = element;
        if(i == dest) break; // we stop as soon as we reach destination
        nodes.add(element);
        List<Integer> iList = getEdge(i);
        System.out.println(i+" -> "+iList);
        int x = 0; 
        while(x < iList.size()){
            int index = iList.get(x);
            if(visited[index] == -1){
                queue.add(index);
                visited[index] = i;
            }
            x++;
        }
    }
    String result = "";
    for(int x = dest; x >= 0; x= visited[x]){
        if(x == source) break; // we are done
        if(visited[x] != -1){
            result += getMovies(x,visited[x]); // get predecessor of x movies from x
        }
    }

    return result;
}

如何显示 Bfs 的路径？

How do I show the path of Bfs?

c#

graph

breadth-first-search