37_数据结构——图

一、图的基本概念1. 图的定义(1) 图的逻辑结构a. 非线性结构i. 节点之间具有多对多的关系⓵ 图由顶点集和边集组成(2) 形式化表示KaTeX parse error: Expected EOF, got at position 4: ̲emsp;emsp;ems…其中VVV是顶点集合EEE是边集合2. 图的基本术语(1) 顶点相关a. 邻接点b. 顶点的度i. 入度与出度有向图(2) 边相关a. 无向边与有向边b. 权值i. 稀疏图与稠密图3. 图的分类(1) 按边的方向a. 无向图b. 有向图(2) 按边的权值a. 无权图b. 有权图网(3) 按连通性a. 连通图b. 非连通图i. 连通分量二、图的数学表示1. 邻接矩阵(1) 定义KaTeX parse error: Expected EOF, got at position 4: ̲emsp;emsp;ems…(2) 性质a. 无向图的邻接矩阵对称b. 空间复杂度O(∣V∣2)O(|V|^2)O(∣V∣2)2. 邻接表(1) 定义a. 每个顶点维护一个邻接链表i. 空间复杂度O(∣V∣∣E∣)O(|V| |E|)O(∣V∣∣E∣)(2) 存储结构/** Allman 风格*/KaTeX parse error: Expected EOF, got at position 4: ̲emsp;emsp;ems…3. 其他存储方式(1) 十字链表有向图(2) 邻接多重表无向图三、图的遍历1. 深度优先搜索(1) 算法思想a. 沿着一条路径走到尽头b. 回溯后继续探索未访问节点(2) 时间复杂度a. 邻接矩阵O(∣V∣2)O(|V|^2)O(∣V∣2)b. 邻接表O(∣V∣∣E∣)O(|V| |E|)O(∣V∣∣E∣)(3) 递归实现/** Allman 风格*/KaTeX parse error: Expected EOF, got at position 4: ̲emsp;emsp;ems…2. 广度优先搜索(1) 算法思想a. 逐层向外扩展b. 使用队列辅助(2) 时间复杂度a. 邻接矩阵O(∣V∣2)O(|V|^2)O(∣V∣2)b. 邻接表O(∣V∣∣E∣)O(|V| |E|)O(∣V∣∣E∣)(3) 实现框架/** Allman 风格*/KaTeX parse error: Expected EOF, got at position 4: ̲emsp;emsp;ems…四、图的最短路径问题1. 单源最短路径(1) Dijkstra 算法a. 适用于非负权图b. 贪心策略i. 时间复杂度O(∣V∣2)O(|V|^2)O(∣V∣2)或O(∣E∣log⁡∣V∣)O(|E| \log |V|)O(∣E∣log∣V∣)(2) Bellman-Ford 算法a. 可处理负权边b. 可检测负环i. 时间复杂度O(∣V∣⋅∣E∣)O(|V| \cdot |E|)O(∣V∣⋅∣E∣)(3) SPFA 算法a. Bellman-Ford 的队列优化2. 多源最短路径(1) Floyd-Warshall 算法a. 动态规划b. 状态转移方程KaTeX parse error: Expected EOF, got at position 4: ̲emsp;emsp;ems…i. 时间复杂度O(∣V∣3)O(|V|^3)O(∣V∣3)五、图的最小生成树1. 生成树的概念(1) 包含所有顶点的连通子图a. 边数为∣V∣−1|V| - 1∣V∣−1i. 无环2. Prim 算法(1) 算法思想a. 每次选择距离当前集合最近的点b. 贪心策略(2) 时间复杂度a. 邻接矩阵O(∣V∣2)O(|V|^2)O(∣V∣2)b. 二叉堆优化O(∣E∣log⁡∣V∣)O(|E| \log |V|)O(∣E∣log∣V∣)3. Kruskal 算法(1) 算法思想a. 按边权从小到大选择b. 并查集判断环(2) 时间复杂度a. 边排序O(∣E∣log⁡∣E∣)O(|E| \log |E|)O(∣E∣log∣E∣)b. 并查集操作近似O(1)O(1)O(1)六、图的拓扑排序1. 定义与条件(1) 针对有向无环图a. 将顶点线性排序i. 若存在边u→vu \to vu→v则uuu排在vvv之前2. 算法实现(1) Kahn 算法a. 基于入度i. 不断删除入度为000的顶点(2) 基于 DFS 的方法a. 后序遍历逆序输出七、图的关键路径1. 基本概念(1) AOE 网a. 顶点表示事件b. 边表示活动i. 权值表示活动持续时间2. 关键路径计算(1) 事件的最早发生时间(2) 事件的最迟发生时间(3) 活动的时间余量i. 余量为000的活动构成关键路径八、图的应用场景1. 社交网络(1) 用户关系图a. 好友推荐b. 社区发现2. 交通网络(1) 最短路径规划(2) 物流配送优化3. 计算机网络(1) 路由算法a. OSPF 协议b. RIP 协议4. 任务调度(1) 拓扑排序确定执行顺序(2) 关键路径确定项目工期5. 机器学习(1) 图神经网络(2) 知识图谱6. 电路设计(1) 电路布线(2) 逻辑电路优化