2. 图论基础回顾：图的定义、节点与边、有向图与无向图、加权图与无权图、邻接矩阵与邻接表
2.1 图到底是什么？—— 从一次项目事故说起
我记得刚入行那会儿，接手过一个网络流量分析的项目。客户说“你们把节点重要性算出来就行”。我当时心想，不就是算个连接数吗？结果一跑数据，全乱套了。后来才发现，我连“图”的基本定义都没搞清楚。
说白了，图就是一种数据结构。它用来描述“东西”和“东西之间的关系”。
- 节点（Vertex）：就是那个“东西”。比如一个路由器、一个网页、一个人。
- 边（Edge）：就是“关系”。比如网线连接、超链接、朋友关系。
你想想看，整个互联网就是一个巨大的图。每个网站是一个节点，每个超链接是一条边。没有比这更直观的例子了。
核心定义：图 G = (V, E)，其中 V 是节点集合，E 是边集合。就这么简单。
2.2 有向图 vs 无向图 —— 方向决定一切
有一次我在做社交网络分析，发现 A 关注了 B，但 B 没关注 A。如果我用无向图去建模，那就完全错了。嗯，这里要注意：方向很重要。
- 无向图：边没有方向。比如“朋友关系”，你是我朋友，我也是你朋友。边 (u, v) 和 (v, u) 是同一个东西。
- 有向图：边有方向。比如“关注关系”、“网页链接”。边 u → v 和 v → u 是两码事。
我个人习惯，在分析网络流量时，一律用有向图。因为数据包从 A 到 B，和从 B 到 A，含义完全不同。你想想看，如果忽略方向，你可能会把“被攻击”误判成“主动连接”。
避坑指南：我曾经在一个项目中，把微博的“关注关系”建模成无向图，结果 PageRank 算出来全是错的。后来改成有向图，才对了。记住：社交关系里，“关注”和“被关注”是两个不同的概念。
2.3 加权图 vs 无权图 —— 权重里藏着秘密
无权图只告诉你“有没有连接”。但现实中，连接是有“强度”的。
- 无权图：边只有存在或不存在。适合分析“是否连通”。
- 加权图：每条边带一个数值（权重）。比如带宽、距离、交易金额。
我在做金融反欺诈时，就遇到过这种情况。两个账户之间有转账，但金额只有 1 块钱，和转账 100 万的，能一样吗？当然不能。所以必须用加权图，权重就是转账金额。
经验之谈：在节点重要性评估中，加权图往往比无权图更有价值。因为权重反映了“关系的重要性”。一个高权重的邻居，比十个低权重的邻居更有影响力。
2.4 邻接矩阵与邻接表 —— 存储方式的选择
好了，图定义好了，怎么存？这是每个工程师都要面对的实际问题。我见过不少新手，一上来就用邻接矩阵，结果内存爆了。
邻接矩阵
用一个 n × n 的矩阵来存。A[i][j] = 1 表示节点 i 到 j 有边，0 表示没有。如果是加权图，A[i][j] 就存权重。
// 无向无权图的邻接矩阵示例
// 节点: 0, 1, 2, 3
// 边: 0-1, 0-2, 1-3, 2-3
0 1 2 3
0: [0, 1, 1, 0]
1: [1, 0, 0, 1]
2: [1, 0, 0, 1]
3: [0, 1, 1, 0]
注意：邻接矩阵的空间复杂度是 O(n²)。如果图有 10 万个节点，矩阵就有 100 亿个元素。你算算内存？我当年就是没算这个，导致程序直接 OOM 了。
邻接表
每个节点维护一个列表，只存它实际连接的邻居。空间复杂度 O(n + m)，m 是边的数量。
// 同一个图的邻接表表示
0: [1, 2]
1: [0, 3]
2: [0, 3]
3: [1, 2]
我个人习惯，在大多数实际项目中都用邻接表。为什么呢？因为现实世界的图往往是稀疏的——节点很多，但每个节点的邻居很少。比如社交网络，一个人平均几百个好友，但总用户数可能是几亿。邻接矩阵根本存不下。
选择建议：
- 图很密集（边接近 n²）→ 用邻接矩阵，查询快
- 图很稀疏（边远小于 n²）→ 用邻接表，省内存
- 需要频繁判断两点是否相连 → 邻接矩阵 O(1)
- 需要遍历邻居 → 邻接表更高效
2.5 本章知识体系总览
下面这张图，是我自己梳理的。它把本章的核心概念串在了一起。你看一遍，应该就能明白图论基础在节点重要性评估中的位置了。
2.6 小结：这些基础到底有什么用？
你可能会问，讲了这么多定义，跟节点重要性评估有什么关系？
关系大了去了。我举个例子：
- 你要算一个节点的“度中心性”，就得先知道图是有向还是无向。有向图里，入度和出度是两个不同的指标。
- 你要算“介数中心性”，就得知道边有没有权重。加权图的最短路径和无权图完全不同。
- 你要存图、遍历图，就得选邻接矩阵还是邻接表。选错了，程序跑不动。
说白了，图论基础就是工具。你手里拿的是螺丝刀还是锤子，决定了你能干什么活。后面几章，我们会基于这些基础，一步步搭建节点重要性评估的完整体系。
一句话总结：图 = 节点 + 边。方向决定关系语义，权重决定关系强度。存图选邻接表还是矩阵，看图的稀疏程度。这些搞清楚了，后面的算法才能落地。
公众号:蓝海资料掘金营，微信deep3321