当前位置：首页 > Java

java图如何判断连通

2026-03-18 19:23:44Java

判断图的连通性

在Java中判断图是否连通，可以通过深度优先搜索（DFS）或广度优先搜索（BFS）实现。连通图是指任意两个顶点之间都存在路径的无向图。以下是具体实现方法：

使用深度优先搜索（DFS）

初始化访问数组 创建一个布尔数组visited，用于标记顶点是否被访问过，初始时所有顶点均未访问。
从任意顶点开始DFS 选择一个顶点作为起点，执行DFS遍历，标记所有访问过的顶点。
检查所有顶点是否被访问 遍历结束后，检查visited数组是否全部为true。若存在未被访问的顶点，则图不连通。

import java.util.*;

public class Graph {
    private int V; // 顶点数
    private LinkedList<Integer>[] adj; // 邻接表

    Graph(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);
        adj[w].add(v); // 无向图需双向添加
    }

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

    boolean isConnected() {
        boolean[] visited = new boolean[V];
        DFSUtil(0, visited); // 从顶点0开始DFS
        for (boolean b : visited)
            if (!b) return false;
        return true;
    }

    public static void main(String args[]) {
        Graph g = new Graph(4);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 3);
        System.out.println("图是否连通: " + g.isConnected());
    }
}

使用广度优先搜索（BFS）

初始化访问数组和队列 创建visited数组和一个队列，用于BFS遍历。
从起点开始BFS 将起点加入队列，标记为已访问，依次处理队列中的顶点，直到队列为空。
验证连通性 检查visited数组是否全部为true。

boolean isConnectedBFS() {
    boolean[] visited = new boolean[V];
    Queue<Integer> queue = new LinkedList<>();
    queue.add(0);
    visited[0] = true;

    while (!queue.isEmpty()) {
        int v = queue.poll();
        for (int n : adj[v]) {
            if (!visited[n]) {
                visited[n] = true;
                queue.add(n);
            }
        }
    }

    for (boolean b : visited)
        if (!b) return false;
    return true;
}