Go语言图的连通性判断（从零开始掌握图算法与无向图连通判断）

什么是图的连通性？

在一个无向图中，如果任意两个顶点之间都存在一条路径（可以经过其他顶点），那么这个图就是连通图。否则，图中会存在多个连通分量（Connected Components）。

例如，上图展示了一个包含4个顶点的图，其中顶点A、B、C彼此相连，构成一个连通分量；而顶点D是孤立的，单独构成另一个连通分量。因此整个图不是连通的。

如何判断图是否连通？

常用的方法是使用 深度优先搜索（DFS） 或 广度优先搜索（BFS） 从任意一个顶点出发，遍历所有可达的顶点。如果遍历结束后访问过的顶点数量等于图中总顶点数，则图是连通的。

Go语言实现步骤

我们将用邻接表（Adjacency List）表示图，并通过 DFS 判断连通性。

1. 定义图结构

type Graph struct {    vertices int    adjList  map[int][]int}func NewGraph(vertices int) *Graph {    g := &Graph{        vertices: vertices,        adjList:  make(map[int][]int),    }    for i := 0; i < vertices; i++ {        g.adjList[i] = []int{}    }    return g}

2. 添加边（无向图）

func (g *Graph) AddEdge(u, v int) {    g.adjList[u] = append(g.adjList[u], v)    g.adjList[v] = append(g.adjList[v], u) // 无向图：双向添加}

3. 深度优先搜索（DFS）

func (g *Graph) dfs(start int, visited map[int]bool) {    visited[start] = true    for _, neighbor := range g.adjList[start] {        if !visited[neighbor] {            g.dfs(neighbor, visited)        }    }}

4. 判断连通性

func (g *Graph) IsConnected() bool {    if g.vertices == 0 {        return true // 空图视为连通    }    visited := make(map[int]bool)    // 从顶点0开始DFS    g.dfs(0, visited)    // 检查是否所有顶点都被访问    for i := 0; i < g.vertices; i++ {        if !visited[i] {            return false        }    }    return true}

5. 完整示例与测试

package mainimport "fmt"// （此处省略上面定义的 Graph 结构和方法）func main() {    // 创建一个包含4个顶点的图    g := NewGraph(4)    // 添加边：0-1, 1-2    g.AddEdge(0, 1)    g.AddEdge(1, 2)    // 顶点3是孤立的    if g.IsConnected() {        fmt.Println("图是连通的")    } else {        fmt.Println("图不是连通的")    }    // 再添加一条边连接3    g.AddEdge(2, 3)    if g.IsConnected() {        fmt.Println("现在图是连通的")    }}

运行结果：

图不是连通的现在图是连通的

总结

通过本文，我们学习了如何在 Go 语言中使用邻接表和 DFS 算法来判断无向图的连通性。这是图算法中最基础但非常实用的技术之一。

掌握 Go语言图的连通性 判断方法，不仅有助于理解 图算法 的核心思想，也为后续学习更复杂的 Go数据结构 打下坚实基础。无论你是初学者还是有一定经验的开发者，动手实现一遍上述代码，都能加深对 无向图连通判断 的理解。

希望这篇教程对你有帮助！欢迎继续探索图论的更多有趣问题，如最短路径、最小生成树等。