图论基础：图的表示、遍历、最短路径入门

P.S. 目前国内还是很缺AI人才的，希望更多人能真正加入到AI行业，共同促进行业进步，增强我国的AI竞争力。想要系统学习AI知识的朋友可以看看我精心打磨的教程 http://blog.csdn.net/jiangjunshow，教程通俗易懂，高中生都能看懂，还有各种段子风趣幽默，从深度学习基础原理到各领域实战应用都有讲解，我22年的AI积累全在里面了。注意，教程仅限真正想入门AI的朋友，否则看看零散的博文就够了。

前言

但凡接触过算法、AI、大数据、网络开发的朋友，大概率都听过图论这个词。很多新手一看到图论的专业术语，比如顶点、边、邻接矩阵、深度优先遍历，直接头大，觉得这是计算机专业大佬才玩得转的高深知识，其实完全不是这么回事。

说白了，图论就是研究点和点之间关系的学问，生活里到处都是图的影子：微信好友关系是图，城市交通路网是图，外卖配送路径规划是图，甚至咱们刷短视频的推荐逻辑，底层也离不开图论算法。作为数据结构与算法的核心板块，图论是入门AI、后端开发、算法岗的必备基础，不管是面试还是实际工程开发，都是绕不开的重点。

这篇文章我就用最接地气的大白话，搭配生活化段子和类比，从零开始带大家搞定图论基础，把图的核心概念、两种存储表示方式、两大遍历算法、经典最短路径算法一次性讲透，全程无晦涩公式，新手也能轻松看懂，看完直接上手写代码。

一、图论入门：先搞懂什么是图

1.1 图的核心定义

先抛开书本上的严谨定义，用一句话理解：图 = 顶点 + 边，专业写法是G=(V, E)。

• 顶点（V）：就是图里的一个个“点”，可以理解成现实里的一个个实体，比如人、城市、网页、外卖商家；
• 边（E）：就是连接两个顶点的“线”，代表顶点之间的关系，比如朋友关系、城市间的公路、网页跳转链接、商家到用户的配送路线。

举个最通俗的例子：把你、我、同事张三看作三个顶点，你和我是好友、我和张三是好友，这两条好友关系就是两条边，这三个顶点加两条边，就构成了一个最简单的图。

和咱们之前学的线性表（数组、链表）、树结构对比一下，更容易理解：

• 线性表：元素之间是一对一的关系，像排队买饭，一个跟着一个；
• 树：元素之间是一对多的关系，像公司层级，一个领导管多个下属；
• 图：元素之间是多对多的关系，任意两个点都能产生关联，灵活性拉满。

1.2 图的常见分类

（1）无向图 vs 有向图

根据边有没有方向，图分为无向图和有向图，这个区别特别好记。

• 无向图：边没有方向，是双向的，就像双向通行的公路，从A城市能到B城市，反过来也能走。比如微信好友关系，你加了我好友，我自动也是你的好友，这就是无向边。
• 有向图：边有明确方向，是单向的，像单行道。比如抖音关注，你关注了网红，网红不一定关注你，这条关注关系就是有向边；再比如网页跳转，从A网页能跳到B网页，不代表B网页能跳回A网页。

（2）无权图 vs 有权图

根据边有没有权重，图分为无权图和有权图。

• 无权图：边只有“连接”和“不连接”两种状态，没有额外数值，只关心两个点是否连通，不关心连通的成本；
• 有权图：边带有数值（权重），这个权重可以代表距离、时间、成本、流量。比如北京到上海的公路，权重是1318公里；外卖商家到用户的路线，权重是配送时间15分钟。

1.3 图的基础术语

再记几个高频术语，后面学算法会反复用到：

• 邻接：两个顶点之间有边直接相连，就说这两个顶点邻接；
• 度：一个顶点相连的边的数量。无向图里直接叫度，有向图里分入度（指向该顶点的边数）和出度（从该顶点出发的边数）；
• 路径：从一个顶点到另一个顶点，经过的顶点和边的序列；
• 简单路径：路径里的顶点不重复，避免绕圈子；
• 连通图：图里任意两个顶点之间都有路径可达，不会出现孤立的点。

二、图的表示：计算机怎么存储图

我们理解的图是纸上的点和线，但计算机没法直接识别，必须把图转换成代码能存储的数据结构。2026年主流的图存储方式有两种：邻接矩阵和邻接表，两者各有优劣，适用场景不同，下面挨个拆解。

2.1 邻接矩阵：直观但费空间的“二维表格”

（1）核心原理

邻接矩阵就是用二维数组存储图，数组的行和列对应图的顶点，数组里的值对应边的信息。

假设图有n个顶点，我们就创建一个n×n的二维数组graph[][]：

• 无向无权图：graph[i][j] = 1表示顶点i和j相连，0表示不相连；
• 无向有权图：graph[i][j] = 权重值表示顶点i和j相连，∞（无穷大）表示不相连；
• 有向图：graph[i][j]表示从i指向j的边，无向图的矩阵是对称的，有向图不一定对称。

（2）通俗类比

邻接矩阵就像一张关系对照表，比如全班同学的同桌关系表，行是第一个同学，列是第二个同学，表格里写1代表是同桌，0代表不是。

（3）代码示例（Python）

以3个顶点的无向有权图为例，顶点0、1、2，0-1权重5，1-2权重3，0-2权重8：

# 定义无穷大，代表无边INF=float('inf')# 3个顶点的邻接矩阵n=3graph=[[0,5,8],[5,0,3],[8,3,0]]

（4）优缺点

• 优点：实现简单，查询两个顶点是否相连超快，时间复杂度O(1)；
• 缺点：太浪费空间！如果是稀疏图（顶点多、边少），比如1000个顶点只有几百条边，二维数组里大部分位置都是∞，空间利用率极低，时间复杂度O(n²)，处理大数据量很拉胯。

2.2 邻接表：省空间的“链表数组”

（1）核心原理

邻接表是数组+链表的组合，数组里的每个元素对应一个顶点，每个顶点后面跟着一条链表，链表里存储该顶点所有邻接的顶点及边的权重。

简单说：给每个顶点建一个“好友列表”，列表里只存和它直接相连的点，没关联的一概不存。

（2）通俗类比

邻接表就像每个人的通讯录，你的通讯录里只存你好友的名字和联系方式，不认识的人不会出现在里面，比邻接矩阵那种全量对照表省太多空间。

（3）代码示例（Python）

还是上面3个顶点的无向有权图，用邻接表实现：

# 邻接表，列表里嵌套列表，每个元素存(邻接顶点, 权重)graph=[[(1,5),(2,8)],# 顶点0的邻接顶点[(0,5),(2,3)],# 顶点1的邻接顶点[(0,8),(1,3)]# 顶点2的邻接顶点]

（4）优缺点

• 优点：空间利用率极高，只存储存在的边，稀疏图首选，时间复杂度O(V+E)（V是顶点数，E是边数），处理大数据量效率高；
• 缺点：查询两个顶点是否相连时，需要遍历对应顶点的链表，速度比邻接矩阵慢一点。

2.3 两种存储方式怎么选？

给大家一个直接能用的选择标准：

• 顶点少、边多的稠密图，用邻接矩阵；
• 顶点多、边少的稀疏图，用邻接表（工程开发、AI算法里绝大多数都是稀疏图，优先选邻接表）。

三、图的遍历：走遍图里所有顶点

图的遍历，就是从一个顶点出发，按照固定的规则，访问图里所有顶点，每个顶点只访问一次，避免重复遍历。这是图论所有高级算法的基础，最短路径、拓扑排序、连通性判断都离不开遍历。

图的遍历有两种经典算法：深度优先遍历（DFS）和广度优先遍历（BFS），两者的遍历顺序完全不同，适用场景也不一样。

3.1 深度优先遍历（DFS）：一条路走到黑

（1）核心思想

DFS的核心就是不撞南墙不回头，沿着一条路径一直往下走，走到走不通了，再退回到上一个岔路口，换另一条路径继续走，直到所有顶点都被访问。

（2）通俗类比

把图比作一个迷宫，DFS就像走迷宫：从入口进去，选一条路一直往前走，遇到岔路就选一条继续走，直到走到死胡同，再原路返回，换另一条没走过的岔路，直到把迷宫所有房间都走一遍。

（3）实现方式：递归+访问标记

需要一个标记数组，记录哪些顶点已经被访问过，避免重复递归。

（4）代码示例（Python，邻接表实现）

# 邻接表graph=[[(1,5),(2,8)],[(0,5),(2,3)],[(0,8),(1,3)]]# 标记数组，初始全为False，代表未访问visited=[False]*len(graph)defdfs(vertex):# 标记当前顶点已访问visited[vertex]=Trueprint(f"访问顶点：{vertex}")# 遍历当前顶点的所有邻接顶点forneighbor,weightingraph[vertex]:ifnotvisited[neighbor]:dfs(neighbor)# 从顶点0开始遍历dfs(0)

（5）特点

• 采用栈的思想（递归本质就是系统栈），先深入后回溯；
• 适合找路径、判断连通性、解决迷宫类问题；
• 代码简洁，但是深度太大时容易出现栈溢出。

3.2 广度优先遍历（BFS）：一层一层往外扩

（1）核心思想

BFS的核心是先近后远，从起始顶点出发，先访问所有和它直接相连的顶点（第一层），再访问第一层顶点所有直接相连的顶点（第二层），以此类推，层层往外扩，直到所有顶点都被访问。

（2）通俗类比

BFS就像往平静的水面扔一颗石头，泛起的涟漪一层一层往外扩散，最中心是起始顶点，每一圈涟漪就是一层顶点。

（3）实现方式：队列+访问标记

用队列存储待访问的顶点，先进先出，保证按层遍历。

（4）代码示例（Python，邻接表实现）

fromcollectionsimportdeque# 邻接表graph=[[(1,5),(2,8)],[(0,5),(2,3)],[(0,8),(1,3)]]visited=[False]*len(graph)defbfs(start):# 创建队列，起始顶点入队queue=deque([start])visited[start]=Truewhilequeue:# 队首顶点出队vertex=queue.popleft()print(f"访问顶点：{vertex}")# 邻接未访问顶点入队forneighbor,weightingraph[vertex]:ifnotvisited[neighbor]:visited[neighbor]=Truequeue.append(neighbor)# 从顶点0开始遍历bfs(0)

（5）特点

• 采用队列的思想，按层遍历；
• 适合找无权图的最短路径，这是BFS最核心的用途；
• 不会出现栈溢出，处理大规模图更稳定。

3.3 DFS和BFS怎么选？

• 想要找路径、回溯求解，用DFS；
• 想要找最短路径、按层遍历，用BFS；
• 工程开发中，BFS的实用性更强，尤其是路径规划类场景。

四、最短路径：图论最实用的核心算法

日常开发里，图论用得最多的就是最短路径问题：在有权图中，找到从一个起始顶点（源点）到其他所有顶点的总权重最小的路径。比如地图导航找最短路线、外卖找最优配送路径、网络找最低延迟传输路线，都是最短路径问题。

这里给大家讲两个2026年最常用、面试必考的最短路径算法：Dijkstra算法和Floyd算法，一个适合单源最短路径，一个适合多源最短路径。

4.1 Dijkstra算法：单源最短路径王者

（1）适用场景

从一个源点出发，到其他所有顶点的最短路径，要求图中所有边的权重非负（不能有负数距离、负数时间），这是工程中最常用的最短路径算法，导航、配送系统基本都用它。

（2）核心思想：贪心算法

把所有顶点分成两部分：

• 已确定最短路径的顶点集合S；
• 未确定最短路径的顶点集合U。

初始时，源点在S里，最短路径为0，其余顶点在U里，最短路径为无穷大。
每次从U里选一个距离源点最近的顶点，加入S，然后更新这个顶点邻接顶点的最短路径，重复这个过程，直到U为空。

（3）通俗类比

就像你要从家出发去城市里所有地方，先找离家最近的商场，确定到商场的最短路径；再以商场为中转站，找离商场最近的公园，更新家到公园的最短路径，一步步把所有地方的最短路径都找出来。

（4）代码示例（Python，邻接表+堆优化）

普通Dijkstra时间复杂度高，2026年工程开发都用堆优化，用最小堆快速找最短路径顶点，效率大幅提升：

importheapqdefdijkstra(graph,start,n):# 初始化最短路径数组，无穷大代表初始不可达INF=float('inf')dist=[INF]*n dist[start]=0# 最小堆，存储(当前距离, 顶点)heap=[]heapq.heappush(heap,(0,start))whileheap:# 取出距离最小的顶点current_dist,vertex=heapq.heappop(heap)# 如果当前距离大于已记录的最短距离，跳过ifcurrent_dist>dist[vertex]:continue# 遍历邻接顶点，更新最短路径forneighbor,weightingraph[vertex]:ifdist[neighbor]>dist[vertex]+weight:dist[neighbor]=dist[vertex]+weight heapq.heappush(heap,(dist[neighbor],neighbor))returndist# 测试：4个顶点的有向有权图n=4graph=[[(1,2),(2,5)],[(0,2),(3,1)],[(0,5),(3,3)],[]]# 从顶点0出发result=dijkstra(graph,0,n)print("顶点0到各顶点的最短路径：",result)

4.2 Floyd算法：多源最短路径

（1）适用场景

求任意两个顶点之间的最短路径，允许边权重为负数，但不能有负权回路，适合顶点数量少的稠密图。

（2）核心思想：动态规划

核心公式：graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
意思是：从i到j的最短路径，要么是直接路径，要么是经过中间顶点k的间接路径，取两者最小值。

遍历所有顶点作为中间顶点k，依次更新任意两个顶点之间的最短路径，最终得到全局最短路径。

（3）代码示例（Python，邻接矩阵实现）

deffloyd(graph,n):# 拷贝邻接矩阵，避免修改原数据dist=[row[:]forrowingraph]# 遍历所有中间顶点kforkinrange(n):# 遍历所有起点iforiinrange(n):# 遍历所有终点jforjinrange(n):ifdist[i][j]>dist[i][k]+dist[k][j]:dist[i][j]=dist[i][k]+dist[k][j]returndist# 测试：3个顶点的无向有权图INF=float('inf')graph=[[0,5,8],[5,0,3],[8,3,0]]result=floyd(graph,3)print("任意两点最短路径矩阵：")forrowinresult:print(row)

（4）优缺点

• 优点：代码极简，能求所有顶点间的最短路径；
• 缺点：时间复杂度O(n³)，只适合小批量顶点，大数据量不推荐。

4.3 最短路径算法选择

• 单源最短路径、边权非负、大数据量：选堆优化Dijkstra；
• 任意两点最短路径、顶点数量少：选Floyd算法；
• 无权图最短路径：直接用BFS，最简单高效。

五、图论基础实战总结

学完上面的内容，咱们简单梳理一下图论基础的核心知识体系，方便大家记忆：

1. 图的本质是顶点和边的集合，分无向/有向、无权/有权，是描述多对多关系的最佳数据结构；
2. 图的存储：邻接矩阵适合稠密图，邻接表适合稀疏图，工程优先邻接表；
3. 图的遍历：DFS一条路走到黑，适合路径搜索；BFS层层遍历，适合无权图最短路径；
4. 最短路径：Dijkstra搞定单源非负权最短路径，Floyd搞定多源最短路径。

图论看着抽象，其实只要结合生活场景去理解，把核心逻辑吃透，再动手敲几遍代码，就能轻松掌握。作为算法和AI开发的基础，图论的应用场景还在不断拓展，比如大模型的知识图谱、自动驾驶路径规划、智慧城市交通调度，全都离不开图论算法。

新手学习切忌死记硬背公式和代码，一定要先理解原理，再动手实践，把每个算法的执行流程走一遍，自然就能融会贯通。后续我会继续分享图论的高级算法，比如最小生成树、拓扑排序、负权图最短路径，带大家一步步攻克图论难关。

结语

图论不是高高在上的理论知识，而是扎根在日常开发、AI应用中的实用工具。不管是想要转行做AI开发，还是备战算法面试，把图论基础打牢都是必不可少的一步。

学习算法没有捷径，唯有多理解、多动手、多总结。希望这篇文章能帮大家扫清图论入门的障碍，不再畏惧复杂的算法逻辑，真正走进算法与AI的世界。后续我会持续输出更多通俗易懂的技术干货，陪大家一起在技术路上稳步前行。

P.S. 目前国内还是很缺AI人才的，希望更多人能真正加入到AI行业，共同促进行业进步，增强我国的AI竞争力。想要系统学习AI知识的朋友可以看看我精心打磨的教程 http://blog.csdn.net/jiangjunshow，教程通俗易懂，高中生都能看懂，还有各种段子风趣幽默，从深度学习基础原理到各领域实战应用都有讲解，我22年的AI积累全在里面了。注意，教程仅限真正想入门AI的朋友，否则看看零散的博文就够了。