Java代码实现DFS算法 |21xrx.com

Java代码实现DFS算法

2023-08-04 01:09:52 深夜i -- --

Java DFS算法实现代码

深度优先搜索（DFS）是图遍历中常用的一种算法，它通过深入图的深处来搜索未被探索的节点。在DFS算法中，我们使用递归或栈来实现。

在Java中，我们可以使用以下代码实现DFS算法：


import java.util.*;
public class DFS {
  private int V; // 图的顶点个数
  private LinkedList<Integer> adj[]; // 邻接表表示的图
  // 构造函数
  DFS(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);
  }
  // 从给定节点开始进行DFS遍历
  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);
    }
  }
  // 对图进行DFS遍历
  void DFS(int v) {
    boolean visited[] = new boolean[V];
    DFSUtil(v, visited);
  }
  // 测试代码
  public static void main(String args[]) {
    DFS dfs = new DFS(4);
    dfs.addEdge(0, 1);
    dfs.addEdge(0, 2);
    dfs.addEdge(1, 2);
    dfs.addEdge(2, 0);
    dfs.addEdge(2, 3);
    dfs.addEdge(3, 3);
    System.out.println("从给定顶点2进行DFS遍历的结果：");
    dfs.DFS(2);
  }
}

上述代码中，我们首先定义了一个DFS类，其中包含了图的顶点个数和邻接表adj。构造函数用于初始化邻接表。addEdge方法用于添加边。DFSUtil方法是DFS算法的核心部分，其中通过递归的方式实现了DFS遍历。DFS方法用于启动DFS算法。最后，在main函数中，我们创建一个DFS对象，并对其进行测试。

执行上述代码，我们将会得到从给定顶点2进行DFS遍历的结果：2 0 1 3。

总结来说，通过以上的Java代码实现，我们可以很方便地使用DFS算法对有向图或无向图进行遍历，从而找到图中的所有节点。

上一篇: idea打包java可执行jar包

下一篇: OpenCV在计算机视觉中有什么用途?

评论区

()

相似文章