一、图论基础回顾：图的定义、类型与存储方式
说实话，每次带新人做图特征工程，我都要先问一句：「你理解图了吗？」
很多人一上来就调库、跑模型，结果连图的基本结构都说不清楚。嗯，这其实挺危险的。图论基础不牢，后面做特征工程很容易踩坑。
今天我们就从最根本的东西说起。我会结合自己这些年踩过的坑，帮你把图论基础打扎实。
1.1 图的定义：到底什么是图？
图，说白了就是「节点」和「边」的集合。节点代表实体，边代表关系。
我习惯用数学语言来定义：图 G = (V, E)，其中 V 是节点集合，E 是边集合。
举个例子：
- 社交网络里，每个人是一个节点，好友关系是一条边
- 电商场景中，每个商品是一个节点，用户购买行为是一条边
- 知识图谱里，每个实体是一个节点，实体间的关系是一条边
核心要点：图的核心就是「关系」。没有关系，就不叫图。
我在做推荐系统项目时，遇到过一个问题：用户和商品之间只有购买记录，没有显式的关系。当时我硬着头皮把购买行为当作边，结果模型效果很差。后来才明白——边必须代表有意义的交互，不能为了建图而建图。
1.2 图的类型：三种常见形态
图的世界里，主要有三种类型。我按实际项目中出现频率排序：
1.2.1 无向图
边没有方向。A 和 B 相连，B 和 A 也相连。
典型场景：社交网络中的好友关系。你加我好友，我加你好友，双向的。
我刚开始做图算法时，经常忽略方向性。有一次用无向图处理网页链接关系，结果 PageRank 算出来全是错的。嗯，这里要注意：网页链接是有向的，不能当无向图处理。
1.2.2 有向图
边有方向。A → B 和 B → A 是两回事。
典型场景：微博的关注关系、网页的超链接、知识图谱中的三元组。
我个人习惯在代码里用 networkx.DiGraph() 来创建有向图，这样方向性一目了然。
1.2.3 加权图
边上带权重。权重可以表示距离、相似度、流量等。
举个例子：
- 交通网络：边的权重是距离或时间
- 推荐系统：边的权重是用户对商品的评分
- 通信网络：边的权重是带宽或延迟
我的经验：加权图在实际项目中占比超过 70%。很多模型效果不好，就是因为忽略了边的权重信息。
我曾经做过一个物流路径优化项目，一开始用无权图算最短路径，结果推荐的路全是绕远的。后来加上距离权重，效果立竿见影。
1.3 图的存储方式：两种主流方案
图建好了，怎么存？这是个很实际的问题。我见过不少新手在这上面栽跟头。
1.3.1 邻接矩阵
用一个 N×N 的矩阵来存储图。N 是节点数。
- 如果节点 i 和节点 j 之间有边，矩阵[i][j] = 1（或权重值）
- 如果没有边，矩阵[i][j] = 0
代码示例：
import numpy as np
# 4个节点的无向图
adj_matrix = np.array([
[0, 1, 1, 0],
[1, 0, 0, 1],
[1, 0, 0, 1],
[0, 1, 1, 0]
])
print("邻接矩阵:\n", adj_matrix)
print("节点0的邻居:", np.where(adj_matrix[0] == 1)[0])避坑指南：我曾经用邻接矩阵存一个 10 万节点的图，结果内存直接爆了。10万×10万的矩阵，float 类型，需要 40GB 内存。所以，稀疏图千万别用邻接矩阵。
邻接矩阵的优缺点：
| 优点 | 缺点 |
|---|---|
| 查询边是否存在 O(1) | 空间复杂度 O(N²) |
| 适合稠密图 | 稀疏图浪费大量空间 |
| 矩阵运算方便（如 GCN） | 添加/删除节点成本高 |
1.3.2 邻接表
每个节点维护一个列表，存储它的邻居节点。
代码示例：
# 邻接表表示法
adj_list = {
0: [1, 2],
1: [0, 3],
2: [0, 3],
3: [1, 2]
}
# 加权图的邻接表
weighted_adj_list = {
0: [(1, 0.5), (2, 0.8)],
1: [(0, 0.5), (3, 0.3)],
2: [(0, 0.8), (3, 0.6)],
3: [(1, 0.3), (2, 0.6)]
}
print("节点0的邻居:", adj_list[0])
print("节点0的加权邻居:", weighted_adj_list[0])我的建议：实际项目中，90% 的情况用邻接表就够了。除非你的图非常稠密（边数接近 N²），否则别碰邻接矩阵。
邻接表的优缺点：
| 优点 | 缺点 |
|---|---|
| 空间复杂度 O(N+E) | 查询边是否存在 O(degree) |
| 适合稀疏图 | 不适合矩阵运算 |
| 添加/删除节点灵活 | 遍历邻居需要额外操作 |
1.4 知识体系总览
下面这张图，是我自己总结的图论基础知识框架。每次带新人，我都会先让他们看这张图：
1.5 实际项目中的选择策略
说了这么多理论，最后分享一点实战经验。
我一般这样选：
- 先看数据规模：节点数少于 1 万，用邻接矩阵；超过 1 万，用邻接表
- 再看图密度：边数接近 N² 用邻接矩阵，否则用邻接表
- 最后看算法需求：要做矩阵运算（如 GCN），用邻接矩阵；要做遍历（如 BFS/DFS），用邻接表
小技巧：如果你不确定用哪种，先用邻接表。因为从邻接表转邻接矩阵很容易，反过来就难了。
好了，图论基础就讲到这里。这些概念虽然基础，但真的很重要。后面我们做图特征工程时，每一步都离不开这些底层知识。