使用 DFS 检查无向图是否连通的 Java 程序
简介
此 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 算法。
相关文章
有用资源
java 参考教程 - 该教程包含有关 java 的更多信息:https://www.cainiaomax.com/java/

