考研复习 Day 18 | 数据结构与算法--图（上）

一、图的基本概念1.1 图的定义图G由顶点集V和边集E组成记为G(V,E)要素说明V(G)顶点的有限非空集E(G)顶点之间关系的集合重要线性表可以是空表树可以是空树但图不可以是空图。顶点集V必须非空但边集E可以为空。1.2 基本术语1. 有向图 vs 无向图类型边的形式说明有向图v, wv称为弧尾w称为弧头表示v→w无向图(v, w)或(w, v)v和w互为邻接点2. 简单图 vs 多重图类型条件简单图① 不存在重复边② 不存在顶点到自身的边多重图两顶点之间边数可超过1条允许顶点通过边与自身关联这里仅讨论简单图。3. 顶点的度、入度、出度图类型定义重要结论无向图度TD(v) 依附于v的边数所有顶点的度之和 2|E|有向图入度ID(v) 以v为终点的边数出度OD(v) 以v为起点的边数所有顶点的入度之和 出度之和 |E|注符号含义对照表符号含义类型举例E边集Edge Set集合E {(A,B), (B,C)}|E|边的条数数字|E| 2很多人会偷懒直接用E表示边数但它本质上是|E|。顶点v的度TD(v) ID(v) OD(v)4. 路径与回路术语定义路径顶点序列v₀, v₁, …, vₙ路径长度路径上边的数量回路环第一个顶点和最后一个顶点相同的路径简单路径路径中顶点不重复出现简单回路除首尾外其余顶点不重复的回路距离从u到v的最短路径的长度不存在则为∞若一个图有n个顶点且有大于n-1条边则此图一定有环。5. 子图若V ⊆ V且E ⊆ E则称G是G的子图。类型定义生成子图满足V(G) V(G)的子图并非V和E的任何子集都能构成子图——E中的边关联的顶点必须在V中。6. 连通性无向图术语定义连通从v到w存在路径连通图图中任意两个顶点都是连通的连通分量无向图中的极大连通子图若一个图有n个顶点边数少于n-1则此图必然是非连通的。7. 强连通性有向图术语定义强连通从v到w和从w到v都有路径强连通图图中任意一对顶点都是强连通的强连通分量有向图中的极大强连通子图有向图强连通的最少边数n条形成一个环8. 生成树与生成森林术语定义生成树连通图的极小连通子图包含所有顶点和n-1条边生成森林非连通图中每个连通分量的生成树共同构成区分极大连通子图连通分量要求包含尽可能多的顶点和边极小连通子图生成树要求保持连通且边数最少。9. 其他术语术语定义完全图无向|E| n(n-1)/2有向|E| n(n-1)稀疏图/稠密图|E| n log₂n视为稀疏图网边上带有权值的图有向树一个顶点的入度为0其余顶点的入度均为1的有向图二、图的存储及基本操作2.1 邻接矩阵法#define MaxVertexNum 100 typedef struct { VertexType vex[MaxVertexNum]; // 顶点表 EdgeType edge[MaxVertexNum][MaxVertexNum]; // 邻接矩阵边表 int vexnum, arcnum; // 当前顶点数和边数 } MGraph;特点图类型邻接矩阵特点无向图一定是对称矩阵第i行列非零元素个数 顶点i的度有向图第i行非零元素个数 出度第i列 入度重要结论空间复杂度O(n²)判断两点是否有边O(1)确定图中边数需遍历整个矩阵稠密图适合邻接矩阵Aⁿ[i][j] 从i到j长度为n的路径数量2.2 邻接表法#define MaxVertexNum 100 typedef struct ArcNode { // 边表结点 int adjvex; // 邻接点位置 struct ArcNode *nextarc; // 下一条边的指针 // InfoType info; // 网边权值 } ArcNode; typedef struct VNode { // 顶点表结点 VertexType data; // 顶点信息 ArcNode *firstarc; // 第一条边 } VNode, AdjList[MaxVertexNum]; typedef struct { AdjList vertices; // 邻接表 int vexnum, arcnum; // 顶点数和边数 } ALGraph;特点图类型空间复杂度特点无向图O(n 2|E|)每条边出现两次有向图O(n |E|)—稀疏图适合邻接表找所有邻接点邻接表高效邻接矩阵需扫描整行判断两点是否有边邻接表需遍历边表效率较低有向图入度需遍历所有顶点的边表邻接表的表示不唯一取决于输入顺序2.3 十字链表有向图每条弧用一个弧结点表示每个顶点用一个顶点结点表示。弧结点结构顶点结点结构优点容易找到以v为尾的弧出度和以v为头的弧入度2.4 邻接多重表无向图每条边只用一个结点表示解决了邻接表中一条边用两个结点表示的问题。边结点结构顶点结点结构优点判断边是否存在只需遍历一次2.5 四种存储方式对比存储方式空间复杂度找相邻边删除边/顶点适用场景表示唯一性邻接矩阵O(n²)遍历行/列O(n)删边方便删顶点需移动数据稠密图唯一邻接表无向O(n2|E|)有向O(n|E|)方便不方便稀疏图不唯一十字链表O(n|E|)方便方便有向图不唯一邻接多重表O(n|E|)方便方便无向图不唯一三、图的遍历3.1 广度优先搜索BFS类似于树的层序遍历借助队列实现按路径长度递增的顺序访问顶点。bool visited[MAX_VERTEX_NUM]; void BFSTraverse(Graph G) { for (int i 0; i G.vexnum; i) visited[i] FALSE; InitQueue(Q); for (int i 0; i G.vexnum; i) if (!visited[i]) BFS(G, i); } void BFS(ALGraph G, int i) { visit(i); visited[i] TRUE; EnQueue(Q, i); while (!QueueEmpty(Q)) { DeQueue(Q, v); for (ArcNode *p G.vertices[v].firstarc; p; p p-nextarc) { w p-adjvex; if (!visited[w]) { visit(w); visited[w] TRUE; EnQueue(Q, w); } } } }性能分析空间复杂度O(n)辅助队列时间复杂度邻接表O(n |E|)邻接矩阵O(n²)BFS求单源最短路径非带权图void BFS_MIN_Distance(Graph G, int u) { for (int i 0; i G.vexnum; i) d[i] ∞; visited[u] TRUE; d[u] 0; EnQueue(Q, u); while (!QueueEmpty(Q)) { DeQueue(Q, u); for (w FirstNeighbor(G, u); w 0; w NextNeighbor(G, u, w)) if (!visited[w]) { visited[w] TRUE; d[w] d[u] 1; EnQueue(Q, w); } } }广度优先生成树邻接矩阵存储生成树唯一邻接表存储生成树可能不唯一3.2 深度优先搜索DFS类似于树的先序遍历借助递归栈实现遵循“尽可能深”地探索的策略。bool visited[MAX_VERTEX_NUM]; void DFSTraverse(Graph G) { for (int i 0; i G.vexnum; i) visited[i] FALSE; for (int i 0; i G.vexnum; i) if (!visited[i]) DFS(G, i); } void DFS(ALGraph G, int i) { visit(i); visited[i] TRUE; for (ArcNode *p G.vertices[i].firstarc; p; p p-nextarc) { j p-adjvex; if (!visited[j]) DFS(G, j); } }性能分析空间复杂度O(n)递归工作栈时间复杂度邻接表O(n |E|)邻接矩阵O(n²)深度优先生成树/森林连通图一棵生成树非连通图生成森林3.3 图的遍历与连通性图类型遍历特点无向图调用BFS/DFS的次数 连通分量数有向图一次遍历不一定能访问所有顶点需外层循环确保全覆盖四、思考1. 邻接矩阵 ≈ 城市之间的直达航班表行是出发城市列是到达城市单元格填1表示有直达航班。对角线是自己的城市0矩阵对称表示往返都有航班。2. 邻接表 ≈ 微信好友列表每个用户有一个好友列表边表只存储自己的好友不存储非好友关系。空间利用率高。3. BFS ≈ 六度分隔理论你认识的朋友是第一层朋友的朋友是第二层……BFS正是按这个层层递进的顺序探索“社交网络”中的人际关系。4. DFS ≈ 走迷宫沿着一条路一直走走到死胡同就退回上一个岔路口换一条路继续走直到走遍所有路。注以上内容参考 2027年数据结构考研复习指导 王道论坛 组编其中有一些个人想法如有任何错误或不妥欢迎各位大佬指出如果各位有一些有意思的想法也可以和我交流一下~感谢五、明日计划图下— 最小生成树、最短路径、拓扑排序、关键路径