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

javaobject oriented programmingprogramming更新于 2024/3/15 18:20:17

简介

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

如果所有顶点都被访问过,则图是连通的。此程序的时间复杂度为 O(V+E),其中 V 是图中的顶点数,E 是边数,由于邻接表,空间复杂度为 O(V+E)。

定义

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

方法

  • 定义一个函数 dfsTraversal,从给定的顶点开始,对给定的图执行 DFS 遍历。此函数有三个参数 -

  • graph - 图的邻接列表

  • vertex - DFS 遍历应从其开始的顶点

  • visited - 一个布尔值数组,表示顶点是否已被访问

dfsTraversal 函数将给定的顶点标记为已访问,然后递归访问其所有未访问的邻居。

  • 定义一个函数 isConnected,检查给定的图是否连通。此函数接受两个参数 -

  • graph - 图的邻接列表

  • vertices - 图中的顶点数

isConnected 函数初始化一个名为 accessed 的布尔值数组,以跟踪已访问的顶点。然后,它使用 dfsTraversal 函数从图的第一个顶点执行 DFS 遍历。最后,它检查是否已访问所有顶点。如果已访问所有顶点,则图已连接,函数返回 true。否则,返回 false。

  • 在主函数中 -

  • 读取图中的顶点和边的数量。

  • 初始化邻接列表图。

  • 读取图的边并将其添加到邻接列表中。

  • 调用 isConnected 函数检查图是否连通,并相应地打印结果。

这种方法背后的关键思想是使用 DFS 访问图中的所有顶点并将它们标记为已访问。如果所有顶点都已被访问,则图是连通的。如果不是,那么一定有一些顶点没有连接到图的其余部分,这意味着图是不连通的。

示例 1

这是一个 Java 程序,使用深度优先搜索 (DFS) 检查无向图是否连通 −

import java.util.*;

public class ConnectedGraphDFS {

   // 对图执行 DFS 遍历的函数
   private static void dfsTraversal(ArrayList<Integer>[] graph, int vertex, boolean[] visited) {
      visited[vertex] = true;

      // 访问该顶点的所有邻居
      for(int neighbor : graph[vertex]) {
         if(!visited[neighbor]) {
            dfsTraversal(graph, neighbor, visited);
         }
      }
   }

    // 函数用于检查给定的图是否连通
    public static boolean isConnected(ArrayList<Integer>[] graph, int vertices) {
        boolean[] accessed = new boolean[vertices];
        
        // 从第一个顶点执行 DFS 遍历
        dfsTraversal(graph, 0, accessed);
        
        // 检查所有顶点是否都被访问过
        for(int i = 0; i < vertices; i++) {
            if(!visited[i]) {
                return false;
            }
        }
        
        return true;
    }

    // 主函数用于测试程序
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取图中的顶点数
        System.out.print("输入图中的顶点数:");
        int vertices = sc.nextInt();
        
        // 读取图中的边数
        System.out.print("输入图中的边数:");
        int edge = sc.nextInt();
        
        // 初始化邻接表
        ArrayList<Integer>[] graph = new ArrayList[vertices];
        
        for(int i = 0; i < vertices; i++) {
        	graph[i] = new ArrayList<Integer>();
        }
        
        System.out.println("输入图中的边:");
        // 读取图的边
        for(int i = 0; i < edge; i++) {
        int u = sc.nextInt();
        int v = sc.nextInt();
        
        // 在 u 和 v 之间添加边
        graph[u].add(v);
        graph[v].add(u);
    	}

        // 检查图是否连通
        boolean isConnected = isConnected(graph, vertices);
        
        if(isConnected) {
       	 	System.out.println("图已连通。");
        }
        else {
        	System.out.println("图未连通。");
        }
   }
}

解释

在此程序中,我们首先定义一个函数 dfsTraversal,该函数从给定顶点开始对给定图执行 DFS 遍历。此函数有三个参数。dfsTraversal 函数将给定顶点标记为已访问,然后递归访问其所有未访问的邻居。接下来,我们定义函数 isConnected,它检查给定图是否连通。此函数有两个参数。

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

输出

输入图中的顶点数:6
输入图中的边数:5
输入图中的边:
0 1
1 2
2 3
4 5
5 4

图未连通

示例 2

这是另一个 Java 程序,使用深度优先搜索 (DFS) 检查无向图是否连通 −

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");
      }
   }
}

输出

输入图中的顶点数:2
输入图中的边数:2
输入图的边数:
0 1
1 0
图是连通的

结论

  • 无向连通图是所有顶点都相互连通,且任意两个顶点之间都有路径的图。

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


相关文章


有用资源