Java 使用DFS检查无向图是否连通

介绍

这个Java程序使用DFS检查无向图是否连通。它从用户那里以图中顶点和边的数量的形式输入图的信息，以及边本身。它创建一个邻接表来存储图的边，然后使用DFS遍历图并检查是否所有顶点都被访问。

如果所有顶点都被访问，则图是连通的。该程序的时间复杂度为O(V+E)，其中V是图中顶点的数量，E是图中边的数量，空间复杂度为O(V+E)。

定义

无向连通图是指所有顶点通过边连接在一起的图。在这样的图中，任意两个顶点之间都存在一条路径。如果我们从任意一个顶点出发，通过边遍历，可以到达图中的所有其他顶点。这个概念在图论中很重要，并且有许多应用，包括网络分析和地理地图。确定无向图的连通性是图论中的一个基本问题，存在多种算法可以解决。其中一种流行的算法是DFS，它可以用来确定无向图是否连通。

方法

• 定义一个函数dfsTraversal，在给定的图中从给定的顶点开始执行DFS遍历。该函数接受三个参数-
• 图 – 图的邻接表
• 顶点 – 应从哪个顶点开始进行DFS遍历
• visited – 一个包含布尔值的数组，指示某个顶点是否被访问过

dfsTraversal函数标记给定的顶点为已访问，并递归地访问其所有未访问的邻居。

• 定义一个函数isConnected，检查给定的图是否连通。该函数接受两个参数-
• 图 – 图的邻接表
• 顶点 – 图中的顶点数量

isConnected函数初始化一个名为visited的布尔值数组，用于跟踪访问过的顶点。然后，它使用dfsTraversal函数从图的第一个顶点开始执行DFS遍历。最后，它检查是否所有顶点都被访问过。如果所有顶点都被访问，则图是连通的，函数返回true。否则，返回false。

• 在主函数中-
• 读取图中的顶点和边的数量。
• 初始化邻接表图。
• 读取图的边并将其添加到邻接表中。
• 调用isConnected函数检查图是否连通，并根据结果打印结果。

这种方法背后的关键思想是使用深度优先搜索（DFS）访问图中的所有顶点并将它们标记为已访问。如果所有顶点都被访问过，那么图是连通的。如果没有，那么必定有一些顶点与图的其余部分不连接，这意味着图是不连通的。

示例1

下面是一个使用深度优先搜索（DFS）检查无向图是否连通的Java程序：

import java.util.*;

public class ConnectedGraphDFS {

   // function to perform DFS traversal on the graph
   private static void dfsTraversal(ArrayList<Integer>[] graph, int vertex, boolean[] visited) {
      visited[vertex] = true;

      // visit all the neighbors of the vertex
      for(int neighbor : graph[vertex]) {
         if(!visited[neighbor]) {
            dfsTraversal(graph, neighbor, visited);
         }
      }
   }

   // function to check whether the given graph is connected or not
   public static boolean isConnected(ArrayList<Integer>[] graph, int vertices) {
      boolean[] visited = new boolean[vertices];

      // perform DFS traversal from the first vertex
      dfsTraversal(graph, 0, visited);

      // check if all the vertices are visited or not
      for(int i = 0; i < vertices; i++) {
         if(!visited[i]) {
            return false;
         }
      }

      return true;
   }

   // main function to test the program
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);

      // read the number of vertices in the graph
      System.out.print("Enter the number of vertices in the graph: ");
      int vertices = sc.nextInt();

      // read the number of edges in the graph
      System.out.print("Enter the number of edges in the graph: ");
      int edges = sc.nextInt();

      // initialize the adjacency list
      ArrayList<Integer>[] graph = new ArrayList[vertices];

      for(int i = 0; i < vertices; i++) {
         graph[i] = new ArrayList<Integer>();
      }

      System.out.println("Enter the edges of the graph:");
      // read the edges of the graph
      for(int i = 0; i < edges; i++) {
         int u = sc.nextInt();
         int v = sc.nextInt();

         // add edge between u and v
         graph[u].add(v);
         graph[v].add(u);
      }

      // check whether the graph is connected or not
      boolean isConnected = isConnected(graph, vertices);

      if(isConnected) {
         System.out.println("The graph is connected.");
      }
      else {
         System.out.println("The graph is not connected.");
      }
   }
}

说明

在这个程序中，我们首先定义了一个名为dfsTraversal的函数，它从给定的顶点开始对给定的图进行深度优先搜索遍历。这个函数有三个参数。dfsTraversal函数将给定的顶点标记为已访问，并递归地访问所有未访问的邻居。接下来，我们定义了一个名为isConnected的函数，它检查给定的图是否连通。这个函数有两个参数。

isConnected函数初始化了一个名为visited的布尔值数组，用于跟踪已访问的顶点。然后，它使用dfsTraversal函数从图的第一个顶点开始进行深度优先搜索遍历。最后，它检查所有的顶点是否都被访问过。如果所有的顶点都被访问过，则图是连通的，函数返回true。否则，返回false。

输出

Enter the number of vertices in the graph: 6
Enter the number of edges in the graph: 5
Enter the edges of the graph:
0 1
1 2
2 3
4 5
5 4

Graph is not connected

示例2

这是另一个使用深度优先搜索（DFS）来检查无向图是否连通的Java程序 –

import java.util.ArrayList;
import java.util.Scanner;

public class GraphConnectivityDFS {
   private int V;
   private ArrayList<ArrayList<Integer>> adj;

   GraphConnectivityDFS(int v) {
      V = v;
      adj = new ArrayList<>(V);
      for (int i = 0; i < V; ++i) {
         adj.add(new ArrayList<>());
      }
   }

   void addEdge(int v, int w) {
      adj.get(v).add(w);
      adj.get(w).add(v);
   }

   void dfsTraversal(int v, boolean[] visited) {
      visited[v] = true;
      for (int n : adj.get(v)) {
         if (!visited[n]) {
            dfsTraversal(n, visited);
         }
      }
   }

   boolean isConnected() {
      boolean[] visited = new boolean[V];
      dfsTraversal(0, visited);
      for (int i = 0; i < V; ++i) {
         if (!visited[i]) {
            return false;
         }
      }
      return true;
   }

   public static void main(String[] args) {
      Scanner scanner = new Scanner(System.in);

      System.out.print("Enter the number of vertices in the graph: ");
      int V = scanner.nextInt();

      System.out.print("Enter the number of edges in the graph: ");
      int E = scanner.nextInt();

      GraphConnectivityDFS graph = new GraphConnectivityDFS(V);

      System.out.println("Enter the edges of the graph:");
      for (int i = 0; i < E; i++) {
         int v = scanner.nextInt();
         int w = scanner.nextInt();
         graph.addEdge(v, w);
      }

      boolean connected = graph.isConnected();
      if (connected) {
         System.out.println("Graph is connected");
      } else {
         System.out.println("Graph is not connected");
      }
   }
}

输出

Enter the number of vertices in the graph: 2
Enter the number of edges in the graph: 2
Enter the edges of the graph:
0 1
1 0
Graph is connected

结论

• 无向连通图是一种图，其中所有顶点互相连接，并且任意两个顶点之间存在路径。

• 确定无向图的连通性是图论中的一个重要问题，存在各种算法来解决它，例如上述Java程序中使用的DFS算法。