万物皆可连 —— 图与图算法

如果说树是层级关系的表达，那图就是万事万物之间复杂关系的终极表达。社交网络、地铁线路、互联网——所有”多对多”的连接，都是图。

📋 开篇自测：你已经知道多少？

1. 微信好友关系和微博关注关系，哪个适合用”无向图”表示，哪个适合用”有向图”？
2. 导航软件是怎么在几千万条道路中瞬间算出最短路线的？
3. BFS和DFS的区别是什么？它们各自适合解决什么类型的问题？

---

一、什么是图——最自由的数据结构

前面学过的数据结构：

• 数组和链表：每个元素最多连一个前驱和一个后继
• 树：每个节点最多一个父节点，可以有多个子节点
• 图：任何节点之间都可以有连接，没有任何限制

图由两个部分组成：

• 顶点（Vertex）： 也叫节点，代表事物本身
• 边（Edge）： 代表事物之间的关系

社交网络：
  Alice --- Bob
    |      / |
    |     /  |
  Carol--/  Dave

图的分类

无向图 vs 有向图：

• 无向图：边没有方向。比如微信好友——你加了对方，对方也加了你。
• 有向图：边有方向。比如微博关注——你关注了明星，明星不一定关注你。

加权图 vs 无权图：

• 加权图：每条边有一个权值。比如城市之间的距离、路段的通行时间。
• 无权图：边没有权值，只表示”有连接”或”无连接”。

# 图的两种常见存储方式

# 方式1：邻接表——用字典存储每个节点的邻居
graph_list = {
    'Alice': ['Bob', 'Carol'],
    'Bob': ['Alice', 'Carol', 'Dave'],
    'Carol': ['Alice', 'Bob'],
    'Dave': ['Bob']
}

# 方式2：邻接矩阵——用二维数组表示连接关系
# 0表示不连通，1表示连通
#         Alice Bob Carol Dave
matrix = [[0,    1,   1,    0],   # Alice
           [1,    0,   1,    1],   # Bob
           [1,    1,   0,    0],   # Carol
           [0,    1,   0,    0]]   # Dave

邻接表 vs 邻接矩阵

特性	邻接表	邻接矩阵
空间复杂度	O(V + E)	O(V²)
查询两点是否相连	O(度)	O(1)
遍历某点的所有邻居	O(度)	O(V)
适合场景	稀疏图（边少）	稠密图（边多）

现实中大多数图是稀疏的（比如社交网络，每个人平均只有几百个好友，而不是和所有人都是好友），所以邻接表更常用。

---

二、广度优先搜索（BFS）——像水波一样扩散

思路

BFS从起点出发，先访问所有距离为1的节点，再访问所有距离为2的节点……就像往水里扔一颗石子，水波一圈一圈向外扩散。

BFS使用队列来实现：把起点放入队列，然后不断从队头取出节点、把它未访问过的邻居放入队尾。

from collections import deque

def bfs(graph, start):
    """广度优先搜索"""
    visited = set()
    queue = deque([start])
    visited.add(start)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print(bfs(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E', 'F']

BFS的经典应用：最短路径（无权图）

BFS天生就能找到无权图中的最短路径——因为它按”层”扩散，第一次到达某个节点的路径一定是最短的。

def shortest_path_bfs(graph, start, end):
    """用BFS找无权图的最短路径"""
    visited = {start}
    queue = deque([(start, [start])])  # (当前节点, 路径)

    while queue:
        node, path = queue.popleft()
        if node == end:
            return path
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    return None  # 不可达

print(shortest_path_bfs(graph, 'A', 'F'))  # ['A', 'C', 'F']

BFS的另一个应用：层序遍历

你在第5章已经见过了——二叉树的层序遍历就是BFS在树上的应用。

🤔 想一想 社交网络中的”你可能认识的人”功能，本质上就是BFS。找到你的朋友的朋友（2跳之内），过滤掉你已经认识的人，就得到了推荐列表。

---

三、深度优先搜索（DFS）——一条路走到黑

思路

DFS从起点出发，沿着一条路一直走到底，走不动了再退回来换条路。就像你在迷宫里探路——选一个方向一直走，碰壁了就原路返回到上一个岔路口，换个方向继续。

DFS可以用递归或者栈来实现。

def dfs_recursive(graph, start, visited=None):
    """深度优先搜索（递归版）"""
    if visited is None:
        visited = set()
    visited.add(start)
    order = [start]
    for neighbor in graph[start]:
        if neighbor not in visited:
            order.extend(dfs_recursive(graph, neighbor, visited))
    return order

def dfs_iterative(graph, start):
    """深度优先搜索（迭代版，用栈）"""
    visited = set()
    stack = [start]
    order = []

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            order.append(node)
            # 注意：为了让遍历顺序和递归版一致，这里反向入栈
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    return order

print(dfs_recursive(graph, 'A'))   # ['A', 'B', 'D', 'E', 'F', 'C']
print(dfs_iterative(graph, 'A'))   # ['A', 'B', 'D', 'E', 'F', 'C']

BFS vs DFS

特性	BFS	DFS
数据结构	队列	栈/递归
搜索顺序	层层扩散	一条路走到底
最短路径（无权图）	能找到	不一定
空间复杂度	O(V)（最宽层）	O(V)（最深路径）
适合场景	最短路径、层级关系	路径搜索、拓扑排序、连通分量

一个直观的比喻：

• BFS像是高空航拍： 先看到整个大局，逐层深入细节
• DFS像是深入探洞： 一条隧道走到底，然后换一条

---

四、Dijkstra算法——加权图的最短路径

在无权图中，BFS就能找到最短路径。但如果边有权重呢？比如地图上每条路的距离不同。

Dijkstra（迪杰斯特拉）算法是解决加权图（权值非负）最短路径的经典算法。

核心思想：维护一个”已确定最短距离的节点集合”，每次从未确定的节点中选距离最近的一个，更新它的邻居的距离。

这就像你从家出发，先标记能直达的最近地点，然后从这个最近地点出发，看看能不能通过它更快地到达其他地点。

import heapq

def dijkstra(graph, start):
    """
    Dijkstra最短路径算法
    graph: {节点: [(邻居, 权重), ...]}
    返回: {节点: 最短距离}
    """
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    predecessors = {node: None for node in graph}
    pq = [(0, start)]  # (距离, 节点)

    while pq:
        current_dist, current_node = heapq.heappop(pq)
        if current_dist > distances[current_node]:
            continue  # 已经找到更短路径了，跳过

        for neighbor, weight in graph[current_node]:
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                predecessors[neighbor] = current_node
                heapq.heappush(pq, (distance, neighbor))

    return distances, predecessors

def get_path(predecessors, start, end):
    """从前驱字典中还原路径"""
    path = []
    node = end
    while node is not None:
        path.append(node)
        node = predecessors[node]
    return path[::-1]

# 城市之间的距离
city_graph = {
    '北京': [('天津', 120), ('石家庄', 280)],
    '天津': [('北京', 120), ('济南', 300)],
    '石家庄': [('北京', 280), ('郑州', 420), ('济南', 350)],
    '济南': [('天津', 300), ('石家庄', 350), ('南京', 600)],
    '郑州': [('石家庄', 420), ('南京', 580)],
    '南京': [('济南', 600), ('郑州', 580)]
}

distances, predecessors = dijkstra(city_graph, '北京')
print("北京到各城市最短距离：")
for city, dist in distances.items():
    path = get_path(predecessors, '北京', city)
    print(f"  {city}: {dist}km, 路线: {' -> '.join(path)}")

时间复杂度： 使用二叉堆时为 O((V + E) log V)，使用斐波那契堆可优化到 O(E + V log V)

🤔 想一想 导航软件给你规划路线时，不仅考虑距离，还考虑路况（拥堵程度）。如果把通行时间作为边的权重，Dijkstra算法就能找到最快的路线。但如果路况是实时变化的呢？这给算法带来了什么挑战？

---

五、图的高级应用

拓扑排序——先修课程问题

有些任务之间存在依赖关系：学”数据结构”之前必须先学”编程基础”。拓扑排序就是在满足所有依赖关系的前提下，找到一个合法的执行顺序。

def topological_sort(graph):
    """
    拓扑排序（基于入度的BFS方法，又叫Kahn算法）
    graph: {节点: [依赖该节点的节点列表]}
    """
    # 计算每个节点的入度
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] = in_degree.get(neighbor, 0) + 1

    # 入度为0的节点入队（没有前置依赖）
    queue = deque([node for node in in_degree if in_degree[node] == 0])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(result) != len(graph):
        raise ValueError("存在循环依赖！")
    return result

# 课程依赖关系
courses = {
    '编程基础': ['数据结构', 'Web开发'],
    '数据结构': ['算法设计', '数据库'],
    '算法设计': ['机器学习'],
    'Web开发': ['全栈开发'],
    '数据库': ['全栈开发'],
    '机器学习': [],
    '全栈开发': []
}

print(topological_sort(courses))
# 可能输出：['编程基础', '数据结构', 'Web开发', '算法设计', '数据库', '机器学习', '全栈开发']

连通分量——社交圈子检测

在社交网络中，找出所有互相连通的”圈子”：

def find_connected_components(graph):
    """找到图中所有连通分量"""
    visited = set()
    components = []

    for node in graph:
        if node not in visited:
            # 用BFS找到这个连通分量的所有节点
            component = []
            queue = deque([node])
            visited.add(node)
            while queue:
                current = queue.popleft()
                component.append(current)
                for neighbor in graph[current]:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append(neighbor)
            components.append(component)

    return components

# 有两个不连通的社交圈
social = {
    '张三': ['李四', '王五'],
    '李四': ['张三'],
    '王五': ['张三'],
    '赵六': ['孙七'],
    '孙七': ['赵六']
}

groups = find_connected_components(social)
for i, group in enumerate(groups):
    print(f"圈子{i + 1}: {group}")
# 圈子1: ['张三', '李四', '王五']
# 圈子2: ['赵六', '孙七']

检测有向图中的环

def has_cycle(graph):
    """检测有向图中是否存在环"""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}

    def dfs(node):
        color[node] = GRAY  # 正在访问
        for neighbor in graph.get(node, []):
            if color.get(neighbor, WHITE) == GRAY:
                return True  # 发现环
            if color.get(neighbor, WHITE) == WHITE:
                if dfs(neighbor):
                    return True
        color[node] = BLACK  # 访问完毕
        return False

    for node in graph:
        if color[node] == WHITE:
            if dfs(node):
                return True
    return False

# 有环的图
cyclic = {'A': ['B'], 'B': ['C'], 'C': ['A']}
print(has_cycle(cyclic))  # True

# 无环的图
acyclic = {'A': ['B'], 'B': ['C'], 'C': []}
print(has_cycle(acyclic))  # False

延伸：最小生成树

除了最短路径，图算法中还有一类重要问题：最小生成树（Minimum Spanning Tree，MST）——用最小的总边权把所有节点连通起来，不形成环。典型场景包括网络布线（用最少的光缆把所有城市连起来）和聚类分析。

两种经典算法：

• Kruskal算法： 把所有边按权重从小到大排序，依次加入，用并查集检测是否成环。时间复杂度O(E log E)。
• Prim算法： 从一个节点出发，每次选择连接已访问和未访问节点的最小权边，类似Dijkstra的思路。用堆优化后时间复杂度O(E log V)。

这两个算法在第13章学习并查集后会更容易理解——Kruskal算法正是并查集的经典应用场景。

⚠️ 常见误区

• 误区1：“Dijkstra适用于所有图” —— Dijkstra要求所有边的权值非负。如果有负权边，需要用Bellman-Ford算法。
• 误区2：“BFS一定比DFS好” —— 取决于问题。找最短路径用BFS，检测环用DFS，找所有路径用DFS。没有哪个绝对更好。
• 误区3：“图算法很难，实际用不到” —— 社交网络推荐、导航规划、任务调度、包管理（pip install的依赖解析）、网络路由……到处都是图算法的应用。

---

📝 掌握度自测

1. 概念题： 什么情况下用邻接表存图比邻接矩阵好？什么情况下反过来？
2. 手算题： 用Dijkstra算法计算下图中A到E的最短路径：A-B(4), A-C(2), B-D(3), C-B(1), C-D(5), D-E(1)。
3. 编码题： 实现一个函数，判断一个无向图是否是”二部图”（节点可以分成两组，组内没有边，所有边都连接两组之间的节点）。
4. 分析题： 如果一个社交网络有1亿用户、50亿条好友关系，用邻接表存储大约需要多少内存？
5. 设计题： 你要设计一个地铁导航系统，支持查询任意两站之间的最少换乘次数。你会怎么建图？用什么算法？

💡 自我评估

• 全部答对：图算法已经难不倒你了，可以挑战更高级的算法，如最小生成树、网络流。
• 答对3-4题：掌握扎实，Dijkstra的细节可以再多练习。
• 答对1-2题：回到BFS和DFS的代码上，用纸笔模拟每一步的执行过程。
• 全部答错：图是最复杂的数据结构，建议先彻底理解BFS和DFS再学其他图算法。

---

图让我们看到了”节点之间的连接关系”，而连接关系不止存在于社交网络和地铁线路中——文本也是一种序列结构，字符与字符之间的排列隐藏着可以被高效利用的规律。下一章，我们从图的世界转向文本的世界，看看如何在海量文字中快速找到目标——字符串匹配算法。