图的表示

📌 核心概念

图（Graph）是由顶点（Vertex）和边（Edge）组成的数据结构，用于表示对象之间的关系。

图的分类：

• 有向图/无向图：边是否有方向
• 有权图/无权图：边是否有权重
• 连通图/非连通图：任意两点是否可达
• 有环图/无环图（DAG）：是否存在环

💻 图的表示方法

🎯 方法对比与选择

复杂度对比

操作	邻接矩阵	邻接表	边集数组
空间复杂度	O(V²)	O(V+E)	O(E)
添加边	O(1)	O(1)	O(1)
删除边	O(1)	O(degree)	O(E)
查询边	O(1)	O(degree)	O(E)
遍历邻居	O(V)	O(degree)	O(E)
遍历所有边	O(V²)	O(V+E)	O(E)

💡 实际应用示例

Go 代码

// 邻接表表示
type Graph struct {
    n        int
    directed bool
    adj      map[int][]int
}
 
func NewGraph(n int, directed bool) *Graph {
    return &Graph{
        n:        n,
        directed: directed,
        adj:      make(map[int][]int),
    }
}
 
func (g *Graph) AddEdge(u, v int) {
    g.adj[u] = append(g.adj[u], v)
    if !g.directed {
        g.adj[v] = append(g.adj[v], u)
    }
}
 
func (g *Graph) GetNeighbors(u int) []int {
    return g.adj[u]
}
 
// 从边列表构建图
func buildGraph(n int, edges [][]int) map[int][]int {
    graph := make(map[int][]int)
 
    for _, edge := range edges {
        u, v := edge[0], edge[1]
        graph[u] = append(graph[u], v)
        graph[v] = append(graph[v], u)
    }
 
    return graph
}
 
// 有权图
type WeightedGraph struct {
    n   int
    adj map[int][]Edge
}
 
type Edge struct {
    to     int
    weight int
}
 
func NewWeightedGraph(n int) *WeightedGraph {
    return &WeightedGraph{
        n:   n,
        adj: make(map[int][]Edge),
    }
}
 
func (g *WeightedGraph) AddEdge(u, v, weight int) {
    g.adj[u] = append(g.adj[u], Edge{v, weight})
    g.adj[v] = append(g.adj[v], Edge{u, weight})
}

🎯 经典题目

题目	LeetCode	关键点
克隆图	133	图的复制
课程表	207	有向图表示
网络延迟时间	743	有权图
冗余连接	684	无向图找环
冗余连接II	685	有向图找环

---

返回：图算法