娄底市网站建设_网站建设公司_展示型网站_seo优化

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

第二章 图论—公式关注公众号

文章目录

• 人工智能之数学基础 离散数学
• 前言
• 一、图的基本定义
• • 1. 什么是图？
  • • 2. 图的类型
  • 3. 基本术语
• 二、图的表示方法
• • 1. 邻接矩阵（Adjacency Matrix）
  • 2. 邻接表（Adjacency List）
• 三、图的遍历算法
• • 1. 广度优先搜索（BFS）
  • • 算法步骤：
  • 2. 深度优先搜索（DFS）
  • • 算法步骤（递归版）：
• 四、最短路径算法
• • 1. Dijkstra 算法（单源最短路径）
  • • 算法步骤：
  • 2. Floyd-Warshall 算法（全源最短路径）
  • • 核心思想：
• 五、Python 代码实现
• • 1. 导入库
  • 2. 图类实现（邻接表）
  • 3. BFS 实现
  • 4. DFS 实现（递归）
  • 5. Dijkstra 算法
  • 6. Floyd-Warshall 算法
  • 7. 可视化：使用 NetworkX
  • 8. 与 NetworkX 内置算法对比
• 六、应用场景速览
• 七、总结
• 后续
• 资料关注

前言

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

• 图的基本概念（有向图/无向图、权重、度）
• 图的表示方法（邻接矩阵、邻接表）
• 图的遍历算法（深度优先搜索 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. 图的类型

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 ] = { 1 若存在边 ( v i , v j ) 0 否则 A[i][j] = \begin{cases} 1 & \text{若存在边 } (v_i, v_j) \\ 0 & \text{否则} \end{cases}A[i][j]={10​若存在边(vi​,vj​)否则​
• 带权图：$ 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) $

核心思想：

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

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

五、Python 代码实现

1. 导入库

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

2. 图类实现（邻接表）

classGraph:def__init__(self,directed=False):self.graph=defaultdict(list)# 邻接表self.directed=directed self.weights={}# 存储边权重: {(u,v): w}defadd_edge(self,u,v,weight=1):self.graph[u].append(v)ifnotself.directed:self.graph[v].append(u)self.weights[(u,v)]=weightifnotself.directed:self.weights[(v,u)]=weightdefget_neighbors(self,u):returnself.graph[u]defget_weight(self,u,v):returnself.weights.get((u,v),float('inf'))defvertices(self):returnlist(self.graph.keys())

3. BFS 实现

defbfs(graph,start):visited=set()queue=deque([start])visited.add(start)order=[]whilequeue:node=queue.popleft()order.append(node)forneighboringraph.get_neighbors(node):ifneighbornotinvisited:visited.add(neighbor)queue.append(neighbor)returnorder# 测试g=Graph()edges=[('A','B'),('A','C'),('B','D'),('C','E')]foru,vinedges:g.add_edge(u,v)print("BFS 顺序:",bfs(g,'A'))# 输出: ['A', 'B', 'C', 'D', 'E']

4. DFS 实现（递归）

defdfs_recursive(graph,start,visited=None):ifvisitedisNone:visited=set()visited.add(start)order=[start]forneighboringraph.get_neighbors(start):ifneighbornotinvisited:order.extend(dfs_recursive(graph,neighbor,visited))returnorderprint("DFS 顺序:",dfs_recursive(g,'A'))# 输出: ['A', 'B', 'D', 'C', 'E']

5. Dijkstra 算法

defdijkstra(graph,start):dist={node:float('inf')fornodeingraph.vertices()}dist[start]=0prev={node:Nonefornodeingraph.vertices()}# 优先队列: (distance, node)pq=[(0,start)]whilepq:current_dist,u=heapq.heappop(pq)# 跳过已处理的更优路径ifcurrent_dist>dist[u]:continueforvingraph.get_neighbors(u):weight=graph.get_weight(u,v)new_dist=dist[u]+weightifnew_dist<dist[v]:dist[v]=new_dist prev[v]=u heapq.heappush(pq,(new_dist,v))returndist,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 算法

deffloyd_warshall(vertices,get_weight):n=len(vertices)idx={v:ifori,vinenumerate(vertices)}INF=float('inf')# 初始化距离矩阵dist=[[INF]*nfor_inrange(n)]foriinrange(n):dist[i][i]=0fori,uinenumerate(vertices):forj,vinenumerate(vertices):ifi!=j:w=get_weight(u,v)ifw!=INF:dist[i][j]=w# 动态规划更新forkinrange(n):foriinrange(n):forjinrange(n):ifdist[i][k]+dist[k][j]<dist[i][j]:dist[i][j]=dist[i][k]+dist[k][j]# 转回字典result={}fori,uinenumerate(vertices):result[u]={}forj,vinenumerate(vertices):result[u][v]=dist[i][j]returnresult# 测试fw_dist=floyd_warshall(gw.vertices(),gw.get_weight)print("Floyd-Warshall A→E:",fw_dist['A']['E'])# 输出: 11

7. 可视化：使用 NetworkX

# 构建 NetworkX 图G_nx=nx.DiGraph()for(u,v),wingw.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 内置算法对比

# BFSprint("NetworkX BFS:",list(nx.bfs_tree(G_nx,'A')))# Dijkstranx_dist=nx.single_source_dijkstra_path_length(G_nx,'A')print("NetworkX Dijkstra:",nx_dist)# 验证一致性assertdist==nx_dist,"结果不一致！"print("✅ 自实现与 NetworkX 结果一致")

六、应用场景速览

七、总结

💡工程建议：

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

后续

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

资料关注

公众号：咚咚王
gitee：https://gitee.com/wy18585051844/ai_learning

《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》