图算法实战：从最短路径到网络流的深度解析与工程应用

图是计算机科学中最强大的数据结构之一。从地图导航的路由规划，到社交网络的好友推荐，再到编译器的依赖分析，图算法无处不在。本文将系统梳理核心图算法，深入探讨它们在真实工程中的实现与优化策略。

一、图的基本概念与存储结构

图（Graph）由顶点集 V 和边集 E 组成，记作 G=(V, E)。根据边是否有向、是否有权、是否包含环，图可以分为多种类型：有向图/无向图、加权图/无权图、有环图/无环图（DAG）。

1.1 邻接矩阵

邻接矩阵用一个 |V|×|V| 的二维数组表示图。若存在边 (u, v)，则 matrix[u][v] = 1（无权图）或 weight（加权图）。

type AdjMatrix struct {
    vertices int
    edges    [][]float64
}

func NewAdjMatrix(n int) *AdjMatrix {
    edges := make([][]float64, n)
    for i := range edges {
        edges[i] = make([]float64, n)
        for j := range edges[i] {
            if i == j {
                edges[i][j] = 0
            } else {
                edges[i][j] = math.Inf(1)
            }
        }
    }
    return &AdjMatrix{vertices: n, edges: edges}
}

邻接矩阵的优势是查询 O(1)，缺点是空间 O(V²)，不适合稀疏图。

1.2 邻接表

邻接表为每个顶点维护一个邻接链表，空间 O(V+E)，是实际工程中最常用的表示法。

type Edge struct {
    To     int
    Weight float64
}

type AdjList struct {
    vertices int
    edges    [][]Edge
}

func NewAdjList(n int) *AdjList {
    return &AdjList{
        vertices: n,
        edges:    make([][]Edge, n),
    }
}

二、图的遍历：DFS 与 BFS

图的遍历是后续所有算法的基础。深度优先搜索（DFS）沿着一条路径深入到底再回溯，广度优先搜索（BFS）则逐层扩展。

func DFS(graph *AdjList, start int) []int {
    visited := make([]bool, graph.vertices)
    stack := []int{start}
    order := []int{}
    for len(stack) > 0 {
        u := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if visited[u] { continue }
        visited[u] = true
        order = append(order, u)
        for _, e := range graph.edges[u] {
            if !visited[e.To] {
                stack = append(stack, e.To)
            }
        }
    }
    return order
}

三、最短路径算法全景

3.1 Dijkstra 算法

Dijkstra 采用贪心策略：每次从未确定最短路径的顶点中选择距离最小的一个，然后对其邻居执行松弛操作。时间复杂度 O((V+E) log V)。

func Dijkstra(graph *AdjList, src int) ([]float64, []int) {
    n := graph.vertices
    dist := make([]float64, n)
    prev := make([]int, n)
    visited := make([]bool, n)
    for i := 0; i < n; i++ {
        dist[i] = math.Inf(1)
        prev[i] = -1
    }
    dist[src] = 0
    pq := &PriorityQueue{}
    heap.Push(pq, &Item{vertex: src, dist: 0})
    for pq.Len() > 0 {
        item := heap.Pop(pq).(*Item)
        u := item.vertex
        if visited[u] { continue }
        visited[u] = true
        for _, e := range graph.edges[u] {
            v := e.To
            if !visited[v] && dist[u]+e.Weight < dist[v] {
                dist[v] = dist[u] + e.Weight
                prev[v] = u
                heap.Push(pq, &Item{vertex: v, dist: dist[v]})
            }
        }
    }
    return dist, prev
}

3.2 Bellman-Ford 与负环检测

当图中存在负权边时，Dijkstra 失效。Bellman-Ford 通过 V-1 轮全局松弛，保证找到最短路径。

func BellmanFord(edges []Edge, n, src int) ([]float64, bool) {
    dist := make([]float64, n)
    for i := range dist { dist[i] = math.Inf(1) }
    dist[src] = 0
    for i := 0; i < n-1; i++ {
        updated := false
        for _, e := range edges {
            if dist[e.From]+e.Weight < dist[e.To] {
                dist[e.To] = dist[e.From] + e.Weight
                updated = true
            }
        }
        if !updated { break }
    }
    for _, e := range edges {
        if dist[e.From]+e.Weight < dist[e.To] {
            return dist, false // 存在负环
        }
    }
    return dist, true
}

3.3 Floyd-Warshall：全源最短路径

基于动态规划，时间复杂度 O(V³)，适合稠密图或需要所有顶点对距离的场景。

func FloydWarshall(dist [][]float64) [][]float64 {
    n := len(dist)
    dp := make([][]float64, n)
    for i := range dp {
        dp[i] = make([]float64, n)
        copy(dp[i], dist[i])
    }
    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if dp[i][k]+dp[k][j] < dp[i][j] {
                    dp[i][j] = dp[i][k] + dp[k][j]
                }
            }
        }
    }
    return dp
}

四、最小生成树

4.1 Kruskal 算法

按边权排序，用并查集维护连通分量，每次加入不形成环的最小边，时间 O(E log E)。

func Kruskal(n int, edges []Edge) ([]Edge, float64) {
    sort.Slice(edges, func(i, j int) bool {
        return edges[i].Weight < edges[j].Weight
    })
    uf := NewUnionFind(n)
    mst := []Edge{}
    totalWeight := 0.0
    for _, e := range edges {
        if uf.Union(e.From, e.To) {
            mst = append(mst, e)
            totalWeight += e.Weight
            if len(mst) == n-1 { break }
        }
    }
    return mst, totalWeight
}

五、网络流：Dinic 算法

网络流问题将图建模为管道系统，目标是求从源点到汇点的最大流量。Dinic 引入分层图和阻塞流概念，时间 O(V²E)。

type Dinic struct {
    n     int
    level []int
    ptr   []int
    graph [][]DinicEdge
}

type DinicEdge struct {
    to  int
    rev int
    cap float64
}

func (d *Dinic) MaxFlow(s, t int) float64 {
    flow := 0.0
    for d.bfs(s, t) {
        d.ptr = make([]int, d.n)
        for {
            pushed := d.dfs(s, t, math.Inf(1))
            if pushed == 0 { break }
            flow += pushed
        }
    }
    return flow
}

在分布式数据库副本同步中，网络流模型可用于带宽分配优化和故障恢复路径规划。

六、强连通分量：Tarjan 算法

通过一次 DFS 找出所有强连通分量（SCC），缩点后得到 DAG，广泛应用于编译优化和数据库循环依赖检测。

func TarjanSCC(graph *AdjList) [][]int {
    n := graph.vertices
    index := 0
    stack := []int{}
    onStack := make([]bool, n)
    indices := make([]int, n)
    lowlink := make([]int, n)
    for i := range indices { indices[i] = -1 }
    sccs := [][]int{}
    var strongconnect func(v int)
    strongconnect = func(v int) {
        indices[v], lowlink[v] = index, index
        index++
        stack = append(stack, v)
        onStack[v] = true
        for _, e := range graph.edges[v] {
            w := e.To
            if indices[w] == -1 {
                strongconnect(w)
                if lowlink[w] < lowlink[v] { lowlink[v] = lowlink[w] }
            } else if onStack[w] {
                if indices[w] < lowlink[v] { lowlink[v] = indices[w] }
            }
        }
        if lowlink[v] == indices[v] {
            scc := []int{}
            for {
                w := stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                onStack[w] = false
                scc = append(scc, w)
                if w == v { break }
            }
            sccs = append(sccs, scc)
        }
    }
    for v := 0; v < n; v++ {
        if indices[v] == -1 { strongconnect(v) }
    }
    return sccs
}

七、算法选型决策树

八、总结与前沿方向

图算法历经数十年发展，已形成完善的理论和工程体系。掌握这些核心算法不仅是面试的需要，更是解决实际工程问题的有力武器。从编译器的依赖分析，到数据库的查询优化，再到分布式系统的拓扑管理，图算法无处不在。随着图神经网络（GNN）的兴起，传统图算法正与深度学习融合，在知识图谱推理、分子结构预测等领域展现出新的生命力。