java - 如何在算法 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 迭代期间填充此 map 。

稍后 - 您可以通过简单地从目标节点 [在 map 中] 开始重建路径 - 直到您回到源头。如果枚举顶点，则此 map 可以实现为数组。