知识体系

图论

10分钟阅读

图论

核心观点：图是描述对象间关系的数学模型，是网络分析和社交网络的理论基础。

🎯 这 20% 能解决哪些问题

你遇到的困惑本质原因马上能改的动作
依赖装了又拆，循环依赖警告不断依赖图有环，不是 DAG用 DFS 找强连通分量，先拆 SCC 再解耦
上线/迁移/任务执行顺序总出错没按拓扑序执行把依赖写成图，拓扑分层，同层并行
微服务雪崩，一个下游挂全链路挂调用图里的关键路径与入度高的节点无隔离算出介数/入度最大的节点，优先加超时+熔断+降级
社交/组织/设备网络里找「一个点挂了一片」求的是割点与连通分量用并查集或 Tarjan 找割点/桥，加冗余边
最短路径、最低成本方案选型不确定有权图算法选错非负权用 Dijkstra，有负权/检测负环用 Bellman-Ford
去重/关联查询越跑越慢用嵌套循环判连通改用并查集，O(α(n)) 近似常数
缓存失效时一层层往下推不知道推到哪缓存依赖是 DAG记录反向依赖图，按拓扑序逆推失效

📊 图的基本概念

图的定义

概念定义表示
图顶点和边的集合G=(V,E)
有向图边有方向<u,v>
无向图边无方向{u,v}
加权图边有权重w(u,v)

图的表示

graph TB
    subgraph 图的表示
        A1["邻接矩阵<br/>A[i,j] = 1 若相邻"]
        A2["邻接表<br/>每个顶点的邻居"]
        A3["边列表<br/>所有边的集合"]
    end    
    A1 & A2 & A3
    
    style A1 fill:#ffebee

📈 特殊图

特殊图类型

类型定义性质
完全图所有顶点相连边数=n(n-1)/2
二分图顶点分为两组可2-染色
平面图可平面嵌入边不相交
树连通无环边数=n-1

树的性质

graph TB
    subgraph 树性质
        A1["连通<br/>任意两点可达"]
        A2["无环<br/>无回路"]
        A3["唯一路径<br/>两点间唯一"]
        A4["边数<br/>|E|=|V|-1"]
    end    
    A1 & A2 & A3 & A4
    
    style A1 fill:#ffebee

🔢 图的性质

度与路径

概念定义意义
度连接边数节点重要性
入度指向的边数有向图
出度发出的边数有向图
路径边的序列连通性

连通性

graph TB
    subgraph 连通性
        A1["连通图<br/>任意两点可达"]
        A2["强连通<br/>有向图双向可达"]
        A3["弱连通<br/>忽略方向连通"]
        A4["连通分量<br/>最大连通子图"]
    end    
    A1 & A2 & A3 & A4
    
    style A1 fill:#ffebee

🎯 图算法

遍历算法

算法原理应用
BFS广度优先最短路径
DFS深度优先拓扑排序

最短路径

算法复杂度特点
DijkstraO(V²)非负权
Bellman-FordO(VE)负权边
FloydO(V³)全源最短路径

最小生成树

graph TB
    subgraph 最小生成树
        A1["Kruskal<br/>边排序+并查集"]
        A2["Prim<br/>顶点扩展"]
    end    
    A1 & A2
    
    style A1 fill:#ffebee

🛠 工程中的图：六种最常见的用法

工程场景图的形态需要的算法一句结论
包/模块依赖有向图环检测、拓扑排序有环就不能分阶段构建，必须先拆 SCC
任务调度/CI加权 DAG关键路径（最长路径）整体工期由关键路径决定，优化非关键任务无效
调用链/服务拓扑有向图 + 统计入度/出度、介数入度高的服务是爆炸半径最大的点，优先隔离
网络路由加权图Dijkstra / Bellman-Ford链路状态协议本质是跑最短路
账户/设备/标签归组无向图并查集（连通分量）只关心「是否同一堆」时用并查集，不建完整邻接表
状态机与迁移合法性有向图可达性、环「不可达状态」要么删要么就是死代码
推荐/关系查询稀疏图BFS 限定层数好友的二度关系查询必须限制深度，否则 O(度^层数) 爆炸
graph LR
    A["写下依赖边"] --> B["先做环检测"]
    B --> C["拓扑排序定顺序"]
    C --> D["关键路径定工期"]
    D --> E["同层任务并行执行"]
    E --> F["监控入度高的节点"]

两个必记结论：

  • 树 = 连通无环图，边数 n-1；所以「n 个服务互相调用不形成环」时，最少要 n-1 条依赖边，加一条就成环。
  • 握手定理：所有顶点的度之和 = 2|E| ⇒ 奇数度的顶点个数必为偶。用于校验数据（如关系表自连接统计是否漏行）。

🤖 机器学习应用

图神经网络

graph TB
    subgraph 图神经网络
        A1["图卷积<br/>邻居聚合"]
        A2["图注意力<br/>注意力加权"]
        A3["图池化<br/>层次化"]
    end    
    A1 & A2 & A3
    
    style A1 fill:#ffebee

社交网络分析

应用方法意义
社区发现图分割群组识别
中心性分析度/介数/接近中心性影响力排序
链接预测图特征关系预测

🎯 核心结论

图论核心概念

  1. 图：对象和关系的数学模型
  2. 度：节点连接数
  3. 路径：边的序列
  4. 连通性：可达性
  5. 算法：遍历、最短路径、最小生成树

学习路径

图论学习四步骤：
1. 基本概念：顶点、边、度
2. 特殊图：树、完全图、二分图
3. 图算法：遍历、最短路径
4. 应用：图神经网络、社交网络

🎓 实战场景（TIL）

  • 场景：发布时 A 依赖 B 的新接口，B 又依赖 A 的新字段，两边都不敢先发。本质：依赖图有环。要点：环必须靠 expand-contract 拆成两个阶段（各自先兼容），而不是靠半夜协调顺序。
  • 场景：构建耗时 40 分钟，优化了三个小任务只降了 2 分钟。本质：优化的是非关键路径。要点：先算最长路径，只动关键路径上的任务。
  • 场景：好友关系二度查询在头部用户上超时。本质：社交图是幂律分布，存在入度极大的点，O(度^2) 爆炸。要点：先取前 N 个邻居再扩展，并按度数做缓存与限流。

📋 一页速查

我要做选这个
判断依赖能否排序DFS 着色法检环；有环先缩强连通分量
求执行顺序拓扑排序（入度为 0 先出队）
求最短路径（非负权）Dijkstra + 堆，O(E log V)
有负权或要检负环Bellman-Ford，O(VE)
全源最短路、V 小Floyd，O(V^3)
只问「是否同一组」并查集（路径压缩 + 按秩合并）
找关键节点（割点/桥）Tarjan 或边双连通分量
无权图最短跳数BFS（按层扩展，首次命中即最短）
存储选择稀疏图用邻接表；频繁问「两点是否直接相连」用邻接矩阵
关系查询防炸限制遍历深度与每层邻居数，分页拉邻居

🔗 相关链接

📚 参考文献

  1. 《图论及其算法》- Bondy
  2. 《图论导引》- West
  3. 《离散数学》- 屈婉玲
  4. 《图神经网络》
  5. 《社交网络分析》
  6. 《网络科学》
  7. 《图论》- 王树禾
  8. 《算法导论》- 图算法部分

关系图谱

反向链接