图论基础：连接的数学

图的表示：邻接表 vs 邻接矩阵

package main

import (
    "container/heap"
    "fmt"
    "math"
)

// 图的表示（邻接表，加权有向图）
type Graph struct {
    adj map[int][]Edge
}

type Edge struct{ to, weight int }

func NewGraph() *Graph {
    return &Graph{adj: map[int][]Edge{}}
}

func (g *Graph) AddEdge(from, to, weight int) {
    g.adj[from] = append(g.adj[from], Edge{to, weight})
}

// Dijkstra 最短路径：O((V+E) log V)
func (g *Graph) Dijkstra(src int) map[int]int {
    dist := map[int]int{}
    for v := range g.adj {
        dist[v] = math.MaxInt64
    }
    dist[src] = 0

    pq := &PQ{{0, src}}
    heap.Init(pq)

    for pq.Len() > 0 {
        item := heap.Pop(pq).(PQItem)
        u := item.node
        if item.dist > dist[u] {
            continue  // 过时的记录
        }
        for _, e := range g.adj[u] {
            if newDist := dist[u] + e.weight; newDist < dist[e.to] {
                dist[e.to] = newDist
                heap.Push(pq, PQItem{newDist, e.to})
            }
        }
    }
    return dist
}

type PQItem struct{ dist, node int }
type PQ []PQItem

func (pq PQ) Len() int            { return len(pq) }
func (pq PQ) Less(i, j int) bool  { return pq[i].dist < pq[j].dist }
func (pq PQ) Swap(i, j int)       { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PQ) Push(x interface{}) { *pq = append(*pq, x.(PQItem)) }
func (pq *PQ) Pop() interface{}   { old := *pq; n := len(old); x := old[n-1]; *pq = old[:n-1]; return x }

func main() {
    g := NewGraph()
    g.AddEdge(0, 1, 4); g.AddEdge(0, 2, 1)
    g.AddEdge(2, 1, 2); g.AddEdge(1, 3, 1); g.AddEdge(2, 3, 5)

    dist := g.Dijkstra(0)
    fmt.Println("从节点 0 出发的最短路径:", dist)
    // map[0:0 1:3 2:1 3:4]
}

拓扑排序：依赖解析的数学

package main

import "fmt"

// Kahn 算法拓扑排序（BFS 版）
// 应用：包管理依赖安装顺序、编译依赖、任务调度
func topoSort(n int, edges [][2]int) ([]int, bool) {
    inDegree := make([]int, n)
    adj := make([][]int, n)
    for _, e := range edges {
        adj[e[0]] = append(adj[e[0]], e[1])
        inDegree[e[1]]++
    }

    queue := []int{}
    for i, d := range inDegree {
        if d == 0 {
            queue = append(queue, i)
        }
    }

    order := []int{}
    for len(queue) > 0 {
        u := queue[0]
        queue = queue[1:]
        order = append(order, u)
        for _, v := range adj[u] {
            inDegree[v]--
            if inDegree[v] == 0 {
                queue = append(queue, v)
            }
        }
    }

    if len(order) != n {
        return nil, false  // 有环，无法拓扑排序
    }
    return order, true
}

func main() {
    // 包依赖：A→C，B→C，C→D（A、B 依赖 C，C 依赖 D）
    edges := [][2]int{{0, 2}, {1, 2}, {2, 3}}
    order, ok := topoSort(4, edges)
    fmt.Println(ok, order)  // true [0 1 2 3] 或 [1 0 2 3]

    // 有环图
    cyclic := [][2]int{{0, 1}, {1, 2}, {2, 0}}
    _, ok2 := topoSort(3, cyclic)
    fmt.Println("有环:", !ok2)  // 有环: true
}

并查集：连通分量的利器

package main

import "fmt"

// 并查集（路径压缩 + 按秩合并）
type UnionFind struct {
    parent, rank []int
}

func NewUF(n int) *UnionFind {
    parent := make([]int, n)
    for i := range parent { parent[i] = i }
    return &UnionFind{parent, make([]int, n)}
}

func (uf *UnionFind) Find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.Find(uf.parent[x])  // 路径压缩
    }
    return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) {
    rx, ry := uf.Find(x), uf.Find(y)
    if rx == ry { return }
    if uf.rank[rx] < uf.rank[ry] { rx, ry = ry, rx }
    uf.parent[ry] = rx
    if uf.rank[rx] == uf.rank[ry] { uf.rank[rx]++ }
}

func main() {
    uf := NewUF(6)
    uf.Union(0, 1); uf.Union(1, 2); uf.Union(3, 4)
    fmt.Println(uf.Find(0) == uf.Find(2))  // true（同一连通分量）
    fmt.Println(uf.Find(0) == uf.Find(3))  // false（不同分量）
}

图论是关系的数学——世界上所有的网络，都是图。

— 图论与应用