Java 邻接表G中顶点v出发深度优先遍历并输出
时间: 2024-04-02 16:33:09 浏览: 16
好的,以下是 Java 邻接表 G 中顶点 v 出发的深度优先遍历代码:
```java
import java.util.LinkedList;
public class Graph {
private int V; // 顶点个数
private LinkedList<Integer>[] adj; // 邻接表
@SuppressWarnings("unchecked")
public Graph(int V) {
this.V = V;
adj = new LinkedList[V];
for (int i = 0; i < V; i++) {
adj[i] = new LinkedList<>();
}
}
// 添加一条边
public void addEdge(int u, int v) {
adj[u].add(v);
}
// 深度优先遍历
public void DFS(int v) {
boolean[] visited = new boolean[V];
DFSUtil(v, visited);
}
private void DFSUtil(int v, boolean[] visited) {
visited[v] = true;
System.out.print(v + " ");
for (int i : adj[v]) {
if (!visited[i]) {
DFSUtil(i, visited);
}
}
}
}
```
在上面的代码中,我们定义了一个 `Graph` 类,其中:
- `V` 表示图中顶点的个数;
- `adj` 是一个邻接表,用于存储图中每个顶点的邻居;
- `addEdge` 方法用于向邻接表中添加一条边;
- `DFS` 方法是对外暴露的方法,用于从顶点 `v` 开始进行深度优先遍历;
- `DFSUtil` 方法是实际执行深度优先遍历的方法,其中 `visited` 数组用于标记每个顶点是否被访问过。
你可以使用以下代码进行测试:
```java
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("深度优先遍历结果:");
g.DFS(2);
}
}
```
输出结果为:
```
深度优先遍历结果:
2 0 1 3
```