图 (Graph)

基本概念

  • 图：由顶点集合 V 和边集合 E 组成的非线性数据结构，记作 G = (V, E)。
  • 无向图 / 有向图：边是否有方向。
  • 度：无向图中与顶点相连的边数；有向图中分入度 (In-degree) 和出度 (Out-degree)。
  • 路径：顶点序列 v1, v2, …, vk，其中相邻顶点间有边。
  • 连通图 / 强连通图：任意两顶点间存在路径。
  • 带权图 (网)：边带有权值 (Weight)。
  • 完全图：每对不同顶点间均有边相连。

数据结构的三要素

  • 逻辑结构
    • 多对多关系：顶点之间通过边建立任意连接。
  • 存储结构
    • 邻接矩阵：二维数组 matrix[i][j] 表示顶点 i 到 j 的边（及权值）。
    • 邻接表：数组索引对应顶点，每个元素为链表/列表，存储相邻顶点。
    • 十字链表 (有向图) / 邻接多重表 (无向图)：优化特定场景的存储。
  • 数据的运算
    • 创建图、添加/删除顶点和边。
    • 遍历：深度优先搜索 (DFS)、广度优先搜索 (BFS)。
    • 路径计算：最短路径、最小生成树、拓扑排序等。

费曼理解

图就像一个城市的地铁路线图。车站是顶点，铁轨是边。有些铁轨是单向的（有向图），有些是双向的（无向图），铁轨上的数字表示通行时间（权值）。我们要做的是：记住地图（存储结构），然后找出从一个站到另一个站的最快路线（算法）。

内部实现：

用 Python 实现图的邻接表表示及核心 API（添加边、DFS、BFS）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
from collections import defaultdict, deque

class Graph:
    def __init__(self, directed=False):
        self.adj = defaultdict(list)  # 邻接表存储
        self.directed = directed

    def add_vertex(self, v):
        if v not in self.adj:
            self.adj[v] = []

    def add_edge(self, u, v):
        self.add_vertex(u)
        self.add_vertex(v)
        self.adj[u].append(v)
        if not self.directed:
            self.adj[v].append(u)

    # 深度优先遍历 (递归版)
    def dfs(self, start):
        visited = set()
        result = []
        def _dfs(v):
            visited.add(v)
            result.append(v)
            for neighbor in self.adj[v]:
                if neighbor not in visited:
                    _dfs(neighbor)
        _dfs(start)
        return result

    # 广度优先遍历
    def bfs(self, start):
        visited = {start}
        queue = deque([start])
        result = [start]
        while queue:
            v = queue.popleft()
            for neighbor in self.adj[v]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    result.append(neighbor)
                    queue.append(neighbor)
        return result

# 示例
g = Graph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
print("DFS:", g.dfs('A'))  # 输出: DFS: ['A', 'B', 'D', 'C'] (顺序可能不同)
print("BFS:", g.bfs('A'))  # 输出: BFS: ['A', 'B', 'C', 'D']

复杂度分析：

存储结构 空间复杂度 添加边 删除边 判断邻接 遍历邻接点
邻接矩阵 O(V²) O(1) O(1) O(1) O(V)
邻接表 O(V + E) O(1) (头插) O(E) O(degree) O(degree)

常用算法复杂度 (V: 顶点数, E: 边数)：

  • DFS / BFS 遍历：邻接表 O(V + E)，邻接矩阵 O(V²)。
  • Dijkstra (最短路径)：二叉堆实现 O((V+E) log V)。
  • Bellman-Ford：O(V·E)。
  • Floyd-Warshall：O(V³)。
  • Kruskal (最小生成树)：O(E log E)。
  • Prim (最小生成树)：邻接矩阵 O(V²)，邻接表 + 堆 O(E log V)。

应用场景：

  • 最短路径问题：
    • 经典问题：导航路线规划（Dijkstra）、网络路由协议 (OSPF)。
    • 真实系统：Google Maps 利用图算法计算驾车、步行时间。
  • 连通性与网络流：
    • 经典问题：社交网络好友推荐（基于共同邻居）、网页爬虫去重。
    • 真实系统：Redis 的 Geo 模块底层使用 跳表 (ZSET) 和 Geohash 处理地理位置图查询。
  • 依赖与调度：
    • 经典问题：课程表安排（拓扑排序检测环）、Makefile 构建依赖。
    • 真实系统：Airflow / DolphinScheduler 使用 DAG (有向无环图) 编排任务流。
  • 内存布局 (微机原理视角)：
    • 邻接矩阵常以二维数组连续存储在内存中，便于 CPU 缓存预取 (空间局部性好)。
    • 邻接表是指针/引用跳转结构，内存碎片化，但节省稀疏图的存储空间。