数据结构——图：存储结构、DFS、BFS、最小生成树-北京尧图网络

图是数据结构中最后一类重要的非线性结构。前面的链表是一对一树是一对多图是多对多。图的遍历DFS/BFS和最小生成树是 408 考研的重点。一、图的基本概念1. 定义图由**顶点Vertex和边Edge**组成。无向图 A —— B | | C —— D 有向图带箭头 A → B ↓ ↓ C ← D术语顶点图中的节点边顶点之间的连线无向图边没有方向(A, B) (B, A)有向图边有方向A, B ≠ B, A完全图任意两个顶点之间都有边权边上的数值如距离、花费连通图任意两个顶点之间都有路径可达二、图的存储结构1. 邻接矩阵// 用一个二维数组存储顶点之间的邻接关系// graph[i][j] 1 表示顶点 i 到 j 有边// graph[i][j] 0 表示没有边publicclassGraphMatrix{privateint[][]matrix;// 邻接矩阵privateintn;// 顶点数privatebooleandirected;// 是否有向publicGraphMatrix(intn,booleandirected){this.nn;this.directeddirected;matrixnewint[n][n];}// 添加边publicvoidaddEdge(inti,intj,intweight){matrix[i][j]weight;// i → jif(!directed){matrix[j][i]weight;// 无向图对称}}// 判断是否有边publicbooleanhasEdge(inti,intj){returnmatrix[i][j]!0;}}无向图的邻接矩阵对称 A B C D A [0, 1, 1, 0] B [1, 0, 0, 1] C [1, 0, 0, 1] D [0, 1, 1, 0]优点判断两点是否有边 O(1)实现简单缺点占用空间 O(n²)稀疏图浪费空间2. 邻接表// 每个顶点维护一个链表存储与其相连的顶点publicclassGraphList{privateListInteger[]adj;// 邻接表数组privateintn;publicGraphList(intn){this.nn;adjnewList[n];for(inti0;in;i){adj[i]newArrayList();}}publicvoidaddEdge(inti,intj){adj[i].add(j);adj[j].add(i);// 无向图}publicListIntegergetNeighbors(intv){returnadj[v];}}无向图的邻接表 A → [B, C] B → [A, D] C → [A, D] D → [B, C]优点节省空间 O(n e)适合稀疏图缺点判断两点是否有边需要遍历链表 O(degree)3. 邻接矩阵 vs 邻接表对比邻接矩阵邻接表空间O(n²)O(n e)判边O(1) O(度)遍历邻居O(n)O(度) 适合稠密图稀疏图常用三、图的遍历1. 深度优先搜索DFS沿着一条路走到黑走不通了再回头。publicclassGraphDFS{privateListInteger[]adj;privateboolean[]visited;publicvoiddfs(intstart){visitednewboolean[adj.length];dfsRecursive(start);}privatevoiddfsRecursive(intv){visited[v]true;System.out.print(v );// 访问当前顶点for(intneighbor:adj[v]){if(!visited[neighbor]){dfsRecursive(neighbor);// 递归访问未访问的邻居}}}}从 A 开始 DFS假设邻接顺序从小到大 A → B → D → C 路径A → B → D → C 访问顺序A, B, D, C时间复杂度O(n e)空间复杂度O(n)递归栈2. 广度优先搜索BFS一层一层往外扩像水的波纹。publicclassGraphBFS{privateListInteger[]adj;privateboolean[]visited;publicvoidbfs(intstart){visitednewboolean[adj.length];QueueIntegerqueuenewLinkedList();visited[start]true;queue.offer(start);while(!queue.isEmpty()){intvqueue.poll();System.out.print(v );// 访问当前顶点for(intneighbor:adj[v]){if(!visited[neighbor]){visited[neighbor]true;queue.offer(neighbor);// 未访问的邻居入队}}}}}从 A 开始 BFS 第一层A 第二层B, C 第三层D 访问顺序A, B, C, D时间复杂度O(n e)空间复杂度O(n)队列3. DFS vs BFS对比DFSBFS数据结构栈递归队列遍历顺序沿着路径深入逐层扩展适用场景连通性判断、拓扑排序最短路径、层序遍历实现难度递归代码简洁循环稍复杂四、最小生成树用最小的总权值把所有顶点连通。1. Prim 算法从一个顶点开始每次找权值最小的边加入。publicclassPrim{/** * Prim 算法求最小生成树 * param graph 邻接矩阵权值0表示无边 * return 最小总权值 */publicstaticintprim(int[][]graph){intngraph.length;int[]lowCostnewint[n];// 到各顶点的最小权值boolean[]visitednewboolean[n];inttotal0;// 从顶点0开始visited[0]true;for(inti0;in;i){lowCost[i]graph[0][i]0?Integer.MAX_VALUE:graph[0][i];}for(inti1;in;i){// 找权值最小的未访问顶点intminInteger.MAX_VALUE;intminIdx-1;for(intj0;jn;j){if(!visited[j]lowCost[j]min){minlowCost[j];minIdxj;}}if(minIdx-1)break;// 不连通visited[minIdx]true;totalmin;// 更新 lowCostfor(intj0;jn;j){if(!visited[j]graph[minIdx][j]!0graph[minIdx][j]lowCost[j]){lowCost[j]graph[minIdx][j];}}}returntotal;}}2. Kruskal 算法每次选权值最小的边只要不形成环就加入。publicclassKruskal{// 边的定义staticclassEdgeimplementsComparableEdge{intu,v,weight;publicintcompareTo(Edgeo){returnthis.weight-o.weight;}}// 并查集staticclassUnionFind{int[]parent;UnionFind(intn){parentnewint[n];for(inti0;in;i)parent[i]i;}intfind(intx){returnparent[x]x?x:(parent[x]find(parent[x]));}booleanunion(intx,inty){intrxfind(x),ryfind(y);if(rxry)returnfalse;parent[rx]ry;returntrue;}}publicstaticintkruskal(Edge[]edges,intn){Arrays.sort(edges);// 按权值排序UnionFindufnewUnionFind(n);inttotal0,count0;for(Edgee:edges){if(uf.union(e.u,e.v)){// 不会形成环totale.weight;count;if(countn-1)break;// n个顶点需要n-1条边}}returntotal;}}3. Prim vs Kruskal对比PrimKruskal策略选顶点选边数据结构邻接矩阵边集并查集时间复杂度O(n²)O(e log e)适合稠密图稀疏图五、408 考研经典考题题1邻接矩阵转邻接表ListInteger[]matrixToList(int[][]matrix){intnmatrix.length;ListInteger[]adjnewList[n];for(inti0;in;i){adj[i]newArrayList();for(intj0;jn;j){if(matrix[i][j]1){adj[i].add(j);}}}returnadj;}题2判断图是否连通booleanisConnected(ListInteger[]adj){intnadj.length;boolean[]visitednewboolean[n];dfs(adj,visited,0);for(booleanv:visited){if(!v)returnfalse;}returntrue;}题3拓扑排序有向无环图DAG的顶点线性排序AOV 网中活动执行的先后顺序。// 核心思想不断删除入度为 0 的顶点ListIntegertopologicalSort(ListInteger[]adj){intnadj.length;int[]inDegreenewint[n];for(inti0;in;i){for(intv:adj[i])inDegree[v];}QueueIntegerqueuenewLinkedList();for(inti0;in;i){if(inDegree[i]0)queue.offer(i);}ListIntegerresultnewArrayList();while(!queue.isEmpty()){intvqueue.poll();result.add(v);for(intneighbor:adj[v]){if(--inDegree[neighbor]0){queue.offer(neighbor);}}}returnresult;}六、图的常见考点1. 有 n 个顶点的无向完全图有 n(n-1)/2 条边 2. 有 n 个顶点的有向完全图有 n(n-1) 条边 3. 连通图至少需要 n-1 条边树 4. 图的邻接矩阵是对称矩阵无向图 DFS/BFS 时间复杂度的写法邻接矩阵O(n²) 邻接表O(n e) 觉得有用的话点赞关注【张老师技术栈】吧每周更新 Java/Python/爬虫实战干货不让你白来。

数据结构——图：存储结构、DFS、BFS、最小生成树

相关推荐

AD74413R与STM32L442KC硬件协同设计与应用

Grafana Dashboard JSON 文件详解

番茄小说下载器完整指南：5种格式+Web界面打造永久个人图书馆

更多资讯

diagram-design：现代前端可视化工程的核心能力

彩云科技两破NanoGPT训练纪录：改结构正在比堆算力更值钱

HTML DOM方法详解：从元素查找到事件委托与性能优化实战

diagram-design：从Mermaid到生产级SVG的全链路实践

AutoHedge：基于动态敞口控制的加密货币自动对冲系统设计与实战

无限画布怎么选？动漫世界观设计工具选型与实战指南

今日更新

CopilotKit Vue Demo 与 React Demo 的 Parity 实现指南：路由、运行时端点与交互语义的全框架对齐

Harbor RBAC 实战：db_auth 模式下非管理员用户管理项目成员的完整验证与权限模型解析

STM32平衡车纯平衡程序从拆包到参数整定的完整调试指南

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？