大话数据结构 p7 - DDL-Killer/The-road-of-Linxu-Group2024 GitHub Wiki
- 图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合
- 在图中数据元素，我们把数据元素称为顶点
- 顶点集合有穷非空
- 任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示
- 无向边：若顶点vi到vj之间的边没有方向，则称这条边为无向边，用无序偶对(vi,vj)来表示；若任意两个顶点之间的边都是无向边，则该图为无向图，链接AD的边可以表示为(A,D)或(D,A)
- 有向边：若顶点vi到vj的边有方向，则称这条边为有向边，也称为弧，用有序偶<vi,vj>来表示，vi为弧尾，vj为弧头，若任意两个顶点之间的边都是有向边，则该图为有向图，链接AD的有向边就是弧，<A,D>表示弧
- 无向边用()，有向边用<>
- 在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图
- 在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图，无向完全图，n个顶点，有 n*(n-1)/2 条边
- 在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图
- 有很少条边或弧的图称为稀疏图，反之为稠密图
- 与图的边或弧相关的数叫做权
- 带权的图通常称为网
- 假设有两个图，如果G'的顶点集和边集都是G的顶点集和边集的子集，则称G'为G的子图
- 对于无向图，如果边在无向图边集内，则称两个顶点互为邻接点，两顶点相邻接，边依附于两顶点，边于两顶点相关联，顶点的度是和顶点相关联的边的数目，记为TD(v)
- 对于有向图，如果弧在有向图边集内，则称弧尾邻接到到弧头，弧头邻接自弧尾，弧和两顶点相关联，以一个顶点为头的弧的数目称为入度ID(v)，以一个顶点为尾的弧的数目称为出度OD(v)，顶点的度为TD(v)=ID(v)+OD(v)
- 无向图G=(V,{E})中从顶点v到v'的路径是一个顶点序列
- 路径的长度是路径上边或弧的数目
- 第一个顶点到最后一个顶点相同的路径称为回路或环。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其他顶点不重复出现的回路，称为简单回路或简单环
- 在无向图G中，如果从顶点v到顶点v'有路径，则称v和v'是连通的。如果对于图中任意两个顶点都是连通的，则称G是连通图
- 无向图中的极大连通子图称为连通分量
- 在有向图G中，如果对于每一对vi、vj属于V，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图
- 有向图中的极大强连通子图称做有向图的强连通分量
- 一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个项点，但足以构成一棵树的n-1条边
- 如果一个有向图恰有一个项点的入度为0，其余项点的入度均为1，则是一棵有向树
- 一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧
- 图按照有无方向分为无向图和有向图。无向图由顶点和边构成，有向图由顶点和弧构成。弧有弧尾和弧头之分
- 图按照边或弧的多少分为稀疏图和稠密图，任意两个顶点之间都存在边叫做完全图，有向的叫做有向完全图，无重复的边或顶点到自身的边叫简单图
- 图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度，顶点分为入度和出度
- 图上的边或弧上带权称为网
- 图中顶点之间存在路径，存在路径是连通的，最终回到起始点称为环，不重复叫做简单路径，任意连通则称连通图，有向为强连通图，有子图，极大连通为连连通分量，有向的则称强连通分量
- 无向图中连通n个顶点n-1条边叫做生成树，一顶点入度为0其余项点入度为1为有向树，一个有向图由若干棵有向树构成生成森林
- 邻接矩阵
- 图的邻接矩阵存储方式是用两个数组来表示图，一个一维数组存储图中的项点信息，一个二维数组存储图中的边或弧的信息
- 无向图的边数组是一个对称矩阵
- 对于有向图，横轴和代表出度，纵轴和代表入度
- n个顶点和e条边的无向图的构建，时间复杂度是O(n+n*n+e)
- 邻接表
- 数组与链表相结合的存储方式称为邻接表
处理方式：
- 顶点用一个一维数组存储
- 每个顶点所有的邻接点构成线性表
- 若是有向图，只给顶点建立一个链接顶点为弧头的表，用逆邻接表
- n个顶点e条边，O(n+e)
- 十字链表
- 边集数组是由两个一维数组构成。一个是存储项点的信息；另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标、终点下标和权构成
- DFS
- 从图中某个顶点v开始，访问此项点，然后从v的未别访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到
- 若图中尚有项点未被访问，则另选图中一个未曾被访问的项点作起始点，重复上述过程，直至图中所有的项点都被访问为止
- 链表
- BFS
- 使用队列：BFS通常使用队列来存储待访问的节点。
- 访问节点：从队列中取出节点，标记为已访问，并执行相应的操作（如打印节点）。
- 入队邻接节点：将当前节点的所有未访问的邻接节点加入队列。
- 重复：重复上述步骤，直到队列为空。
- 邻接矩阵
- 邻接表
- 普利姆算法从任意一个顶点开始，逐步构建最小生成树。它的核心思想是不断从现有的生成树中扩展到未包含的顶点，选择权重最小的边。每一步都选择一条边，将一个新的顶点加入生成树，直到所有顶点都被纳入生成树为止。
- 时间复杂度O(n²)
- 将图中的所有边按权重从小到大进行排序。
- 从最小的边开始，逐条检查是否可以加入生成树。如果加入该边不会形成环，就将其纳入生成树中。
- 重复步骤 2，直到生成树包含所有顶点（即包含 𝑉−1 条边，V 是顶点数）。
在克鲁斯卡尔算法中，避免形成环的过程通常通过并查集（Union-Find）来实现，用于动态维护已经加入生成树的顶点和边
- 时间复杂度由边数e决定，O(elog e)，边数少的效率高
- 最短路径是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点
- 初始化
首先，算法会创建两个集合：已确定最短路径的节点集合和未确定最短路径的节点集合。初始状态下，只有源节点的最短路径长度为零，其余所有节点的路径长度都被设置为“无穷大”表示未知路径。
- 找出距离最短的节点
在未确定最短路径的节点中，选择一个到源节点距离最小的节点，这一步保证我们逐步找到最短路径。因为这个节点已经是当前未访问节点中的最小距离，因此我们可以认为它的最短路径已经确定。
- 更新相邻节点的距离
对于刚确定的节点，检查它的所有邻居节点，更新这些节点到源节点的距离。具体来说，如果通过当前节点到达某个邻居节点的路径比当前记录的路径要短，那么更新这个邻居节点的路径长度，并记录路径来源节点。
- 重复选择与更新
重复步骤 2 和 3，不断从未访问节点中选择距离最小的节点，并更新其相邻节点的最短路径，直到所有节点都确定了最短路径，或者无法继续找到更短路径为止。
- 输出结果
当算法结束时，源节点到其他所有节点的最短路径长度都已经确定。如果需要显示路径，也可以通过记录的路径来源节点逐步回溯出完整路径。
- 实现
- 初始化距离矩阵：首先，我们将图中的距离信息存储到一个矩阵中，称为“距离矩阵”。矩阵中的值表示直接连接的边的权重。如果两个节点之间没有直接连接，距离设为无穷大（表示不可达）。
- 动态更新路径：接着，通过将每个节点依次作为“中间节点”，检查通过这个节点到达其他节点的路径是否更短。具体来说，假设有三个节点 i、j、k：
- 如果从 i 到 j 的直接路径比从 i 经过 k 再到 j 的路径长，则不更新。
- 如果从 i 到 j 经过 k 的路径更短，那么更新距离矩阵的值，将 i 到 j 的距离更新为经过 k 的最短路径。
- 循环遍历每个节点：将所有节点依次作为中间节点，反复更新每对节点间的距离矩阵，直到找出最短路径。
- 最终结果：经过所有节点的迭代更新后，距离矩阵中的每个元素会显示图中任意两节点间的最短路径长度
- 在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网
- 设G=(V,E)是一个具有n个顶点的有向图,V中的顶点序列v1，v2...vn,满足若从vi到vj有一条路径，则在顶点序列中顶点vi必须在vj之间，则我们称这样的顶点序列是一个拓扑序列
- 一个AOV网，拓扑序列不唯一
- 所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程
- 基本思路：从AOV网中选一个入度为0的顶点输出，然后删除此顶点，并删除以此顶点为尾的弧，直到输出全部顶点，或者AOV网中不存在入度为0的顶点为止
- 为AOV网建立一个邻接表，在原来顶点表结点结构中，增加一个入度域in，in就是入度的数字
- 用栈结构存储入度为0的顶点下标
- 结构代码
- 完整代码
- 时间复杂度O(n+e)
- 在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，我们称之为AOE网
- 路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大的长度的路径叫关键路径，关键路径上的活动叫做关键活动
- 我们需要找到所有活动的最早开始时间和最晚开始时间，并且比较它们，如果相等就意味着此活动是关键活动，活动间的路径为关键路径
⚠️ **GitHub.com Fallback** ⚠️