# 人工智能之数学基础 离散数学

第二章 图论

---

# 前言

图论是离散数学的核心分支，广泛应用于**社交网络分析、路径规划、编译器优化、知识图谱、推荐系统**等计算机科学领域。本文系统讲解：

- **图的基本概念**（有向图/无向图、权重、度）
- **图的表示方法**（邻接矩阵、邻接表）
- **图的遍历算法**（深度优先搜索 DFS、广度优先搜索 BFS）
- **最短路径算法**（Dijkstra、Floyd-Warshall）
- **配套 Python 代码实现**（从零构建 + NetworkX 对比 + 可视化）

---

# 一、图的基本定义

## 1. 什么是图？

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

- **顶点集（Vertices / Nodes）**：$ V = \{v_1, v_2, \dots, v_n\} $
- **边集（Edges）**：$E \subseteq V \times V $

### 2. 图的类型

| 类型 | 边的性质 | 示例 |
|------|--------|------|
| **无向图** | 边无方向，$ (u,v) = (v,u) $ | 社交好友关系 |
| **有向图（Digraph）** | 边有方向，$(u,v) \ne (v,u) $ | 网页链接、依赖关系 |
| **带权图** | 每条边有权重 $ w(u,v) \in \mathbb{R} $| 路网距离、通信成本 |
| **简单图** | 无自环、无重边 | 大多数算法假设 |
| **完全图** | 任意两点间有边 | $ K_n $) |

## 3. 基本术语

- **度（Degree）**：
  - 无向图：节点连接的边数
  - 有向图：**入度（in-degree）** + **出度（out-degree）**
- **路径（Path）**：顶点序列 $ v_1 \to v_2 \to \dots \to v_k $，边连续
- **环（Cycle）**：起点 = 终点的路径（长度 ≥ 1）
- **连通性**：
  - 无向图：任意两点间有路径 → **连通图**
  - 有向图：任意两点互相可达 → **强连通**

---

# 二、图的表示方法

## 1. 邻接矩阵（Adjacency Matrix）

- **定义**：$ n \times n $矩阵 $ A $，其中
  $$
  A[i][j] =
  \begin{cases}
  1 & \text{若存在边 } (v_i, v_j) \\
  0 & \text{否则}
  \end{cases}
  $$
- **带权图**：$ A[i][j] = w(v_i, v_j) $，无边用 $ \infty $ 表示
- **特点**：
  - 空间复杂度：$ O(n^2) $
  - 查询边：$ O(1) $
  - 适合**稠密图**

## 2. 邻接表（Adjacency List）

- **定义**：数组 + 链表（或字典），每个节点存储其邻居列表
- **Python 表示**：`graph = { 'A': ['B', 'C'], 'B': ['A'], ... }`
- **特点**：
  - 空间复杂度：$ O(n + m) $（$ m $ 为边数）
  - 遍历邻居：$ O(\text{degree}(v)) $
  - 适合**稀疏图**

> ✅ **选择建议**：
> 
> - 节点数少、边多 → 邻接矩阵
> - 节点数多、边少（如社交网络）→ 邻接表

---

# 三、图的遍历算法

## 1. 广度优先搜索（BFS）

- **策略**：逐层扩展，使用**队列（FIFO）**
- **应用**：
  - 最短路径（无权图）
  - 连通分量
  - 二分图检测
- **时间复杂度**：$ O(n + m) $

### 算法步骤：

1. 将起始节点入队，标记已访问
2. 当队列非空：
   - 出队一个节点 $ u $
   - 遍历 $ u $ 的所有未访问邻居 $ v $
   - 标记 $ v $ 已访问，入队

---

## 2. 深度优先搜索（DFS）

- **策略**：一条路走到黑，使用**栈（LIFO）** 或递归
- **应用**：
  - 拓扑排序
  - 强连通分量（Kosaraju）
  - 环检测
- **时间复杂度**：$ O(n + m) $

### 算法步骤（递归版）：

1. 访问当前节点 $ u $，标记已访问
2. 对每个未访问邻居 $ v $：
   - 递归调用 DFS(v)

---

# 四、最短路径算法

## 1. Dijkstra 算法（单源最短路径）

- **适用**：**非负权重**有向/无向图
- **策略**：贪心 + 优先队列（最小堆）
- **时间复杂度**：
  - 普通实现：$ O(n^2) $
  - 堆优化：$ O((n + m) \log n) $

### 算法步骤：

1. 初始化：`dist[source] = 0`，其余为 $ \infty $
2. 将所有节点加入优先队列（按 dist 排序）
3. 当队列非空：
   - 取出 dist 最小的节点 $ u $
   - 对每个邻居 $ v $：
     - 若 `dist[u] + w(u,v) < dist[v]`，更新 `dist[v]`

> ❌ **不能处理负权边**（可用 Bellman-Ford）

---

## 2. Floyd-Warshall 算法（全源最短路径）

- **适用**：任意权重（可含负权，但无负环）
- **策略**：动态规划
- **时间复杂度**：$ O(n^3) $
- **空间复杂度**：$ O(n^2) $

### 核心思想：

$$
\text{dist}[i][j] = \min(\text{dist}[i][j],\ \text{dist}[i][k] + \text{dist}[k][j])
$$

对所有中间节点 $ k $ 进行动态更新。

---

# 五、Python 代码实现

## 1. 导入库

```python
import heapq
from collections import deque, defaultdict
import matplotlib.pyplot as plt
import networkx as nx

# 设置中文字体（可选）
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False
```

---

## 2. 图类实现（邻接表）

```python
class Graph:
    def __init__(self, directed=False):
        self.graph = defaultdict(list)  # 邻接表
        self.directed = directed
        self.weights = {}  # 存储边权重: {(u,v): w}
    
    def add_edge(self, u, v, weight=1):
        self.graph[u].append(v)
        if not self.directed:
            self.graph[v].append(u)
        self.weights[(u, v)] = weight
        if not self.directed:
            self.weights[(v, u)] = weight
    
    def get_neighbors(self, u):
        return self.graph[u]
    
    def get_weight(self, u, v):
        return self.weights.get((u, v), float('inf'))
    
    def vertices(self):
        return list(self.graph.keys())
```

---

## 3. BFS 实现

```python
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.get_neighbors(node):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return order

# 测试
g = Graph()
edges = [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'E')]
for u, v in edges:
    g.add_edge(u, v)

print("BFS 顺序:", bfs(g, 'A'))  # 输出: ['A', 'B', 'C', 'D', 'E']
```

---

## 4. DFS 实现（递归）

```python
def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    order = [start]
    
    for neighbor in graph.get_neighbors(start):
        if neighbor not in visited:
            order.extend(dfs_recursive(graph, neighbor, visited))
    
    return order

print("DFS 顺序:", dfs_recursive(g, 'A'))  # 输出: ['A', 'B', 'D', 'C', 'E']
```

---

## 5. Dijkstra 算法

```python
def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph.vertices()}
    dist[start] = 0
    prev = {node: None for node in graph.vertices()}
    
    # 优先队列: (distance, node)
    pq = [(0, start)]
    
    while pq:
        current_dist, u = heapq.heappop(pq)
        
        # 跳过已处理的更优路径
        if current_dist > dist[u]:
            continue
            
        for v in graph.get_neighbors(u):
            weight = graph.get_weight(u, v)
            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

# 带权图测试
gw = Graph(directed=True)
gw.add_edge('A', 'B', 4)
gw.add_edge('A', 'C', 2)
gw.add_edge('B', 'C', 1)
gw.add_edge('B', 'D', 5)
gw.add_edge('C', 'D', 8)
gw.add_edge('C', 'E', 10)
gw.add_edge('D', 'E', 2)

dist, prev = dijkstra(gw, 'A')
print("Dijkstra 距离:", dist)
# 输出: {'A': 0, 'B': 4, 'C': 2, 'D': 9, 'E': 11}
```

---

## 6. Floyd-Warshall 算法

```python
def floyd_warshall(vertices, get_weight):
    n = len(vertices)
    idx = {v: i for i, v in enumerate(vertices)}
    INF = float('inf')
    
    # 初始化距离矩阵
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for i, u in enumerate(vertices):
        for j, v in enumerate(vertices):
            if i != j:
                w = get_weight(u, v)
                if w != INF:
                    dist[i][j] = 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]
    
    # 转回字典
    result = {}
    for i, u in enumerate(vertices):
        result[u] = {}
        for j, v in enumerate(vertices):
            result[u][v] = dist[i][j]
    return result

# 测试
fw_dist = floyd_warshall(gw.vertices(), gw.get_weight)
print("Floyd-Warshall A→E:", fw_dist['A']['E'])  # 输出: 11
```

---

## 7. 可视化：使用 NetworkX

```python
# 构建 NetworkX 图
G_nx = nx.DiGraph()
for (u, v), w in gw.weights.items():
    G_nx.add_edge(u, v, weight=w)

pos = nx.spring_layout(G_nx)
nx.draw(G_nx, pos, with_labels=True, node_color='lightblue', 
        node_size=1500, font_size=12, arrowsize=20)
labels = nx.get_edge_attributes(G_nx, 'weight')
nx.draw_networkx_edge_labels(G_nx, pos, edge_labels=labels)
plt.title("带权有向图")
plt.show()
```

---

## 8. 与 NetworkX 内置算法对比

```python
# BFS
print("NetworkX BFS:", list(nx.bfs_tree(G_nx, 'A')))

# Dijkstra
nx_dist = nx.single_source_dijkstra_path_length(G_nx, 'A')
print("NetworkX Dijkstra:", nx_dist)

# 验证一致性
assert dist == nx_dist, "结果不一致！"
print("✅ 自实现与 NetworkX 结果一致")
```

---

# 六、应用场景速览

| 算法 | 应用场景 | 示例 |
|------|--------|------|
| **BFS** | 无权最短路径 | 社交网络“六度空间” |
| **DFS** | 拓扑排序 | 课程先修关系、任务调度 |
| **Dijkstra** | GPS 导航 | 高德地图最短路径 |
| **Floyd-Warshall** | 全对最短路径 | 航空网络票价计算 |
| **强连通分量** | 网页聚类 | Google PageRank 预处理 |

---

# 七、总结

| 概念 | 关键点 | 复杂度 |
|------|------|--------|
| **邻接矩阵** | 快速查边，内存大 | $ O(n^2) $ |
| **邻接表** | 节省内存，遍历快 | $ O(n + m) $ |
| **BFS** | 队列，层序遍历 | $ O(n + m) $ |
| **DFS** | 栈/递归，深度优先 | $ O(n + m) $ |
| **Dijkstra** | 贪心，非负权 | $ O((n+m)\log n) $ |
| **Floyd-Warshall** | 动态规划，全源 | $ O(n^3) $ |

> 💡 **工程建议**：
> 
> - 小图（< 1000 节点）：邻接矩阵 + Floyd-Warshall
> - 大稀疏图：邻接表 + Dijkstra（堆优化）
> - 无权图：直接用 BFS 求最短路径
> - 负权边：改用 Bellman-Ford 或 SPFA

# 后续

python过渡项目部分代码已经上传至gitee，后续会逐步更新。

# 资料关注

公众号：咚咚王

《Python编程：从入门到实践》
《利用Python进行数据分析》
《算法导论中文第三版》
《概率论与数理统计（第四版） (盛骤) 》
《程序员的数学》
《线性代数应该这样学第3版》
《微积分和数学分析引论》
《（西瓜书）周志华-机器学习》
《TensorFlow机器学习实战指南》
《Sklearn与TensorFlow机器学习实用指南》
《模式识别（第四版）》
《深度学习 deep learning》伊恩·古德费洛著 花书
《Python深度学习第二版(中文版)【纯文本】 (登封大数据 (Francois Choliet)) (Z-Library)》
《深入浅出神经网络与深度学习+(迈克尔·尼尔森（Michael+Nielsen）》
《自然语言处理综论  第2版》
《Natural-Language-Processing-with-PyTorch》
《计算机视觉-算法与应用(中文版)》
《Learning OpenCV 4》
《AIGC：智能创作时代》杜雨+&+张孜铭
《AIGC原理与实践：零基础学大语言模型、扩散模型和多模态模型》
《从零构建大语言模型（中文版）》
《实战AI大模型》
《AI 3.0》

图论是离散数学的核心分支，广泛应用于社交网络分析、路径规划、编译器优化、知识图谱、推荐系统等计算机科学领域。本文系统讲解：

人工智能之数学基础 离散数学：第二章 图论

技术岗

编程语言

图论是离散数学核心分支，涵盖图的基本概念、表示方法（邻接矩阵/邻接表）、遍历算法（BFS/DFS）和最短路径算法（Dijkstra/Floyd-Warshall）。本文结合Python代码实现，详细讲解图论在社交网络、路径规划等领域的应用，并提供NetworkX可视化对比，帮助读者掌握图论核心算法与实践技巧。

自然语言处理

计算机视觉

智能创作

人工智能

机器学习

深度学习

大数据

编译器

Python

AI驱动 智领未来

bigdata-class

ai-class

腾讯云BI新客户首次购买9.9元起！


5位重磅专家聚焦 AI 时代开发者核心成长需求，带你深入解锁全栈进化、人机协作关键路径！点击报名到场：<a href="https://cloud.tencent.com/developer/salon/salon-2403/signup" target="_blank">https://cloud.tencent.com/developer/salon/salon-2403/signup</a><br/> 
 <img src="https://qcloudimg.tencent-cloud.cn/raw/487c82639d2338df3ef66dfb1450601a.png"/>

腾讯技术创作特训营「年度论坛」正在报名中！

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

人工智能之数学基础 离散数学：第二章 图论-腾讯云开发者社区-腾讯云

人工智能之数学基础离散数学：第二章图论

人工智能之数学基础离散数学：第二章图论

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

人工智能之数学基础 离散数学：第二章 图论

人工智能之数学基础 离散数学：第二章 图论

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

人工智能之数学基础离散数学：第二章图论

人工智能之数学基础离散数学：第二章图论