有向图遍历java实现代码
时间: 2023-10-14 18:04:28 浏览: 50
以下是深度优先搜索和广度优先搜索在 Java 中的实现代码:
深度优先搜索:
```java
import java.util.*;
public class Graph {
private int V; // 节点个数
private LinkedList<Integer>[] adj; // 邻接表
public Graph(int v) {
V = v;
adj = new LinkedList[V];
for (int i = 0; i < V; ++i) {
adj[i] = new LinkedList<Integer>();
}
}
public void addEdge(int v, int w) {
adj[v].add(w);
}
public void DFS(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]) {
DFS(n, visited);
}
}
}
public void DFS(int v) {
boolean[] visited = new boolean[V];
DFS(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);
g.DFS(2);
}
}
```
广度优先搜索:
```java
import java.util.*;
public class Graph {
private int V; // 节点个数
private LinkedList<Integer>[] adj; // 邻接表
public Graph(int v) {
V = v;
adj = new LinkedList[V];
for (int i = 0; i < V; ++i) {
adj[i] = new LinkedList<Integer>();
}
}
public void addEdge(int v, int w) {
adj[v].add(w);
}
public void BFS(int v) {
boolean[] visited = new boolean[V];
LinkedList<Integer> queue = new LinkedList<Integer>();
visited[v] = true;
queue.add(v);
while (queue.size() != 0) {
v = queue.poll();
System.out.print(v + " ");
Iterator<Integer> i = adj[v].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n]) {
visited[n] = true;
queue.add(n);
}
}
}
}
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);
g.BFS(2);
}
}
```
在上面的代码中,我们使用邻接表来表示有向图,其中 `V` 表示节点个数,`adj` 是一个数组,每个元素 `adj[i]` 是一个链表,表示从节点 `i` 出发可以到达的节点。在深度优先搜索中,我们使用递归来实现,同时需要记录哪些节点已经被访问过,从而避免重复访问。在广度优先搜索中,我们使用队列来实现,同样需要记录哪些节点已经被访问过。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)