用java写java的深度优先算法
时间: 2023-06-18 13:02:49 浏览: 57
以下是一个使用 Java 编写的深度优先搜索算法的示例代码,假设我们要搜索的是一个无向图:
```java
import java.util.*;
public class DFS {
private int V; // 图的顶点数
private LinkedList<Integer>[] adj; // 图的邻接表表示
public DFS(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i) {
adj[i] = new LinkedList();
}
}
// 添加边
public void addEdge(int v, int w) {
adj[v].add(w);
}
// DFS搜索
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);
}
}
// 对DFS进行封装
public void DFS(int v) {
boolean[] visited = new boolean[V];
DFS(v, visited);
}
public static void main(String[] args) {
DFS g = new DFS(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
```
此代码使用邻接表表示图,并通过 `addEdge` 方法添加图的边。`DFS` 方法中,`visited` 数组用于记录已访问过的节点,`listIterator` 方法用于获取该节点的邻接节点,如果邻接节点没有被访问过,则递归调用 `DFS` 方法进行搜索。在 `main` 方法中,我们创建了一个图并从节点 `2` 开始进行深度优先搜索。