第10章图 (Graphs)

一、导读

1.1 本章学习目标

完成本章学习后，你将能够：

理解图的基本概念：顶点、边、度、路径、连通性

掌握图的表示方法：邻接矩阵、邻接表

熟练运用图的遍历算法：深度优先搜索（DFS）和广度优先搜索（BFS）

理解最短路径算法：Dijkstra算法和Bellman-Ford算法

掌握最小生成树算法：Prim算法和Kruskal算法

理解欧拉回路和哈密顿回路的区别

掌握图的着色问题及其实际应用

能够将实际问题建模为图问题并选择合适的算法求解

理解网络流问题的基本概念和Ford-Fulkerson算法

掌握二分图匹配的原理和应用

1.2 为什么本章如此重要

图是计算机科学中最通用的数据结构之一，能够建模各种现实世界的问题。

在网络中：互联网、社交网络、交通网络都可以用图表示。路由算法本质上是图的最短路径问题。CDN节点的选择涉及最小生成树和网络流优化。

在编译器中：控制流图、数据依赖图、调用图都是图的应用。寄存器分配是图着色问题。指令调度涉及DAG的最长路径计算。

在操作系统中：资源分配图检测死锁；进程调度涉及拓扑排序。虚拟内存的页面置换可以建模为图问题。

在数据库中：实体关系图（ER图）设计数据库模式；图数据库直接存储图结构。查询优化中的连接顺序选择涉及图的遍历。

在人工智能中：状态空间搜索是图遍历；知识图谱是带标签的图。强化学习中的马尔可夫决策过程是有向图。

在生物信息学中：蛋白质相互作用网络、基因调控网络都是图。序列比对可以建模为图的最长公共子序列问题。

在计算机视觉中：图像分割使用图割算法；立体匹配涉及能量最小化，可以转化为图问题。

在社会科学中：社交网络分析使用中心性度量、社区发现等图算法。影响力最大化是组合优化问题。

1.3 核心问题引导

在学习本章之前，请思考以下问题：

图和树有什么区别？树是特殊的图吗？

为什么社交网络中"六度分隔"理论可能成立？

DFS和BFS各适用于什么场景？

Dijkstra算法为什么不能处理负权边？

什么是NP完全问题？图着色为什么难？

欧拉回路和哈密顿回路哪个更容易找到？

如何检测图中是否有环？

图的稀疏性和稠密性如何影响算法选择？

最大流最小割定理的直观含义是什么？

什么是小世界网络？它有什么特性？

二、核心概念详解

10.1 图的基本概念

定义

图 G = (V, E) 由两个集合组成：

V：顶点（节点）的有限集合
E：边的集合，每条边连接两个顶点

无向图：边是无序对 {u, v}，表示双向连接。

有向图：边是有序对 (u, v)，表示从u到v的单向连接。

加权图：每条边有一个权重（成本、距离、容量等）。

多重图：允许两个顶点之间有多条边（平行边）。

伪图：允许自环（边连接顶点到自身）。

简单图：没有自环和平行边的图。

基本术语

度（Degree）：与顶点相连的边数。

无向图：deg(v) = 与v相连的边数
有向图：入度 in-deg(v) 和出度 out-deg(v)

握手定理：在无向图中，所有顶点的度之和等于边数的两倍。

$$\sum_{v \in V} \deg(v) = 2|E|$$

证明：每条边贡献2到度数总和（每个端点贡献1）。∎

推论：度为奇数的顶点个数必为偶数。

证明：设V_odd是奇度顶点集合，V_even是偶度顶点集合。

Σ deg(v) = Σ_{v∈V_odd} deg(v) + Σ_{v∈V_even} deg(v) = 2|E|

右边是偶数，Σ_{v∈V_even} deg(v) 是偶数，所以 Σ_{v∈V_odd} deg(v) 必须是偶数。由于每个奇度顶点的度是奇数，奇数个奇数相加是奇数，偶数个奇数相加是偶数。因此 |V_odd| 必须是偶数。∎

路径（Path）：顶点序列 v₀, v₁, ..., vₖ，使得每对相邻顶点之间有边。

路径长度：路径上的边数（无权图）或权重之和（加权图）。

简单路径：不重复顶点的路径。

环（Cycle）：起点和终点相同的路径（长度至少为3）。

简单环：除起点和终点外不重复顶点的环。

连通图：任意两个顶点之间都存在路径。

连通分量：极大连通子图。

强连通（有向图）：任意两个顶点之间都存在双向路径。

弱连通（有向图）：忽略方向后是连通的。

子图：H是G的子图，如果 V(H) ⊆ V(G) 且 E(H) ⊆ E(G)。

生成子图：包含G的所有顶点的子图。

诱导子图：由顶点子集S诱导的子图包含S中所有顶点以及G中两端都在S中的所有边。

10.2 特殊图类

完全图

完全图 Kₙ 有n个顶点，每对顶点之间都有一条边。

边数：|E| = C(n,2) = n(n-1)/2

二分图

二分图的顶点可以分为两个集合X和Y，使得每条边连接不同集合的顶点。

判定：图是二分图当且仅当不含奇数长度的环。

算法：使用BFS进行二染色。

正则图

k-正则图：每个顶点的度都是k。

示例：完全图Kₙ是(n-1)-正则图；立方体图是3-正则图。

平面图

平面图：可以画在平面上使得边不相交（除端点外）。

欧拉公式：对于连通平面图，V - E + F = 2，其中F是面的数量。

推论：简单平面图的边数 E ≤ 3V - 6（当V ≥ 3时）。

四色定理：任何平面图的色数不超过4。

树

树：连通无环图。等价于：

连通且有 V-1 条边
无环且有 V-1 条边
任意两点之间有且仅有一条路径

10.3 图的表示

邻接矩阵

n×n的矩阵A，其中 A[i][j] = 1（或权重）如果存在边(i,j)，否则为0。

优点：

查询两点间是否有边：O(1)
适合稠密图
矩阵运算可用于图分析（如计算路径数）

缺点：

空间复杂度 O(V²)
遍历邻居需要 O(V)
对稀疏图浪费空间

邻接表

每个顶点维护一个邻居列表（或链表）。

优点：

空间复杂度 O(V + E)
遍历邻居高效
适合稀疏图

缺点：

查询两点间是否有边：O(degree)
需要额外数据结构处理权重

边列表

简单地存储所有边的列表。

优点：

简单，节省空间
适合Kruskal等需要遍历所有边的算法

缺点：

查询效率低
遍历邻居需要扫描整个列表

选择建议

稠密图（E ≈ V²）：邻接矩阵
稀疏图（E ≈ V）：邻接表
只需要遍历边：边列表

10.4 图的遍历

深度优先搜索（DFS）

思想：尽可能深地探索图，回溯时探索其他分支。

算法（递归版本）：

python

def dfs(graph, vertex, visited):
    visited.add(vertex)
    process(vertex)
    for neighbor in graph.neighbors(vertex):
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

迭代版本（使用栈）：

python

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        vertex = stack.pop()
        if vertex in visited:
            continue
        visited.add(vertex)
        process(vertex)
        for neighbor in graph.neighbors(vertex):
            if neighbor not in visited:
                stack.append(neighbor)

时间复杂度：O(V + E)

应用：

检测环
拓扑排序
连通分量
迷宫求解
双连通分量
强连通分量（Kosaraju算法）

DFS树：DFS过程中形成的树结构。边可以分为：

树边：DFS树中的边
回边：指向祖先的边（检测环的关键）
前向边：指向后代的非树边
横叉边：连接不同子树的边

广度优先搜索（BFS）

思想：逐层探索图，先访问距离源点近的顶点。

算法：

python

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    distance = {start: 0}
    
    while queue:
        vertex = queue.popleft()
        process(vertex)
        for neighbor in graph.neighbors(vertex):
            if neighbor not in visited:
                visited.add(neighbor)
                distance[neighbor] = distance[vertex] + 1
                queue.append(neighbor)
    
    return distance

时间复杂度：O(V + E)

应用：

无权图的最短路径
社交网络中的好友推荐（共同好友）
网页爬虫（按层次抓取）
广播协议
二分图判定

DFS vs BFS

特性	DFS	BFS
数据结构	栈（递归）	队列
空间	O(V)	O(V)
最短路径	不保证（有权图）	保证（无权图）
内存使用	可能更少（深度优先）	可能更多（需要存储整层）
适用场景	深度探索、环检测、拓扑排序	最短路径、层次遍历、二分图判定
完备性	可能在无限图中不终止	在有限图中保证找到解

10.5 最短路径

Dijkstra算法

前提：所有边权非负。

思想：贪心策略，每次选择距离源点最近的未处理顶点，更新其邻居的距离。

算法：

python

import heapq

def dijkstra(graph, source):
    dist = {v: float('inf') for v in graph.vertices}
    dist[source] = 0
    pq = [(0, source)]  # (distance, vertex)
    prev = {v: None for v in graph.vertices}
    
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, weight in graph.neighbors(u):
            new_dist = dist[u] + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                prev[v] = u
                heapq.heappush(pq, (new_dist, v))
    
    return dist, prev

时间复杂度：O((V + E) log V)（使用二叉堆）

正确性证明思路：

维护不变式：每次从优先队列中弹出的顶点u，其dist[u]已经是最终的最短距离
证明：假设u是第一个违反不变式的顶点，则存在更短的路径通过某个未处理的顶点v。但dist[v] ≥ dist[u]（因为u先被弹出），矛盾。

为什么不能处理负权边：Dijkstra基于贪心策略，一旦确定某顶点的距离就不再更新。但负权边可能导致后续发现更短的路径。

Bellman-Ford算法

优点：可以处理负权边，检测负权环。

算法：

python

def bellman_ford(graph, source):
    dist = {v: float('inf') for v in graph.vertices}
    dist[source] = 0
    
    # 松弛所有边 V-1 次
    for _ in range(len(graph.vertices) - 1):
        for u, v, w in graph.edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    
    # 检测负权环
    for u, v, w in graph.edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None  # 存在负权环
    
    return dist

时间复杂度：O(VE)

原理：最短路径最多包含V-1条边（否则有环）。每次迭代至少确定一条边的最短距离。

负权环检测：如果第V次迭代还能松弛，说明存在负权环。

Floyd-Warshall算法

目的：计算所有点对之间的最短路径。

算法：

python

def floyd_warshall(graph):
    n = len(graph.vertices)
    dist = [[float('inf')] * n for _ in range(n)]
    
    # 初始化
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in graph.edges:
        dist[u][v] = w
    
    # 动态规划
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

时间复杂度：O(V³)

原理：考虑是否可以通过中间节点k来缩短i到j的距离。

10.6 最小生成树

Prim算法

思想：从任意顶点开始，逐步扩展树，每次添加代价最小的边。

算法：

python

import heapq

def prim_mst(graph, start):
    mst_edges = []
    visited = {start}
    edges = [(w, start, v) for v, w in graph.neighbors(start)]
    heapq.heapify(edges)
    
    total_weight = 0
    
    while edges and len(visited) < len(graph.vertices):
        w, u, v = heapq.heappop(edges)
        if v in visited:
            continue
        visited.add(v)
        mst_edges.append((u, v, w))
        total_weight += w
        
        for next_v, next_w in graph.neighbors(v):
            if next_v not in visited:
                heapq.heappush(edges, (next_w, v, next_v))
    
    return mst_edges, total_weight

时间复杂度：O(E log V)

Kruskal算法

思想：按权重从小到大考虑边，如果不形成环则加入。

算法：

python

def kruskal_mst(graph):
    parent = {v: v for v in graph.vertices}
    rank = {v: 0 for v in graph.vertices}
    
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # 路径压缩
            x = parent[x]
        return x
    
    def union(x, y):
        px, py = find(x), find(y)
        if px == py:
            return False
        if rank[px] < rank[py]:
            px, py = py, px
        parent[py] = px
        if rank[px] == rank[py]:
            rank[px] += 1
        return True
    
    edges = sorted(graph.all_edges(), key=lambda e: e[2])
    mst_edges = []
    total_weight = 0
    
    for u, v, w in edges:
        if union(u, v):
            mst_edges.append((u, v, w))
            total_weight += w
    
    return mst_edges, total_weight

时间复杂度：O(E log E) = O(E log V)

正确性：基于贪心选择性质和切割性质。

切割性质：对于任意切割，跨越切割的最小权重边一定在某个MST中。

10.7 特殊图问题

欧拉回路

欧拉回路：经过每条边恰好一次的回路。

定理：连通无向图存在欧拉回路当且仅当所有顶点的度都是偶数。

证明思路：

必要性：每次进入一个顶点就要离开，所以度必须是偶数。
充分性：从任意顶点出发，沿着未访问的边走，由于度是偶数，最终会回到起点形成一个环。如果还有未访问的边，从环上某个有未访问边的顶点出发，形成另一个环，合并到原环中。重复直到所有边都被访问。∎

欧拉路径：经过每条边恰好一次的路径（不一定是回路）。

定理：连通无向图存在欧拉路径当且仅当恰有0个或2个顶点的度是奇数。

Hierholzer算法：用于寻找欧拉回路/路径。

哈密顿回路

哈密顿回路：经过每个顶点恰好一次的回路。

判定：NP完全问题，没有已知的多项式时间算法。

充分条件（Dirac定理）：如果n≥3且每个顶点的度至少为n/2，则存在哈密顿回路。

必要条件：图必须连通，且不能有割点（对于n≥3）。

应用：旅行商问题（TSP）是加权版本的哈密顿回路问题。

图着色

k-着色：用k种颜色给顶点着色，使得相邻顶点颜色不同。

色数 χ(G)：使G可着色的最小颜色数。

四色定理：任何平面图的色数不超过4。

应用：

寄存器分配：冲突图的着色
时间表安排：课程/考试的着色
频率分配：无线电频道的着色

贪心着色算法：

python

def greedy_coloring(graph):
    colors = {}
    for v in graph.vertices:
        used_colors = {colors[u] for u in graph.neighbors(v) if u in colors}
        color = 0
        while color in used_colors:
            color += 1
        colors[v] = color
    return colors

近似：贪心算法最多使用 Δ+1 种颜色，其中Δ是最大度。

判定k-着色：NP完全问题（k≥3）。

二分图匹配

匹配：边的子集，没有两条边共享顶点。

最大匹配：边数最多的匹配。

完美匹配：覆盖所有顶点的匹配。

匈牙利算法：用于求二分图的最大匹配。

Hall定理：二分图G=(X,Y,E)存在覆盖X的匹配当且仅当对所有 S ⊆ X，|N(S)| ≥ |S|，其中N(S)是S的邻居集合。

应用：任务分配、婚姻问题、稳定匹配。

10.8 网络流

流网络：有向图，每条边有容量，有源点s和汇点t。

流：给每条边分配流量，满足：

容量限制：0 ≤ f(u,v) ≤ c(u,v)

流量守恒：对所有 v ≠ s,t，流入 = 流出

最大流问题：找到从s到t的最大流。

Ford-Fulkerson算法：

找到增广路径（从s到t的路径，所有边都有剩余容量）

沿增广路径增加流量

重复直到没有增广路径

最大流最小割定理：最大流等于最小割的容量。

割：将顶点分为包含s的集合S和包含t的集合T，割的容量是从S到T的边的容量之和。

应用：

项目选择
图像分割
棒球淘汰问题
二分图匹配（可以转化为最大流）

三、程序员的视角

3.1 在计算机科学中的应用

网络路由

OSPF协议使用Dijkstra算法
BGP协议考虑路径策略
SDN中的流量工程使用网络流优化

社交网络

好友推荐：共同好友数量、Jaccard系数
影响力分析：PageRank算法、中心性度量
社区发现：Louvain算法、谱聚类

编译优化

控制流图：基本块之间的跳转
数据流分析：变量定义和使用
寄存器分配：图着色
指令调度：DAG的最长路径

3.2 常见陷阱与误区

负权边

Dijkstra算法不能处理负权边，应使用Bellman-Ford。

图的表示选择

稠密图用邻接矩阵，稀疏图用邻接表。错误的选择会导致性能问题。

无限循环

确保DFS/BFS正确标记已访问节点。在有环图中尤其重要。

整数溢出

最短路径算法中，距离累加可能溢出。使用适当的数据类型。

3.3 与其他层级的联系

硬件层：电路网表是图；PCB布线是图问题
操作系统层：进程通信图；文件系统的目录图
网络层：拓扑结构；路由表
应用层：推荐系统；搜索引擎的PageRank

四、代码实战

10.1 图的基本实现

python

"""
图的基本实现和遍历算法
"""

from collections import defaultdict, deque


class Graph:
    """无向图类"""
    
    def __init__(self):
        self.adjacency_list = defaultdict(list)
        self.vertices = set()
    
    def add_vertex(self, v):
        self.vertices.add(v)
    
    def add_edge(self, u, v, weight=1):
        self.vertices.add(u)
        self.vertices.add(v)
        self.adjacency_list[u].append((v, weight))
        self.adjacency_list[v].append((u, weight))
    
    def neighbors(self, v):
        return self.adjacency_list.get(v, [])
    
    def dfs(self, start):
        """深度优先搜索"""
        visited = set()
        order = []
        
        def dfs_recursive(v):
            visited.add(v)
            order.append(v)
            for neighbor, _ in self.neighbors(v):
                if neighbor not in visited:
                    dfs_recursive(neighbor)
        
        dfs_recursive(start)
        return order
    
    def bfs(self, start):
        """广度优先搜索"""
        visited = {start}
        queue = deque([start])
        order = []
        
        while queue:
            v = queue.popleft()
            order.append(v)
            for neighbor, _ in self.neighbors(v):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        
        return order
    
    def connected_components(self):
        """找出所有连通分量"""
        visited = set()
        components = []
        
        for v in self.vertices:
            if v not in visited:
                component = []
                queue = deque([v])
                visited.add(v)
                
                while queue:
                    node = queue.popleft()
                    component.append(node)
                    for neighbor, _ in self.neighbors(node):
                        if neighbor not in visited:
                            visited.add(neighbor)
                            queue.append(neighbor)
                
                components.append(component)
        
        return components
    
    def has_cycle(self):
        """检测是否有环"""
        visited = set()
        
        def dfs_cycle(v, parent):
            visited.add(v)
            for neighbor, _ in self.neighbors(v):
                if neighbor not in visited:
                    if dfs_cycle(neighbor, v):
                        return True
                elif neighbor != parent:
                    return True
            return False
        
        for v in self.vertices:
            if v not in visited:
                if dfs_cycle(v, None):
                    return True
        return False


def demonstrate_graph_traversal():
    """演示图遍历"""
    
    g = Graph()
    edges = [
        ('A', 'B'), ('A', 'C'), ('B', 'D'),
        ('B', 'E'), ('C', 'F'), ('D', 'E'),
        ('E', 'F')
    ]
    
    for u, v in edges:
        g.add_edge(u, v)
    
    print("=== 图遍历 ===")
    print(f"顶点: {sorted(g.vertices)}")
    print(f"DFS从A开始: {g.dfs('A')}")
    print(f"BFS从A开始: {g.bfs('A')}")
    print(f"连通分量: {g.connected_components()}")
    print(f"有环: {g.has_cycle()}")


if __name__ == "__main__":
    demonstrate_graph_traversal()

10.2 最短路径算法

python

"""
最短路径算法实现
"""

import heapq


def dijkstra(graph, source):
    """
    Dijkstra最短路径算法
    
    参数:
        graph: 邻接表表示的图 {vertex: [(neighbor, weight), ...]}
        source: 源顶点
    
    返回:
        dist: 到各顶点的最短距离字典
        prev: 前驱节点字典（用于重构路径）
    """
    dist = {v: float('inf') for v in graph}
    prev = {v: None for v in graph}
    dist[source] = 0
    
    pq = [(0, source)]
    
    while pq:
        d, u = heapq.heappop(pq)
        
        if d > dist[u]:
            continue
        
        for v, w in graph[u]:
            new_dist = dist[u] + w
            if new_dist < dist[v]:
                dist[v] = new_dist
                prev[v] = u
                heapq.heappush(pq, (new_dist, v))
    
    return dist, prev


def reconstruct_path(prev, target):
    """从前驱字典重构路径"""
    path = []
    current = target
    while current is not None:
        path.append(current)
        current = prev[current]
    path.reverse()
    return path


def bellman_ford(vertices, edges, source):
    """
    Bellman-Ford算法
    
    参数:
        vertices: 顶点列表
        edges: 边列表 [(u, v, w), ...]
        source: 源顶点
    
    返回:
        dist: 最短距离字典，或None（如果有负权环）
    """
    dist = {v: float('inf') for v in vertices}
    dist[source] = 0
    
    for _ in range(len(vertices) - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    
    # 检测负权环
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None
    
    return dist


def demonstrate_shortest_path():
    """演示最短路径算法"""
    
    # 示例图
    graph = {
        'A': [('B', 1), ('C', 4)],
        'B': [('A', 1), ('C', 2), ('D', 5)],
        'C': [('A', 4), ('B', 2), ('D', 1)],
        'D': [('B', 5), ('C', 1)]
    }
    
    print("=== Dijkstra最短路径 ===")
    dist, prev = dijkstra(graph, 'A')
    
    print("从A到各顶点的最短距离:")
    for v in sorted(dist.keys()):
        path = reconstruct_path(prev, v)
        print(f"  A -> {v}: 距离={dist[v]}, 路径={' -> '.join(path)}")
    
    # Bellman-Ford示例
    print("\n=== Bellman-Ford ===")
    vertices = ['A', 'B', 'C', 'D']
    edges = [
        ('A', 'B', 1), ('A', 'C', 4),
        ('B', 'C', 2), ('B', 'D', 5),
        ('C', 'D', 1)
    ]
    
    dist = bellman_ford(vertices, edges, 'A')
    if dist:
        print("最短距离:", dist)
    else:
        print("存在负权环")


if __name__ == "__main__":
    demonstrate_shortest_path()

五、深入思考

5.1 历史背景

图论起源于1736年莱昂哈德·欧拉解决的柯尼斯堡七桥问题。威廉·罗文·汉密尔顿研究了哈密顿回路。艾兹格·迪杰斯特拉提出了最短路径算法（1956）。约瑟夫·克鲁斯卡尔和罗伯特·普里姆独立发现了最小生成树算法。Lester Ford和Delbert Fulkerson发展了网络流理论。

蒂姆·伯纳斯-李发明的万维网本质上是一个巨大的有向图。拉里·佩奇和谢尔盖·布林的PageRank算法改变了搜索引擎。

5.2 前沿方向

图神经网络（GNN）：深度学习在图数据上的应用
大规模图处理：分布式图计算框架（如Pregel、GraphX）
动态图算法：处理不断变化的图
量子图算法：利用量子计算机加速图问题
图数据库：Neo4j等原生图存储系统
复杂网络：小世界网络、无标度网络的分析

5.3 延伸阅读

《Introduction to Graph Theory》by Douglas B. West
《Graph Algorithms》by Mark Needham and Amy Hodler
《Networks, Crowds, and Markets》by Easley and Kleinberg
《Algorithms》by Sedgewick and Wayne（第4部分：图算法）

六、实验笔记

实验1：图算法可视化工具

目标：可视化图算法的执行过程。

任务：

实现图的交互式绘制

逐步展示DFS/BFS的探索过程

动画演示Dijkstra算法

比较不同算法的效果

支持自定义图输入

提交物：可运行的程序、可视化输出、用户手册。

实验2：社交网络分析

目标：应用图算法分析社交网络。

任务：

构建社交网络图

计算节点的度中心性、介数中心性、接近中心性

发现社区结构

模拟信息传播

识别关键节点

提交物：源代码、分析报告、可视化结果。

七、本章小结

本章介绍了图论的基础。图由顶点和边组成，可以用邻接矩阵或邻接表表示。DFS和BFS是两种基本的图遍历方法，分别适用于深度探索和最短路径查找。

Dijkstra算法和Bellman-Ford算法解决单源最短路径问题。Prim算法和Kruskal算法找到最小生成树。欧拉回路存在条件简单（所有顶点度为偶数），而哈密顿回路判定是NP完全问题。

图着色、二分图匹配、网络流等问题在实际应用中有重要价值。图论是理解网络、优化和社会系统的关键工具。

掌握图的表示和算法选择是解决实际问题的关键。稀疏图用邻接表，稠密图用邻接矩阵。最短路径根据是否有负权边选择Dijkstra或Bellman-Ford。

八、习题

习题1（基础）：对于给定的图，手动执行DFS和BFS，记录访问顺序。

习题2（基础）：证明握手定理。

习题3（中等）：使用Dijkstra算法求下图从A到所有其他顶点的最短路径。

习题4（中等）：证明连通无向图存在欧拉回路当且仅当所有顶点的度都是偶数。

习题5（中等）：实现Kruskal算法并验证其正确性。

习题6（较难）：证明任何树都是二分图。

习题7（较难）：研究PageRank算法的原理并实现简化版本。

习题8（挑战）：证明图着色问题是NP完全的（概述证明思路）。

习题9（挑战）：设计一个算法检测有向图中的所有强连通分量（Kosaraju算法或Tarjan算法）。

习题10（开放）：选择一个实际网络（如交通、社交、互联网），建立图模型并分析其性质。包括：

网络的规模和结构
中心性度量分析
社区发现结果
小世界特性检验

第10章 图 (Graphs)

一、导读

1.1 本章学习目标

1.2 为什么本章如此重要

1.3 核心问题引导

二、核心概念详解

10.1 图的基本概念

定义

基本术语

10.2 特殊图类

完全图

二分图

正则图

平面图

树

10.3 图的表示

邻接矩阵

邻接表

边列表

选择建议

10.4 图的遍历

深度优先搜索（DFS）

广度优先搜索（BFS）

DFS vs BFS

10.5 最短路径

Dijkstra算法

Bellman-Ford算法

Floyd-Warshall算法

10.6 最小生成树

Prim算法

Kruskal算法

10.7 特殊图问题

欧拉回路

哈密顿回路

图着色

二分图匹配

10.8 网络流

三、程序员的视角

3.1 在计算机科学中的应用

网络路由

社交网络

编译优化

3.2 常见陷阱与误区

负权边

图的表示选择

无限循环

整数溢出

3.3 与其他层级的联系

四、代码实战

10.1 图的基本实现

10.2 最短路径算法

五、深入思考

5.1 历史背景

5.2 前沿方向

5.3 延伸阅读

六、实验笔记

实验1：图算法可视化工具

实验2：社交网络分析

七、本章小结

八、习题

第10章图 (Graphs)