深度优先搜索点到点的所有路径用Java实现
时间: 2023-05-29 17:06:56 浏览: 114
以下是使用Java实现深度优先搜索点到点的所有路径的示例代码:
```
import java.util.ArrayList;
import java.util.List;
public class DFS {
private int[][] graph;
private boolean[] visited;
private List<List<Integer>> paths;
public DFS(int[][] graph) {
this.graph = graph;
visited = new boolean[graph.length];
paths = new ArrayList<>();
}
public List<List<Integer>> findAllPaths(int start, int end) {
List<Integer> path = new ArrayList<>();
path.add(start);
dfs(start, end, path);
return paths;
}
private void dfs(int current, int end, List<Integer> path) {
visited[current] = true;
if (current == end) {
paths.add(new ArrayList<>(path));
} else {
for (int i = 0; i < graph[current].length; i++) {
if (graph[current][i] == 1 && !visited[i]) {
path.add(i);
dfs(i, end, path);
path.remove(path.size() - 1);
}
}
}
visited[current] = false;
}
}
```
在这个示例中,我们使用一个二维数组来表示图,其中数组的第一维表示每个节点,第二维表示与该节点相邻的节点。如果两个节点之间有边相连,则数组中相应位置的值为1,否则为0。我们还使用一个布尔数组来跟踪每个节点是否已被访问过,以避免重复访问。
我们定义了一个`findAllPaths`方法来查找从起点到终点的所有路径。在该方法中,我们开始遍历从起点开始的所有可能路径,并将它们添加到路径列表中。我们使用一个递归函数`dfs`来实现深度优先搜索。在该函数中,我们首先将当前节点标记为已访问,然后遍历所有与该节点相邻的未访问节点。对于每个未访问节点,我们将其添加到当前路径中,并继续搜索从该节点开始的路径。如果该节点是终点,则将当前路径添加到路径列表中。最后,我们将当前节点标记为未访问,以允许在后续搜索中访问该节点。
在主程序中,我们可以使用以下代码来测试`DFS`类:
```
public static void main(String[] args) {
int[][] graph = {
{0, 1, 1, 0, 0},
{1, 0, 1, 1, 0},
{1, 1, 0, 1, 1},
{0, 1, 1, 0, 1},
{0, 0, 1, 1, 0}
};
DFS dfs = new DFS(graph);
List<List<Integer>> paths = dfs.findAllPaths(0, 4);
for (List<Integer> path : paths) {
System.out.println(path);
}
}
```
在这个例子中,我们使用一个小的示例图来测试`DFS`类。我们将起点设置为0,终点设置为4,并查找从起点到终点的所有路径。我们将所有找到的路径打印到控制台上。