Java 邻接表G中顶点v出发深度优先遍历
时间: 2023-07-24 09:40:11 浏览: 34
以下是 Java 邻接表中顶点v出发的深度优先遍历的代码实现:
```java
public void DFS(int v, boolean[] visited) {
// 标记当前顶点为已访问
visited[v] = true;
System.out.print(v + " ");
// 遍历邻接表中与当前顶点相邻的未访问顶点
for (int i = 0; i < adjList.get(v).size(); i++) {
int u = adjList.get(v).get(i);
if (!visited[u]) {
DFS(u, visited);
}
}
}
```
其中,`v`表示起始顶点,`visited`数组表示每个顶点的访问状态(已访问为 true,未访问为 false)。首先将起始顶点 `v` 标记为已访问,并输出其值。然后遍历邻接表中与 `v` 相邻的所有未访问顶点,对每个未访问顶点递归调用 `DFS` 方法,直到所有顶点都被访问过为止。
相关问题
Java 邻接表G中顶点v出发深度优先遍历并输出
以下是Java代码实现邻接表G中顶点v出发深度优先遍历并输出:
```
import java.util.LinkedList;
public 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);
}
// 深度优先遍历
void DFSUtil(int v,boolean visited[]) {
visited[v] = true;
System.out.print(v+" ");
// 遍历邻接表中的所有节点
for (int i:adj[v]) {
if (!visited[i])
DFSUtil(i, visited);
}
}
// 对图进行深度优先遍历
void DFS(int v) {
boolean visited[] = new boolean[V];
DFSUtil(v, visited);
}
// 测试
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开始的深度优先遍历:");
g.DFS(2);
}
}
```
输出结果为:
```
从顶点2开始的深度优先遍历:
2 0 1 3
```
图 邻接表的深度优先遍历java
以下是Java中邻接表的深度优先遍历的实现方法:
假设我们有一个图,其中顶点从0到V-1编号,我们可以使用邻接表来表示它。我们可以使用一个布尔数组visited[]来跟踪哪些顶点已经被访问过。我们从给定的源顶点开始遍历图,并在遍历过程中将visited[]中的相应条目标记为true。对于每个未被访问的相邻顶点,我们递归地调用深度优先遍历函数。
```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);
}
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);
}
}
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("Following is Depth First Traversal " + "(starting from vertex 2)");
g.DFS(2);
}
}
```