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

文章目录前言一、图论入门先搞懂什么是图1.1 图的核心定义1.2 图的常见分类1无向图 vs 有向图2无权图 vs 有权图1.3 图的基础术语二、图的表示计算机怎么存储图2.1 邻接矩阵直观但费空间的“二维表格”1核心原理2通俗类比3代码示例Python4优缺点2.2 邻接表省空间的“链表数组”1核心原理2通俗类比3代码示例Python4优缺点2.3 两种存储方式怎么选三、图的遍历走遍图里所有顶点3.1 深度优先遍历DFS一条路走到黑1核心思想2通俗类比3实现方式递归访问标记4代码示例Python邻接表实现5特点3.2 广度优先遍历BFS一层一层往外扩1核心思想2通俗类比3实现方式队列访问标记4代码示例Python邻接表实现5特点3.3 DFS和BFS怎么选四、最短路径图论最实用的核心算法4.1 Dijkstra算法单源最短路径王者1适用场景2核心思想贪心算法3通俗类比4代码示例Python邻接表堆优化4.2 Floyd算法多源最短路径1适用场景2核心思想动态规划3代码示例Python邻接矩阵实现4优缺点4.3 最短路径算法选择五、图论基础实战总结结语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、20-1权重51-2权重30-2权重8# 定义无穷大代表无边INFfloat(inf)# 3个顶点的邻接矩阵n3graph[[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(VE)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):# 创建队列起始顶点入队queuedeque([start])visited[start]Truewhilequeue:# 队首顶点出队vertexqueue.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):# 初始化最短路径数组无穷大代表初始不可达INFfloat(inf)dist[INF]*n dist[start]0# 最小堆存储(当前距离, 顶点)heap[]heapq.heappush(heap,(0,start))whileheap:# 取出距离最小的顶点current_dist,vertexheapq.heappop(heap)# 如果当前距离大于已记录的最短距离跳过ifcurrent_distdist[vertex]:continue# 遍历邻接顶点更新最短路径forneighbor,weightingraph[vertex]:ifdist[neighbor]dist[vertex]weight:dist[neighbor]dist[vertex]weight heapq.heappush(heap,(dist[neighbor],neighbor))returndist# 测试4个顶点的有向有权图n4graph[[(1,2),(2,5)],[(0,2),(3,1)],[(0,5),(3,3)],[]]# 从顶点0出发resultdijkstra(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个顶点的无向有权图INFfloat(inf)graph[[0,5,8],[5,0,3],[8,3,0]]resultfloyd(graph,3)print(任意两点最短路径矩阵)forrowinresult:print(row)4优缺点优点代码极简能求所有顶点间的最短路径缺点时间复杂度O(n³)只适合小批量顶点大数据量不推荐。4.3 最短路径算法选择单源最短路径、边权非负、大数据量选堆优化Dijkstra任意两点最短路径、顶点数量少选Floyd算法无权图最短路径直接用BFS最简单高效。五、图论基础实战总结学完上面的内容咱们简单梳理一下图论基础的核心知识体系方便大家记忆图的本质是顶点和边的集合分无向/有向、无权/有权是描述多对多关系的最佳数据结构图的存储邻接矩阵适合稠密图邻接表适合稀疏图工程优先邻接表图的遍历DFS一条路走到黑适合路径搜索BFS层层遍历适合无权图最短路径最短路径Dijkstra搞定单源非负权最短路径Floyd搞定多源最短路径。图论看着抽象其实只要结合生活场景去理解把核心逻辑吃透再动手敲几遍代码就能轻松掌握。作为算法和AI开发的基础图论的应用场景还在不断拓展比如大模型的知识图谱、自动驾驶路径规划、智慧城市交通调度全都离不开图论算法。新手学习切忌死记硬背公式和代码一定要先理解原理再动手实践把每个算法的执行流程走一遍自然就能融会贯通。后续我会继续分享图论的高级算法比如最小生成树、拓扑排序、负权图最短路径带大家一步步攻克图论难关。结语图论不是高高在上的理论知识而是扎根在日常开发、AI应用中的实用工具。不管是想要转行做AI开发还是备战算法面试把图论基础打牢都是必不可少的一步。学习算法没有捷径唯有多理解、多动手、多总结。希望这篇文章能帮大家扫清图论入门的障碍不再畏惧复杂的算法逻辑真正走进算法与AI的世界。后续我会持续输出更多通俗易懂的技术干货陪大家一起在技术路上稳步前行。P.S. 目前国内还是很缺AI人才的希望更多人能真正加入到AI行业共同促进行业进步增强我国的AI竞争力。想要系统学习AI知识的朋友可以看看我精心打磨的教程 http://blog.csdn.net/jiangjunshow教程通俗易懂高中生都能看懂还有各种段子风趣幽默从深度学习基础原理到各领域实战应用都有讲解我22年的AI积累全在里面了。注意教程仅限真正想入门AI的朋友否则看看零散的博文就够了。