在广度优先搜索中保存遍历的边

Question

下面是我的bfs算法，该算法在给定开始和目标的情况下工作并找到节点。但是我想在linkedList中保存所用路径的边来绘制路径。

我的BFS：

public DGPath breadthFirstSearch(String startId, String targetId) {

        V start = this.getVertexById(startId);
        V target = this.getVertexById(targetId);
        if (start == null || target == null) return null;

        DGPath path = new DGPath();
        path.start = start;
        path.visited.add(start);

        // easy target
        if (start == target) return path;

        // TODO calculate the path from start to target by breadth-first-search
        //  register all visited vertices while going, for statistical purposes
        //  if you hit the target: complete the path and bail out !!!
        Queue<V> fifoQueue = new LinkedList<>();
        Map<V,V> visitedFrom = new HashMap<>();

        fifoQueue.offer(start);
        visitedFrom.put(start, null);

        while (!fifoQueue.isEmpty()) {
            V current = fifoQueue.poll();
            for (E e : current.getEdges()) {
                V neighbour = e.getTo();
                path.visited.add(neighbour);
                if (neighbour == target) {
                    while (current != null) {
                        path.getEdges().addFirst(e);
                        current = visitedFrom.get(current);

                    }
                    return path;
                } else if (!visitedFrom.containsKey(neighbour)) {
                    visitedFrom.put(neighbour,current);
                    fifoQueue.offer(neighbour);
                }
            }
        }


        // no path found, graph was not connected ???
        return null;
    }

DGPath是创建路径的类，如下所示：

public class DGPath {
        private V start = null;
        private LinkedList<E> edges = new LinkedList<>();
        private double totalWeight = 0.0;
        private Set<V> visited = new HashSet<>();

        /**
         * representation invariants:
         * 1. The edges are connected by vertices, i.e. FOR ALL i: 0 < i < edges.length: edges[i].from == edges[i-1].to
         * 2. The path begins at vertex == start
         * 3. if edges is empty, the path also ends at vertex == start
         * otherwise edges[0].from == start and the path continues along edges[i].to for all 0 <= i < edges.length
         **/

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder(
                    String.format("Weight=%f Length=%d Visited=%d (",
                            this.totalWeight, 1 + this.edges.size(), this.visited.size()));
            sb.append(start.getId());
            for (E e : edges) {
                sb.append(", " + e.getTo().getId());
            }
            sb.append(")");
            return sb.toString();
        }

        public V getStart() {
            return start;
        }

        public LinkedList<E> getEdges() {
            return edges;
        }

        public double getTotalWeight() {
            return totalWeight;
        }

        public Set<V> getVisited() {
            return visited;
        }
    }

我想从BGPath类(在我的BFS algo方法中名为path )将正确的edges保存在de linkedlist edges中。因此，我已经将使用过的顶点保存在贴图中，以便返回到根。但是当我将边添加到路径中时，它只是保存了多次使用的最后一条边。问题是顶点可以有多条边，所以我需要添加前一个边指向最后一个“当前”的边，直到我回到根。但是我不能想出正确的方法来做这件事。

现在我将边添加到边列表的那一行是：path.getEdges().add(e)

Answer 1

我认为，你的问题是同一条线，你在其中添加边，这条线一次又一次地在内部while循环中添加相同的边，所以你只是向后遍历，而不是将这些节点添加到你的边列表中。

我觉得应该是这样的

while (!fifoQueue.isEmpty()) {
            V current = fifoQueue.poll();
            for (E e : current.getEdges()) {
                V neighbour = e.getTo();
                path.visited.add(neighbour);
                if (neighbour == target) {
                    path.getEdges().addFirst(e):
                    while (current != null) {
                        path.getEdges().addFirst(current) ;
                        current = visitedFrom.get(current);
                    }
                    return path;
                } else if (!visitedFrom.containsKey(neighbour)) {
                    visitedFrom.put(neighbour,current);
                    fifoQueue.offer(neighbour);
                }
            }
        }


        // no path found, graph was not connected ???
        return null;
    }