程序员数学04：图论 - 微服务依赖管理

本文是《程序员数学扫盲课》系列文章

← 上一篇：程序员数学03：集合论 – Redis与SQL | → 下一篇：程序员数学05：概率论 – 系统可用性

TL;DR

为什么微服务会出现循环依赖？为什么CI/CD流水线要按顺序执行？为什么地图导航能找到最短路径？答案都藏在图论里。这篇文章用Go代码带你搞懂图的基本概念，看完你会发现：图就是”带箭头的关系网”。

系列导航

《程序员数学扫盲课》系列：
1. 破冰篇：数学符号就是代码
2. 对数Log：数据库索引的魔法
3. 集合论：玩转Redis与SQL
4. 图论基础：微服务依赖管理（本篇）
5. 概率论：系统可用性计算
6. 统计学：P99延迟与监控报警
7. 线性代数入门：推荐系统的数学基础
8. 哈希与模运算：负载均衡算法
9. 信息论：数据压缩与编码
10. 组合数学：容量规划与性能预估

一、图论到底是什么？

先说重点：图就是”节点+边”的关系网络。

1.1 从微信好友关系说起

假设你有3个微信好友：

你 → 张三（你关注了张三）
你 → 李四（你关注了李四）
张三 → 李四（张三关注了李四）

这就是一个有向图（Directed Graph）：
– 节点（Vertex）：你、张三、李四
– 边（Edge）：箭头表示关注关系

如果是双向关注（互相关注），就是无向图（Undirected Graph）。

1.2 图的数学定义

看到这个公式别慌：

G = (V, E)

翻译成人话：
– V（Vertex）：节点集合，比如 {你, 张三, 李四}
– E（Edge）：边集合，比如 {(你→张三), (你→李四), (张三→李四)}

Go代码表示：

package main

import "fmt"

// 图的基本结构
type Graph struct {
    Vertices []string          // 节点列表
    Edges    map[string][]string // 邻接表：节点 -> 邻居列表
}

func NewGraph() *Graph {
    return &Graph{
        Vertices: []string{},
        Edges:    make(map[string][]string),
    }
}

// 添加节点
func (g *Graph) AddVertex(v string) {
    g.Vertices = append(g.Vertices, v)
    if g.Edges[v] == nil {
        g.Edges[v] = []string{}
    }
}

// 添加边（有向）
func (g *Graph) AddEdge(from, to string) {
    g.Edges[from] = append(g.Edges[from], to)
}

// 打印图
func (g *Graph) Print() {
    fmt.Println("图结构:")
    for _, v := range g.Vertices {
        neighbors := g.Edges[v]
        if len(neighbors) > 0 {
            fmt.Printf("  %s → %v\n", v, neighbors)
        } else {
            fmt.Printf("  %s → (无出边)\n", v)
        }
    }
}

func main() {
    g := NewGraph()

    // 添加节点
    g.AddVertex("你")
    g.AddVertex("张三")
    g.AddVertex("李四")

    // 添加边（关注关系）
    g.AddEdge("你", "张三")
    g.AddEdge("你", "李四")
    g.AddEdge("张三", "李四")

    g.Print()
}

输出：

图结构:
  你 → [张三 李四]
  张三 → [李四]
  李四 → (无出边)

1.3 为什么后端程序员必须懂图论？

因为所有的关系和依赖都是图：

你看，图论无处不在。不懂图论，就看不懂系统架构的依赖关系。

二、有向无环图（DAG）：CI/CD的数学基础

2.1 什么是DAG？

DAG（Directed Acyclic Graph）：有向无环图。

翻译成人话：箭头单向流动，永远走不回原点。

示例：CI/CD流水线

代码提交 → 编译 → 单元测试 → 集成测试 → 部署

这是个DAG，因为：
– 有方向：必须先编译才能测试
– 无环：不能部署完了又回去编译

2.2 Go实现DAG

package main

import "fmt"

type DAG struct {
    Graph
}

func NewDAG() *DAG {
    return &DAG{
        Graph: Graph{
            Vertices: []string{},
            Edges:    make(map[string][]string),
        },
    }
}

// 检测是否有环（DFS）
func (dag *DAG) HasCycle() bool {
    visited := make(map[string]bool)
    recStack := make(map[string]bool) // 递归栈

    var dfs func(string) bool
    dfs = func(v string) bool {
        visited[v] = true
        recStack[v] = true

        for _, neighbor := range dag.Edges[v] {
            if !visited[neighbor] {
                if dfs(neighbor) {
                    return true
                }
            } else if recStack[neighbor] {
                // 在递归栈中，说明有环
                return true
            }
        }

        recStack[v] = false
        return false
    }

    for _, v := range dag.Vertices {
        if !visited[v] {
            if dfs(v) {
                return true
            }
        }
    }

    return false
}

func main() {
    // 场景1：正常的CI/CD流水线（无环）
    pipeline := NewDAG()
    pipeline.AddVertex("代码提交")
    pipeline.AddVertex("编译")
    pipeline.AddVertex("测试")
    pipeline.AddVertex("部署")

    pipeline.AddEdge("代码提交", "编译")
    pipeline.AddEdge("编译", "测试")
    pipeline.AddEdge("测试", "部署")

    fmt.Println("CI/CD流水线:")
    pipeline.Print()
    fmt.Printf("是否有环: %v\n\n", pipeline.HasCycle())

    // 场景2：错误的依赖（有环）
    badPipeline := NewDAG()
    badPipeline.AddVertex("A")
    badPipeline.AddVertex("B")
    badPipeline.AddVertex("C")

    badPipeline.AddEdge("A", "B")
    badPipeline.AddEdge("B", "C")
    badPipeline.AddEdge("C", "A") // 循环依赖！

    fmt.Println("错误的依赖:")
    badPipeline.Print()
    fmt.Printf("是否有环: %v\n", badPipeline.HasCycle())
}

输出：

CI/CD流水线:
  代码提交 → [编译]
  编译 → [测试]
  测试 → [部署]
  部署 → (无出边)
是否有环: false

错误的依赖:
  A → [B]
  B → [C]
  C → [A]
是否有环: true

2.3 拓扑排序：找出正确的执行顺序

问题： 有一堆任务，它们之间有依赖关系，怎么安排执行顺序？

拓扑排序（Topological Sort）：把DAG的节点排成一条线，保证所有箭头都从左指向右。

Go实现：

// 拓扑排序（Kahn算法）
func (dag *DAG) TopologicalSort() []string {
    // 1. 计算每个节点的入度
    inDegree := make(map[string]int)
    for _, v := range dag.Vertices {
        inDegree[v] = 0
    }
    for _, neighbors := range dag.Edges {
        for _, neighbor := range neighbors {
            inDegree[neighbor]++
        }
    }

    // 2. 找出所有入度为0的节点（起点）
    queue := []string{}
    for _, v := range dag.Vertices {
        if inDegree[v] == 0 {
            queue = append(queue, v)
        }
    }

    // 3. BFS遍历
    result := []string{}
    for len(queue) > 0 {
        // 取出队首
        current := queue[0]
        queue = queue[1:]
        result = append(result, current)

        // 删除当前节点的所有出边
        for _, neighbor := range dag.Edges[current] {
            inDegree[neighbor]--
            if inDegree[neighbor] == 0 {
                queue = append(queue, neighbor)
            }
        }
    }

    // 4. 检查是否所有节点都被访问（有环则无法完成）
    if len(result) != len(dag.Vertices) {
        return nil // 有环，无法拓扑排序
    }

    return result
}

func main() {
    // 微服务启动顺序
    services := NewDAG()
    services.AddVertex("配置中心")
    services.AddVertex("注册中心")
    services.AddVertex("网关")
    services.AddVertex("用户服务")
    services.AddVertex("订单服务")

    // 依赖关系
    services.AddEdge("配置中心", "注册中心")
    services.AddEdge("注册中心", "网关")
    services.AddEdge("注册中心", "用户服务")
    services.AddEdge("注册中心", "订单服务")
    services.AddEdge("用户服务", "订单服务")

    fmt.Println("微服务依赖关系:")
    services.Print()

    order := services.TopologicalSort()
    fmt.Printf("\n启动顺序: %v\n", order)
}

输出：

微服务依赖关系:
  配置中心 → [注册中心]
  注册中心 → [网关 用户服务 订单服务]
  网关 → (无出边)
  用户服务 → [订单服务]
  订单服务 → (无出边)

启动顺序: [配置中心 注册中心 网关 用户服务 订单服务]

三、最短路径：地图导航的数学原理

3.1 带权图（Weighted Graph）

权重（Weight）：边上的数字，表示距离、成本、时间等。

示例：城市间的距离

北京 --800km--> 上海
北京 --1200km--> 广州
上海 --1400km--> 广州

Go代码表示：

type WeightedGraph struct {
    Vertices []string
    Edges    map[string]map[string]int // from -> to -> weight
}

func NewWeightedGraph() *WeightedGraph {
    return &WeightedGraph{
        Vertices: []string{},
        Edges:    make(map[string]map[string]int),
    }
}

func (g *WeightedGraph) AddVertex(v string) {
    g.Vertices = append(g.Vertices, v)
    if g.Edges[v] == nil {
        g.Edges[v] = make(map[string]int)
    }
}

func (g *WeightedGraph) AddEdge(from, to string, weight int) {
    g.Edges[from][to] = weight
}

3.2 Dijkstra算法：找最短路径

问题： 从北京到广州，怎么走最近？

Dijkstra算法核心思想：
1. 从起点开始，记录到每个点的最短距离
2. 每次选择距离最小的未访问节点
3. 更新它的邻居的距离
4. 重复直到到达终点

Go实现（简化版）：

import (
    "container/heap"
    "math"
)

// 优先队列节点
type PQItem struct {
    vertex   string
    distance int
    index    int
}

type PriorityQueue []*PQItem

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

// Dijkstra最短路径
func (g *WeightedGraph) Dijkstra(start, end string) (int, []string) {
    dist := make(map[string]int)
    prev := make(map[string]string)

    // 初始化距离为无穷大
    for _, v := range g.Vertices {
        dist[v] = math.MaxInt32
    }
    dist[start] = 0

    // 优先队列
    pq := &PriorityQueue{}
    heap.Init(pq)
    heap.Push(pq, &PQItem{vertex: start, distance: 0})

    visited := make(map[string]bool)

    for pq.Len() > 0 {
        current := heap.Pop(pq).(*PQItem)

        if visited[current.vertex] {
            continue
        }
        visited[current.vertex] = true

        // 到达终点
        if current.vertex == end {
            break
        }

        // 更新邻居距离
        for neighbor, weight := range g.Edges[current.vertex] {
            newDist := dist[current.vertex] + weight
            if newDist < dist[neighbor] {
                dist[neighbor] = newDist
                prev[neighbor] = current.vertex
                heap.Push(pq, &PQItem{vertex: neighbor, distance: newDist})
            }
        }
    }

    // 重建路径
    path := []string{}
    for at := end; at != ""; at = prev[at] {
        path = append([]string{at}, path...)
        if at == start {
            break
        }
    }

    return dist[end], path
}

3.3 使用示例：城市导航

func main() {
    // 构建城市地图
    cityMap := NewWeightedGraph()

    cities := []string{"北京", "上海", "广州", "深圳", "成都"}
    for _, city := range cities {
        cityMap.AddVertex(city)
    }

    // 添加道路（双向）
    cityMap.AddEdge("北京", "上海", 1200)
    cityMap.AddEdge("上海", "北京", 1200)

    cityMap.AddEdge("北京", "成都", 1800)
    cityMap.AddEdge("成都", "北京", 1800)

    cityMap.AddEdge("上海", "广州", 1400)
    cityMap.AddEdge("广州", "上海", 1400)

    cityMap.AddEdge("广州", "深圳", 140)
    cityMap.AddEdge("深圳", "广州", 140)

    cityMap.AddEdge("成都", "广州", 2100)
    cityMap.AddEdge("广州", "成都", 2100)

    // 查找最短路径
    distance, path := cityMap.Dijkstra("北京", "深圳")

    fmt.Printf("从北京到深圳的最短路径:\n")
    fmt.Printf("路径: %v\n", path)
    fmt.Printf("总距离: %d km\n", distance)
}

输出：

从北京到深圳的最短路径:
路径: [北京 上海 广州 深圳]
总距离: 2740 km

四、小结

这篇文章的核心观点：

1. 图就是”节点+边”的关系网络，有向图、无向图、带权图是最基础的类型
2. DAG（有向无环图）是CI/CD流水线的数学基础，检测环用DFS，时间复杂度O(V+E)
3. 拓扑排序解决依赖顺序问题，微服务启动、任务调度都靠它
4. Dijkstra算法找最短路径，地图导航、网络路由都用这个原理
5. 图论无处不在：微服务依赖、社交网络、任务调度、地图导航都是图

记住这个对照表：

实战建议：
– 微服务启动前先做拓扑排序，避免依赖错误
– CI/CD流水线设计时检测环，防止死锁
– 路由选择用Dijkstra，找最优路径

下次面试官问”如何检测微服务循环依赖”，你就可以回答：用DFS遍历依赖图，维护递归栈，如果遇到栈中节点说明有环。

参考资料
– 《算法导论》第22章：图的基本算法
– 《算法导论》第24章：单源最短路径
– Kubernetes源码：拓扑排序实现

返回系列总览

👉 程序员数学扫盲课：完整课程大纲