深度优先搜索一个点至另一个点的所有路径,用Java实现
时间: 2023-05-30 20:04:18 浏览: 89
以下是Java实现深度优先搜索一个点至另一个点的所有路径的示例代码:
```java
import java.util.ArrayList;
import java.util.List;
public class DFS {
public static List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
path.add(0); // add the starting node to the path
dfs(graph, 0, path, result);
return result;
}
private static void dfs(int[][] graph, int node, List<Integer> path, List<List<Integer>> result) {
if (node == graph.length - 1) { // if we reach the destination node
result.add(new ArrayList<>(path)); // add the path to the result list
return;
}
for (int neighbor : graph[node]) { // for each neighbor of the current node
path.add(neighbor); // add the neighbor to the path
dfs(graph, neighbor, path, result); // recursive call to dfs with the neighbor as the new node
path.remove(path.size() - 1); // remove the neighbor from the path
}
}
public static void main(String[] args) {
int[][] graph = {{1,2},{3},{3},{}}; // example graph
List<List<Integer>> paths = allPathsSourceTarget(graph);
System.out.println(paths);
}
}
```
在这个示例中,我们定义了一个`allPathsSourceTarget`方法,该方法接受一个图(用邻接表表示)作为参数,并返回从起始节点(0)到目标节点(最后一个节点)的所有路径。我们使用深度优先搜索(DFS)算法来查找所有路径。我们记录当前路径,并在我们到达目标节点时将其添加到结果列表中。
在DFS方法中,我们首先检查当前节点是否是目标节点。如果是,我们将当前路径添加到结果列表中。否则,我们遍历当前节点的所有邻居,并将它们添加到路径中。然后,我们递归调用DFS方法,以便在新邻居作为节点时继续查找路径。在回溯时,我们将最后一个邻居从路径中删除。
在主方法中,我们创建一个示例图,并调用`allPathsSourceTarget`方法以查找所有路径。我们将结果打印到控制台上。