如何在BFS算法中跟踪路径

Question

我正在寻找一种为我的bfs算法跟踪路径的方法，但我不知道如何跟踪。也许我错了，但我认为我确实需要一个双ArrayList，以节省一切可能的方式。在以下示例中，这意味着：

​

​

1. 列队名单: 6-3-1
2. 排列名单: 6-3-5
3. 排列名单: 5-9-7
4. 排列名单: 6-9-10

如果从3到9之间有关联的话，情况会更糟。

    public List<E> BFS(N source, N target)
    {
        ArrayList<ArrayList<N>> nodes_paths = new ArrayList<ArrayList<N>>();
        ArrayList<N> nodes_list = new ArrayList<N>(graph.getNodes());
        N current_node;

        Queue <N> list = new LinkedList<N>();
        HashMap<N, Boolean> already_visited = new HashMap<N, Boolean>();
//      mark all nodes in HashMap as not visited
        for(int i=0; i<nodes_list.size(); i++)
        {
            already_visited.put(nodes_list.get(i), false);
        }

        ArrayList<N> successors = new ArrayList<N>();
        list.add(source);

        while(!list.isEmpty())
        {
            current_node = list.poll();
            already_visited.put(current_node, true);
          //need to add the node to any path, but don't know to which?
            if(current_node.equals(target))
            {

            }
            else
            {
                successors = new ArrayList<N>(graph.getSuccessors(current_node));
                for(int j=0; j<successors.size(); j++)
                {
                    if(!already_visited.get(successors.get(j)))
                    {
                        already_visited.put(successors.get(j), true);
                        list.add(successors.get(j));
                    }
                }
            }
        }


//      need the path array here!
        ArrayList<E> edges_list = new ArrayList<E>(graph.getEdges());
        ArrayList<E> path_edges = new ArrayList<E>();
        for(int k=0; k<path.size()-1; k++)  //If there are path.size nodes, so therer are only path.size-1 edges
        {
            for(int l=0; l<edges_list.size(); l++)
            {
                if(path.get(k).equals(edges_list.get(l).getSource()) && path.get(k+1).equals(edges_list.get(l).getTarget()))
                {
                    path_edges.add(edges_list.get(l));
                }
            }
        }

        return path_edges;


    }

Answer 1

这种方法需要进行复杂的管理，您可以存储一个从顶点到顶点的映射: v -> v，它将从每个节点v映射到“发现”v的顶点u。

您将在BFS迭代期间填充此映射。

稍后，您可以通过简单地从映射中的目标节点恢复路径，直到返回到源。如果枚举顶点，则可以将此映射实现为数组。