深度优先算法java
时间: 2023-02-26 12:48:40 浏览: 53
深度优先搜索(Depth-First Search, DFS)是一种用于遍历或搜索树或图的算法。它的基本思想是:在树或图中从某个起始顶点出发,先沿着树的深度遍历节点,直到找到一个没有子节点的叶节点,然后回溯到叶节点的父节点,继续搜索下一个子节点,直到遍历完整棵树。
下面是一个简单的 Java 代码实现 DFS 算法的例子:
```
// 定义一个二维数组表示图
int[][] graph = {
{0, 1, 1, 0, 0, 0},
{0, 0, 0, 1, 0, 0},
{0, 1, 0, 0, 1, 1},
{0, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0}
};
// 定义一个一维数组表示节点是否被访问过
boolean[] visited = new boolean[6];
// 定义DFS方法
public void DFS(int start) {
// 将起始节点标记为已访问
visited[start] = true;
System.out.print(start + " ");
// 遍历起始节点的所有子节点
for (int i = 0; i < 6; i++) {
// 如果子节点没有被访问过并且存在边相连,则递归调用DFS方法
if (!visited[i] && graph[start][i] == 1) {
DFS(i);
}
}
}
```
在这个例子中,图是一个二维数组,0 表示两个节点之间没有边