图论基础：从零开始认识图
各位同学，今天我们来聊聊图论。说实话，我第一次接触图论是在做支付网络风控的时候。当时要分析几百万个账户之间的资金流转关系，用传统的关系型数据库查得我头皮发麻。后来我才意识到，这不就是个图的问题吗？
图论听起来高大上，其实没那么玄乎。你想想看，微信好友关系、城市之间的航班、甚至你每天点的外卖配送路线，背后都是图在支撑。咱们今天就把图论的基础打牢。
图的基本概念：节点、边、度
先说说图到底长什么样。一个图由两部分组成：节点和边。节点就是图中的点，边就是连接点的线。
举个例子，假设我们要分析一个社交网络。每个用户就是一个节点，用户之间的好友关系就是一条边。就这么简单。
核心定义：
- 节点（Vertex）：图中的基本元素，也叫顶点。我习惯用 V 表示节点集合。
- 边（Edge）：连接两个节点的线，用 E 表示边的集合。
- 度（Degree）：一个节点连接的边的数量。说白了，就是你有几个邻居。
这里有个坑，我刚开始学的时候经常搞混。在无向图中，一个节点的度就是它有多少条边连着。但在有向图里，度要分成入度和出度。入度是指向该节点的边数，出度是从该节点出发的边数。
我的经验：在金融网络中，节点的度往往能反映重要程度。比如一个银行账户如果出度特别高，说明它频繁向外转账，这可能是洗钱的特征。我曾经在反洗钱项目中就用这个特征抓到了几个异常账户。
图的类型：有向图、无向图、加权图
图不是千篇一律的，根据边的性质不同，我们可以把图分成几种类型。我个人觉得，理解这些类型比背定义重要得多。
无向图
无向图的边没有方向。就像微信好友关系，你加了我，我们就是好友，不分谁加谁。边用 (u, v) 表示，u 和 v 是对等的。
有向图
有向图的边有方向。就像微博关注，你关注了某大V，但大V不一定关注你。边用 <u, v> 表示，箭头从 u 指向 v。
注意：在金融网络中，资金流向天然就是有向的。A 转账给 B，和 B 转账给 A，完全是两码事。我见过有人用无向图分析资金流，结果把洗钱路径都搞反了。
加权图
加权图的每条边带有一个数值，叫权重。权重可以表示距离、成本、金额等。比如城市之间的航班，边上的权重就是飞行时间或票价。
加权图在金融领域太常见了。转账金额就是权重，交易手续费也是权重。我做过一个最优换汇路径的项目，每条边的权重就是汇率，我们要找一条让收益最大化的路径。
| 图类型 | 边的特点 | 金融应用场景 |
|---|---|---|
| 无向图 | 无方向，对称关系 | 企业关联关系、共同持股 |
| 有向图 | 有方向，非对称关系 | 资金转账、借贷关系 |
| 加权图 | 边带权重 | 交易金额、汇率、风险评分 |
图的表示方法：邻接矩阵与邻接表
图在计算机里怎么存？这是个实际问题。我刚开始写代码时，用了个二维数组硬存，结果数据量一大就崩了。后来才学会用正确的表示方法。
邻接矩阵
邻接矩阵用一个二维数组来表示图。假设有 n 个节点，就建一个 n×n 的矩阵。如果节点 i 和节点 j 之间有边，矩阵的 (i, j) 位置就填 1（或权重值），否则填 0。
# 邻接矩阵示例 - 无向图
# 节点: A, B, C, D
# 边: A-B, A-C, B-D, C-D
adj_matrix = [
[0, 1, 1, 0], # A 的邻居
[1, 0, 0, 1], # B 的邻居
[1, 0, 0, 1], # C 的邻居
[0, 1, 1, 0] # D 的邻居
]
# 检查 A 和 C 是否相连
print(adj_matrix[0][2]) # 输出 1，表示相连优缺点分析：
- 优点：判断两个节点是否相连，时间复杂度 O(1)，快得很。
- 缺点：空间复杂度 O(n²)，节点一多就炸。10000 个节点就要 1 亿个格子。
邻接表
邻接表用列表或字典来存每个节点的邻居。每个节点后面跟着一个列表，里面是它所有邻居的编号。
# 邻接表示例 - 有向图
# 节点: 1, 2, 3, 4
# 边: 1->2, 1->3, 2->4, 3->4
adj_list = {
1: [2, 3],
2: [4],
3: [4],
4: []
}
# 获取节点 1 的所有邻居
print(adj_list[1]) # 输出 [2, 3]
# 加权图用元组存 (邻居, 权重)
weighted_adj_list = {
1: [(2, 100), (3, 200)],
2: [(4, 150)],
3: [(4, 250)],
4: []
}我的建议：在实际项目中，我 90% 的情况都用邻接表。原因很简单——金融网络通常是稀疏的。几百万个账户，每个账户的交易对手可能只有几十个。用邻接矩阵存，内存根本扛不住。我曾经处理过一个 50 万节点的图，邻接矩阵要 2500 亿个格子，而邻接表只用了不到 2GB。
知识体系总览
下面这张图把本章的核心内容串起来了。我画这张图的时候，特意把三种图类型和两种表示方法放在一起对比，方便你理解它们之间的关系。
避坑指南：我曾经在做一个资金链路分析项目时，用邻接矩阵存了 10 万个节点的图。程序跑起来直接 OOM，服务器都卡死了。后来换成邻接表，内存占用从 40GB 降到了 500MB。所以记住：金融网络几乎都是稀疏图，用邻接表就对了。
好了，图论的基础就这些。节点、边、度是核心三要素，有向无向加权是三种常见类型，邻接矩阵和邻接表是两种存储方式。这些东西看着简单，但后面所有的图算法——最短路径、社区发现、中心性分析——都建立在这个基础上。
下一节我们会用 Python 的 NetworkX 库把这些概念落地，写点能跑的代码。到时候你就知道，图论不是纸上谈兵，是真能解决实际问题的。
公众号:蓝海资料掘金营，微信deep3321