3、图论基础回顾：图的定义与表示
各位同学，咱们今天聊点基础的东西。图论，说白了就是研究“节点”和“边”的学问。你想想看，股票市场里，每只股票就是一个节点，它们之间的相关性就是边。嗯，就是这么简单。
我个人习惯把图理解成一种“关系容器”。它不关心节点本身长什么样，只关心节点之间有没有连接。这在金融分析里特别有用——我们不在乎某只股票代码是多少，只在乎它跟别的股票怎么联动。
3.1 图的定义
一个图 G 由两部分组成：顶点集合 V 和边集合 E。记作 G = (V, E)。
- 顶点（Vertex）：图中的基本单元。在股票关联分析中，顶点就是一只股票。
- 边（Edge）：顶点之间的连接。可以是有向的，也可以是无向的。
举个例子：假设我们有 5 只股票：茅台、五粮液、宁德时代、比亚迪、腾讯。它们之间的关联关系就构成了一张图。茅台和五粮液都是白酒股，它们之间有一条边；宁德时代和比亚迪是新能源产业链的，也有一条边。
重要概念区分：
- 无向图：边没有方向。A 和 B 关联，B 和 A 也关联。股票相关性通常用无向图。
- 有向图：边有方向。A → B 不代表 B → A。比如资金流向，A 流入 B，但 B 不一定流入 A。
- 加权图：每条边带一个权重值。比如相关系数 0.8 就比 0.3 的边“更粗”。
我在项目中遇到过一个问题：刚开始做股票关联分析时，我直接用无向图。后来发现，有些资金是单向流动的，比如机构买入某只股票，但散户不一定跟着买。这时候就得用有向图了。嗯，这里要注意，选错图类型，后面的分析全白做。
3.2 图的表示方法
图在计算机里怎么存？主要有两种方式：邻接矩阵和邻接表。我建议你两种都掌握，因为不同场景下效率差别很大。
3.2.1 邻接矩阵
邻接矩阵是一个 N×N 的二维数组，N 是顶点数。如果顶点 i 和顶点 j 之间有边，那么 A[i][j] = 1（或权重值），否则为 0。
# 一个简单的邻接矩阵示例
# 4只股票：A, B, C, D
# 边：A-B, A-C, B-D
adj_matrix = [
[0, 1, 1, 0], # A 连接 B 和 C
[1, 0, 0, 1], # B 连接 A 和 D
[1, 0, 0, 0], # C 只连接 A
[0, 1, 0, 0] # D 只连接 B
]
邻接矩阵的好处是：查询任意两个顶点之间是否有边，时间复杂度是 O(1)。但坏处也很明显——空间复杂度是 O(N²)。如果你有 3000 只股票，矩阵就有 900 万个元素。大部分是 0，浪费内存。
避坑指南：我曾经用邻接矩阵存 5000 只股票的关联图，结果内存直接爆了。后来才意识到，股票关联图其实是稀疏图——大部分股票之间没有强相关性。这时候用邻接表更合适。
3.2.2 邻接表
邻接表只存有边的连接。每个顶点维护一个列表，列表里存的是它连接到的顶点。
# 同样的图，用邻接表表示
adj_list = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A'],
'D': ['B']
}
邻接表的空间复杂度是 O(V + E)，V 是顶点数，E 是边数。对于稀疏图来说，这比邻接矩阵省太多内存了。
| 表示方法 | 空间复杂度 | 查询边 | 遍历邻居 | 适用场景 |
|---|---|---|---|---|
| 邻接矩阵 | O(V²) | O(1) | O(V) | 稠密图、小规模图 |
| 邻接表 | O(V+E) | O(degree) | O(degree) | 稀疏图、大规模图 |
我个人习惯：在金融场景下，股票数量通常几百到几千，但相关性强的股票其实不多。所以我一般用邻接表。只有在做全市场相关性热力图时，才会用邻接矩阵——因为那时候我需要快速查任意两只股票的相关性。
3.3 图的遍历
遍历就是“走一遍图”。两种经典方法：广度优先搜索（BFS）和深度优先搜索（DFS）。
3.3.1 广度优先搜索（BFS）
BFS 像水波扩散。从一个顶点出发，先访问它所有的邻居，再访问邻居的邻居。一层一层往外走。
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
print(f"访问节点: {node}")
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# 使用示例
graph = {
'茅台': ['五粮液', '泸州老窖'],
'五粮液': ['茅台', '山西汾酒'],
'泸州老窖': ['茅台'],
'山西汾酒': ['五粮液']
}
bfs(graph, '茅台')
BFS 在股票分析里有什么用？我举个例子：你想找某只股票的“关联链”。比如茅台涨了，哪些股票会跟着涨？BFS 可以帮你找到所有通过“一步关联”、“两步关联”能影响到的股票。这在做风险传导分析时特别有用。
3.3.2 深度优先搜索（DFS）
DFS 像走迷宫。一条路走到黑，走不通了再回头。它用栈（递归或显式栈）来实现。
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
print(f"访问节点: {node}")
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
# 使用示例
dfs(graph, '茅台')
DFS 适合找“路径”。比如我想知道茅台和宁德时代之间有没有一条完整的传导路径——茅台涨 → 白酒板块涨 → 消费板块涨 → 新能源板块？DFS 可以帮你找到这条路径。
我的经验：BFS 和 DFS 的选择取决于你的目标。找“最短路径”用 BFS，找“是否存在路径”用 DFS。在股票关联分析中，我通常先用 BFS 看关联范围，再用 DFS 找具体传导路径。
3.4 图的属性
图有几个关键属性，在股票分析中经常用到。
3.4.1 度（Degree）
一个顶点的度，就是它有多少条边。在无向图中，度就是邻居的数量。在有向图中，分为入度（指向它的边数）和出度（它指向别人的边数）。
在股票市场里，度高的股票意味着什么？说明它跟很多股票都有相关性。这种股票往往是“核心资产”或者“龙头股”。我记得有一次分析沪深300的关联图，茅台的度是最高的——它跟消费、金融、甚至新能源都有一定的相关性。
3.4.2 连通性（Connectivity）
如果图中任意两个顶点之间都有路径，那这个图就是连通图。否则，它由多个连通分量组成。
在股票分析中，连通分量很有意思。它天然地把股票分成了不同的“板块”或“概念”。比如白酒股在一个连通分量里，新能源股在另一个分量里。如果两个分量之间没有边，说明这两个板块之间没有明显的联动关系。
实战技巧：我经常用连通分量来做“板块发现”。不需要人工标注哪些股票属于哪个板块，直接跑一遍连通分量算法，图结构自己就把板块分出来了。当然，这需要你设置一个合理的相关性阈值——太低了所有股票都连在一起，太高了每个股票都是孤岛。
3.4.3 聚类系数（Clustering Coefficient）
聚类系数衡量一个顶点的邻居之间互相连接的紧密程度。公式很简单：
局部聚类系数 = (邻居之间实际存在的边数) / (邻居之间可能存在的最大边数)
如果某只股票的邻居之间也互相连接，说明这个股票所在的“圈子”很紧密。比如白酒板块，茅台、五粮液、泸州老窖之间互相都有强相关性，聚类系数就很高。
聚类系数高的股票，往往意味着它所在的板块是“抱团”的。这在做风险分散时很重要——如果你持有一只聚类系数高的股票，那它的同板块股票大概率也涨跌同步，分散风险的效果就不好。
3.5 本章小结
好了，图论基础就讲这些。你想想看，其实图论没那么神秘。顶点就是股票，边就是相关性，遍历就是找关联路径，度就是影响力，连通性就是板块划分，聚类系数就是抱团程度。
这些概念在后面的图神经网络课程里会反复用到。特别是邻接矩阵和邻接表的选择，会直接影响你构建图神经网络的效率。我个人建议：先拿小规模数据用邻接矩阵跑通，再切换到邻接表做大规模优化。
下一章，我们会把这些概念真正用到股票数据上，构建一个真实的股票关联图。到时候你就知道，这些基础概念有多重要了。