dfs深度优先遍历 java
时间: 2024-03-08 16:43:41 浏览: 34
深度优先搜索(DFS)是一种常用的图遍历算法,它可以用来遍历或搜索图中的节点。在DFS中,从一个起始节点开始,沿着一条路径尽可能深入地访问节点,直到无法继续深入为止,然后回溯到上一个节点,继续访问其他未被访问的节点,直到所有节点都被访问为止。
在Java中,可以使用递归或者栈来实现DFS算法。下面是一个使用递归实现DFS的示例代码:
```java
import java.util.*;
class Graph {
private int V; // 图中节点的数量
private LinkedList<Integer> adj[]; // 邻接表表示图
// 构造函数
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
// 添加边
void addEdge(int v, int w) {
adj[v].add(w);
}
// 递归实现DFS
void DFSUtil(int v, boolean visited[]) {
visited[v] = true;
System.out.print(v + " ");
Iterator<Integer> i = adj[v].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n])
DFSUtil(n, visited);
}
}
// 对外公开的DFS接口
void DFS(int v) {
boolean visited[] = new boolean[V];
DFSUtil(v, visited);
}
}
public class Main {
public static void main(String args[]) {
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
System.out.println("节点2开始的DFS遍历结果:");
g.DFS(2);
}
}
```
上述代码中,我们首先定义了一个`Graph`类来表示图,其中使用邻接表来存储图的结构。然后,我们实现了`DFSUtil`方法来递归地进行DFS遍历,并在遍历过中打印节点的值。最后,在`main`方法中创建一个图对象,并调用`DFS`方法来进行DFS遍历。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)