Java中深度优先搜索算法
时间: 2024-06-13 12:07:54 浏览: 12
以下是Java中深度优先搜索算法的实现步骤:
1. 创建一个栈来存储遍历过的节点。
2. 将起始节点压入栈中。
3. 创建一个布尔类型的数组来记录每个节点是否被访问过,并将起始节点标记为已访问。
4. 当栈不为空时,执行以下操作:
- 弹出栈顶节点。
- 遍历该节点的所有未访问过的邻居节点,将其压入栈中,并标记为已访问。
5. 重复步骤4,直到栈为空。
下面是Java代码示例:
```java
import java.util.Stack;
public class DFS {
public void dfs(Node start) {
Stack<Node> stack = new Stack<>();
boolean[] visited = new boolean[100];
stack.push(start);
visited[start.id] = true;
while (!stack.isEmpty()) {
Node node = stack.pop();
System.out.print(node.id + " ");
for (Node neighbor : node.neighbors) {
if (!visited[neighbor.id]) {
stack.push(neighbor);
visited[neighbor.id] = true;
}
}
}
}
}
class Node {
int id;
List<Node> neighbors;
}
```
相关推荐
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)