在深度优先搜索Java上添加路径的边

Question

我试图在一个depth first search algorithm上实现directed graph。图存在顶点(V Vertex)，每个顶点都有一组边(E Edge)。每个边都有一个指向下一个(.getTo())的指针和一个指向前一个(.getFrom())的指针。我想找到从起始顶点到目标顶点的边的路径。为了存储和创建路径，我创建了一个助手类DGPath。我想用递归的方式来做这件事。

在DGPath创建路径助手类下面：

/**
     * represents a path of connected vertices and edges in the graph
     */
    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;
        }
    }

在Depth first search method下面

/**
     * Uses a depth-first search algorithm to find a path from the start vertex to the target vertex in the graph
     * The path.totalWeight should indicate the number of edges in the result path
     * All vertices that are being visited by the search should also be registered in path.visited
     *
     * @param startId the id of the start Vertex
     * @param targetId the id of the end Vertex
     * @return the DGpath for the path from start to target
     * returns null if either start or target cannot be matched with a vertex in the graph
     * or no path can be found from start to target
     */
    public DGPath depthFirstSearch(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 recursive depth-first-search
        //  (create another private recursive helper method)
        //  register all visited vertices while going, for statistical purposes
        //  if you hit the target: complete the path and bail out !!!

        for (E edge : start.getEdges()) {
            if (!path.getVisited().contains(target)) {
                dfsHelper(edge.getTo(), path.visited);
            } else {
                return path;
            }
        }

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

最后，下面是深度优先搜索方法的recursive助手方法：

private void dfsHelper(V current, Set<V> discovered) {
        discovered.add(current);
        for (E edge : current.getEdges()) {
            while(edge.getTo() != null){
                V nextV = edge.getTo();
                if (!discovered.contains(nextV)) {
                    dfsHelper(nextV, discovered);
                }
            }
        }

    }

这段代码现在不起作用，它一直停留在递归中。

如何更改此代码以找到从开始顶点到目标顶点的正确路径?如何在DGPath.edges中保存用于从开始到目标的边？

Answer 1

我认为问题是在for循环中调用dfsHelper函数(我看不出为什么需要循环！！)。对于每次迭代，您必须在循环结束时清空path.visited，然后再次执行path.visited.add(start);。

关于第二个问题，为路径定义另一个字段，比如边，每当您向path.visited添加一个新节点时，将相应的边缘添加到path.edges (不要忘记为每次迭代刷新path.edges类似于path.visited )，在调用depthFirstSearch之后，path.visited将得到您想要的

Answer 2

我用保存边的方法修正了工作算法：

DGPath助手类仍然与上面相同

DFS方法和递归的“助手”：

public DGPath depthFirstSearch(String startId, String targetId) {
        // get node/vertex on ID
        V start = this.getVertexById(startId);
        V target = this.getVertexById(targetId);
        // if they dont exist return null
        if (start == null || target == null) return null;
        // create new path
        DGPath path = new DGPath();
        // set starting node/vertex
        path.start = start;

        // easy target
        if (start == target) {
            path.visited.add(start);
            return path;
        }

        // return the recursive method with starting point, target and the path
        return dfsRecursive(path.start, target, path);
    }

    private DGPath dfsRecursive(V current, V target, DGPath path) {
        // if node/vertex is already visited we have no path
        if (path.getVisited().contains(current)) {
            return null;
        }
        // add current node/vertex to visited set
        path.getVisited().add(current);
        // if we reach the destination we return the path
        if (current.equals(target)) {
            return path;
        }
        // else we go check all de edges connected to the vertex
        for (E edge : current.getEdges()){
            // if there is a new path we continue recursive until destination is reached
            if (dfsRecursive(edge.getTo(), target, path) != null) {
                // we add the edges as first in the set of edges to create the path
                path.getEdges().addFirst(edge);
                return path;
            }
        }
        return null;
    }