java深度优先遍历dfs
时间: 2023-11-12 17:56:44 浏览: 69
Java中深度优先遍历(DFS)可以通过递归实现,以下是一个简单的示例代码:
```java
public void dfs(Node node) {
if (node == null) {
return;
}
System.out.print(node.val + " ");
node.visited = true;
for (Node neighbor : node.neighbors) {
if (!neighbor.visited) {
dfs(neighbor);
}
}
}
```
其中,`Node`表示图中的节点,`neighbors`表示与该节点相邻的节点列表,`visited`表示该节点是否已被访问过。
相关问题
java深度优先遍历
Java中的深度优先遍历(Depth-First Search,简称DFS)是一种用于图或树的遍历算法。下面是一个使用递归实现深度优先遍历的示例代码:
```java
import java.util.ArrayList;
import java.util.List;
class Graph {
private int vertices;
private List<List<Integer>> adjList;
public Graph(int vertices) {
this.vertices = vertices;
adjList = new ArrayList<>(vertices);
for (int i = 0; i < vertices; i++) {
adjList.add(new ArrayList<>());
}
}
public void addEdge(int source, int destination) {
adjList.get(source).add(destination); }
private void dfsUtil(int v, boolean[] visited) {
visited[v] = true;
System.out.print(v + " ");
for (int neighbor : adjList.get(v)) {
if (!visited[neighbor]) {
dfsUtil(neighbor, visited);
}
}
}
public void DFS(int startVertex) {
boolean[] visited = new boolean[vertices];
dfsUtil(startVertex, visited);
}
}
public class Main {
public static void main(String[] args) {
Graph graph = new Graph(5);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
System.out.println("Depth-First Traversal (starting from vertex 0):");
graph.DFS(0);
}
}
```
在上述代码中,我们首先定义了一个Graph类来表示图。构造函数中初始化了邻接表和顶点数。addEdge方法用于添加边。
在dfsUtil方法中,我们使用了递归来进行深度优先遍历。我们首先将当前顶点标记为已访问,并打印该顶点。然后递归遍历该顶点的所有未访问过的邻居。
最后,在main方法中创建一个Graph对象,并添加边。然后调用DFS方法来开始深度优先遍历。
输出结果为:0 1 3 4 2,表示从顶点0开始的深度优先遍历路径。
希望这个示例能够帮助你理解Java中的深度优先遍历。如有疑问,请随时提问。
dfs深度优先遍历 java
深度优先搜索(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遍历。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.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)