在Depth first Search Java中将路径的边缘添加到列表中

Question

我正在尝试在directed graph上实现depth first search algorithm。该图存在多个顶点(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函数(我看不出为什么需要循环！！(。对于每次迭代，您必须清空循环结束时访问的路径.visited，然后再次执行path.visited.add(start);

关于第二个问题，定义路径的另一个字段，比如边，每当您向path.visited添加新节点时，将相应的边添加到path.edges(不要忘记在每次迭代中刷新路径。边，如path.visited(在调用depthFirstSearch后，访问的路径将具有您想要的内容

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;
}