图论基础：从定义到表示方法

图论听起来有点抽象，但其实它就在我们身边。你打开手机的地图导航，里头那个路网就是一张图；你在数据库里查药物和靶点的关系，画出来也是一张图。说白了，图就是研究"东西怎么连在一起"的学问。

我在做药物知识图谱的时候，每天打交道的就是图。顶点代表药物、靶点、疾病，边代表它们之间的相互作用。理解了图论基础，后面的特征提取才能站得住脚。好，我们直接进入正题。

图的定义：顶点与边

图是什么？数学定义很简单：图 G = (V, E)。V 是顶点集合，E 是边集合。

顶点（Vertex），你可以把它理解为"实体"。在药物知识图谱里，顶点可以是阿司匹林、布洛芬，也可以是 COX-1、COX-2 这些靶点。边（Edge）就是"关系"，比如"阿司匹林抑制COX-1"这条边，就连接了两个顶点。

我刚开始接触图论时，总觉得顶点和边太简单了。但后来发现，真正决定图结构质量的，恰恰是你怎么定义顶点和边。定义得太粗，信息都丢了；定义得太细，图又大得跑不动。这个平衡点，我建议你从业务目标反推——先想清楚你要用图来回答什么问题，再去定边界。

举个例子，一个最简单的药物-靶点图：

顶点集 V = {阿司匹林, 布洛芬, COX-1, COX-2}
边集 E = {(阿司匹林, COX-1), (阿司匹林, COX-2), (布洛芬, COX-1), (布洛芬, COX-2)}

每条边代表"抑制"关系。你看，图就是这么直观。

有向图与无向图：方向决定语义

边有了，但方向呢？这取决于关系的性质。

有向图的边带箭头，表示单向关系。比如"药物→靶点"是抑制，反过来不成立，那就得用有向边。我个人习惯把药物-靶点相互作用建模为有向图，因为方向里藏着作用机制。

无向图的边没有方向，表示对称关系。比如药物-药物联合使用，A 和 B 联用，B 和 A 也联用，方向没意义。蛋白质-蛋白质相互作用也经常用无向图建模。

你想想看，选错方向会怎样？明明是无向关系，你非加个箭头，后续计算出来的特征就会带偏；反过来，有向关系你当无向处理，也会丢失关键信息。方向选对了，图结构才能忠实反映真实世界。

特性	有向图	无向图
边的方向	有箭头，单向	无箭头，对称
适用场景	抑制、激活、调控	结合、联合、相互作用
邻接矩阵对称性	不对称	对称
药物图谱例子	药物→靶点（抑制）	药物-药物（联合）

图的表示方法：存到计算机里

定义清楚了，下一步就是存起来。计算机不认识顶点和边，它只认识数字和数组。最常见的两种表示方法是邻接矩阵和邻接表。

邻接矩阵

假设有 n 个顶点，就建一个 n×n 的矩阵。第 i 行第 j 列的值表示顶点 i 到顶点 j 是否有边。有向图和无向图都能表示，只不过无向图矩阵是对称的。

拿前面的药物-靶点例子来说，4 个顶点，邻接矩阵长这样：

# 顶点顺序：[阿司匹林, 布洛芬, COX-1, COX-2]
adj_matrix = [
    [0, 0, 1, 1],   # 阿司匹林 → COX-1, COX-2
    [0, 0, 1, 1],   # 布洛芬 → COX-1, COX-2
    [0, 0, 0, 0],   # COX-1 没有出边
    [0, 0, 0, 0]    # COX-2 没有出边
]

简单直观，但问题也很明显：如果图有 1 万个顶点，矩阵就是 1 亿个元素。大部分元素是 0，太浪费了。

邻接表

邻接表就聪明多了——每个顶点只存它"认识"的邻居。用哈希表或列表来实现：

# 同样是上面的有向图
adj_list = {
    '阿司匹林': ['COX-1', 'COX-2'],
    '布洛芬':   ['COX-1', 'COX-2'],
    'COX-1':    [],
    'COX-2':    []
}

我只存有边的信息，空顶点不占空间。在药物知识图谱里，顶点动不动就几十万，但每个顶点平均连接的边可能只有几条。这时候邻接表的内存效率完胜邻接矩阵。

两种表示方法的对比与选择

邻接矩阵和邻接表各有长短，我遇到过不少人在这个选择上翻车。来，直接对比一下：

对比维度	邻接矩阵	邻接表
内存占用	O(n²)，固定大小	O(n+e)，e 为边数
查询两顶点是否有边	O(1)，直接取下标	O(d)，d 为顶点度
遍历某顶点的邻居	O(n)，要扫一整行	O(d)，直达邻居列表
适合图类型	稠密图	稀疏图
药物图谱适用性	差（顶点多、边稀疏）	好（省内存、遍历快）

另外还有一个容易被忽略的点：当你需要在图上做大量"插入/删除边"的操作时，邻接表的动态扩展更灵活。邻接矩阵一旦确定大小，改起来就得重新分配整块内存。嗯，这点在你构建动态知识图谱时会特别明显。

好，图论基础就聊到这儿。顶点和边搭起了骨架，有向/无向赋予了语义，邻接矩阵和邻接表让图能在计算机里跑起来。这些东西看似基础，但往后 29 章的特征提取方法，全都建在这几块基石上。你把这个底打牢了，后面学起来会顺很多。