当前位置：首页 > article >正文

数据结构6-图

article 2025/3/30 22:01:35

图的基本概念

顶点的度

与该顶点相关联的边的数目，记为 TD(v)

在有向图中，顶点的度等于该顶点的入度与出度之和。

顶点 v 的入度是以 v 为终点的有向边的条数，记作 ID(v)

顶点 v 的出度是以 v 为起点的有向边的条数，记作 OD(v)

路径：

路径、回路及相关概念

路径连续的边构成的顶点序列。

路径长度 路径上边或弧的数量/权值之和。

回路（环） 第一个顶点和最后一个顶点相同的路径。

简单路径 除路径起点和终点可以相同外，其余顶点均不相同的路径。

简单回路（简单环） 除路径起点和终点相同外，其余顶点均不相同的路径。

路径的分类

简单路径路径中的顶点不重复。

非简单路径路径中存在重复的顶点。

回路（环）起点和终点相同，形成封闭路径。

连通图：

在无向图或有向图G=(V, E)中，若对任意两个顶点v,u 都存在从 v 到 u 的路径，则称G 是连通图（强连通图）。

子图：

设有两个图 G=(V,E)、G1=(V1,E1)，若 V1⊆V 且 E1⊆E，则称 G1 是 G 的子图。(b)、(c) 是 (a) 的子图

无向图连通分量：

无向图 G 的极大连通子图称为 G 的连通分量。

极大连通子图：该子图是 G 的连通子图，若将 G 的任何不在该子图中的顶点加入，则子图不再连通。

左侧（非连通图）该图由两个独立的部分组成，不能通过一条路径连接所有点，因此是非连通图。

右侧（连通分量）通过连通分量的概念，将原始图拆分成两个连通的子图。一个子图包含V0,V1,V2,V3。另一个子图包含V4,V5。

有向图强连通分量：

有向图 G 的极大强连通子图称为 G 的强连通分量。

极大强连通子图的意思是：该子图是 G 的强连通子图，若将 G 的任何不在该子图中的顶点加入，则子图不再是强连通的。

左侧（有向图）该图包含多个有向边，部分顶点可以互相到达，但不是所有顶点之间都存在路径。

右侧（强连通分量）该图被分成了两个强连通分量：V0,V2,V3 组成一个强连通分量，因为在这三个顶点之间，存在双向的可达路径。V1 作为单独的一个强连通分量，因为它无法到达其他顶点，其他顶点也无法到达它。

极小子图，生成树：

极小连通子图该子图是 G 的连通子图，在该子图中删除任何一条边，子图不再连通。

生成树包含无向图 G 所有顶点的极小连通子图。

生成森林对于非连通图，由各个连通分量的生成树的集合组成。

左侧（连通图）该图是连通的，所有顶点之间至少存在一条路径。

右侧（生成树）该图保留了所有顶点，但删除了一些边，使其仍然连通但不形成回路。生成树是极小的，即它不含任何多余的边，同时确保所有顶点仍然连通。

图的存储结构(数组表示法、邻接表表示法)

数组（邻接矩阵）表示法

建立一个：顶点表（记录各个顶点的信息）邻接矩阵（表示各个顶点之间的关系）

邻接矩阵是 n×n 的矩阵：

A[i][j]=1 表示顶点 Vi 和 Vj 之间有一条边。

A[i][j]=0 表示两顶点之间没有边。

适用场景：稠密图（边比较多的图）。快速查询 顶点之间是否有边（O(1) 复杂度）。

对于一个无向图 G：

设 G 有 n 个顶点，记作 V1,V2,...,Vn。

邻接矩阵 A 是一个 n×n 的方阵，其中：

无向图的邻接矩阵是对称的，即：

有无向图，邻接矩阵如下：

有向图数组表示法（邻接矩阵）：

对于一个有向图 G：

设 G 有 n 个顶点，记作 V1,V2,...,Vn。

邻接矩阵 A 是一个 n×n 的二维数组，其中：

有向图的邻接矩阵一般是不对称的，即：

有向图，邻接矩阵如下：

顶点的出度=第i行元素之和

顶点的入度=第i列元素之和

顶点的度=第i行元素之和+第i列元素之和

无向图邻接表表示法（）：

邻接表是一种适用于 稀疏图（边数较少）的数据结构，它使用链表存储与某个顶点相邻的顶点。

头结点（Vertex Node）每个顶点 vvv 存储在一个一维数组中：Vexs[n]。每个顶点都有一个头指针 firstarc，指向其邻接点链表的第一个节点。

表结点（Edge Node）每条边在链表结构中存储，每个邻接点包含：adjvex：存储相邻顶点的编号，nextarc：指向下一个邻接点（链表），info（可选）：可以存储边的权值或其他信息

性质：

邻接表不唯一因为链表存储的顺序可以不同，所以同一个图可能有不同的邻接表表示。

存储规模若无向图有 n 个顶点，e 条边，则：头结点数量 = n，表结点数量 = 2e （因为无向图的边被存储两次）

顶点的度顶点 vi 的度等于邻接链表中结点的个数，即：degree(vi) = 该顶点的邻接表中结点数

有向图邻接表表示法（只记录点的出度指针）：

有向图的邻接表与逆邻接表的区别，以及如何通过这两种结构计算顶点的出度和入度：

邻接表：

顶点 Vi 的出度：直接查看第 i 个链表的节点个数（即该顶点指向的顶点数量）。

顶点 Vi 的入度：需要遍历所有链表中值为 i−1 的节点（即其他顶点指向 Vi 的次数），效率较低。

逆邻接表：

顶点 Vi 的入度：直接查看第 i 个链表的节点个数（即指向该顶点的其他顶点数量）。

顶点 Vi 的出度：需要遍历所有链表中值为 i−1 的节点，效率较低。

图的深度优先搜索和广度优先搜索算法及简单应用

深度优先搜索（无节点可遍历就回退）：

DFS 的核心逻辑

深度优先：从起点出发，尽可能深地访问未探索的分支，直到尽头后回溯。

回溯机制：当某节点的所有邻接节点均被访问后，逐层返回上一层节点继续探索。

图中顶点从 V1 到 V8，可能的邻接关系如下（假设）：V1 连接 V2 和 V3，V2 连接 V4 和 V5，V4 连接 V8，V5 连接 V8，V3 连接 V6 和 V7，根据邻接关系，不同分支选择会导致不同的遍历顺序：

V1 ⇒ V2 ⇒ V4 ⇒ V8 ⇒ V5 ⇒ V3 ⇒ V6 ⇒ V7，V2 优先选择 V4 分支，再回溯到 V5。

V1 ⇒ V2 ⇒ V5 ⇒ V8 ⇒ V4 ⇒ V3 ⇒ V6 ⇒ V7，V2 优先选择 V5 分支，再回溯到 V4。

V1 ⇒ V3 ⇒ V6 ⇒ V7 ⇒ V2 ⇒ V4 ⇒ V8 ⇒ V5，V1 优先选择 V3 分支，再回溯到 V2。

DFS 与树的先根遍历的关联

相似性：DFS 对连通图的遍历顺序类似于树的先根遍历（Root-L-Child-R-Child）。

差异：图可能有环，需额外标记已访问节点以避免重复遍历。

为何存在多种遍历顺序？

邻接表顺序影响：若邻接表中节点的邻接点存储顺序不同（如 V2 的邻接表为 [V4, V5] 或 [V5, V4]），遍历顺序会不同。

实现策略：递归或栈的选择逻辑可能影响分支优先级。

广度优先搜索：

广度优先遍历（BFS）的核心逻辑

逐层访问：从起点开始，先访问所有直接邻接的顶点，再依次访问下一层邻接顶点。

队列结构：使用队列保存待访问顶点，按“先进先出”顺序处理。

避免重复：需标记已访问顶点，防止重复遍历。

在用户示例中的具体表现

BFS 遍历过程：

从 V1（索引 0）入队。

访问 V1，将其邻接点 V2（索引 1）入队。

访问 V2，将其邻接点 V3（索引 2）入队。

重复此过程，直到访问完 V8（索引 7）。

遍历结果：

V1 ⇒ V2 ⇒ V3 ⇒ V4 ⇒ V5 ⇒ V6 ⇒ V7 ⇒ V8。

比较复杂度：

时间复杂度

DFS：平均/最坏情况：O(V + E)，其中 V 为顶点数，E 为边数。

BFS：平均/最坏情况：O(V + E)，与 DFS 相同。

空间复杂度

DFS：最坏情况：O(V)（例如线性链式图）

BFS：最坏情况：O(V)（例如完全二叉树）

图遍历的应用:最小生成树、最短路径、拓扑排序、关键路径等

最小生成树：

给定无向网络，在该网的左右生成树中，使得各个边的权值之和最小的树称为最小生成树，也是最小代价生成树。

prim最小生成树：（最小生长树）

初始化：选择一个起始顶点，将其加入最小生成树中。

选择一个起始顶点。假设我们选择顶点1作为起始点。
将顶点1加入最小生成树中。

选择边：在所有连接已选顶点和未选顶点的边中，选择权重最小的边。

在所有连接已选顶点（目前只有顶点1）和未选顶点的边中，选择权重最小的边。
假设从顶点1出发，连接的边及其权重如下：
- 1-3: 权重3
- 1-4: 权重4
选择权重最小的边1-3。
......

添加顶点：将这条边连接的未选顶点加入最小生成树中。

将边1-3连接的未选顶点3加入最小生成树中。
现在，最小生成树包含顶点1和3。
......

重复：重复步骤2和3，直到所有顶点都被包含在最小生成树中。

kruscal最小生成树：（从小到大加边不成环）

使用克鲁斯卡尔算法构造树的步骤如下：

既然需要使得构造树的路径权值最小，可先将连通图中的所有路径拿出来，按照权值从小到的顺序进行排列。

然后后按照顺序将路径一条条地添加进节点之间，直到所有的节点都有被树连接。在这个过程中，我们需要避免环的产生，如下图，在添加权值为4的路径时，路径（1-3-4）与路径（3-4-7）均形成了环路。为了形成树，在第四步添加路径时，我们就需要通过判断成环而从树状图数据中剔除路径{1,3}及{4,7}。

比较：

思路

Prim算法：基于顶点的贪心算法。它从一个起始顶点开始，逐步扩展生成树，每次选择连接已选顶点和未选顶点的最小权重边。

Kruskal算法：基于边的贪心算法。它从所有边中选择权重最小的边，逐步构建生成树，确保不形成环。

实现

Prim算法：选择一个起始顶点。重复步骤，直到所有顶点都被包含在生成树中：选择连接已选顶点和未选顶点的最小权重边。将这条边连接的未选顶点加入生成树。

Kruskal算法：将所有边按权重从小到大排序。重复步骤，直到生成树包含所有顶点：选择当前最小权重的边。如果这条边连接的两个顶点不在同一集合中（即不形成环），则将其加入生成树，并合并这两个集合。

复杂度

Prim算法：使用二叉堆时，时间复杂度为 O(ElogV)，其中 E 是边数，V 是顶点数。

Kruskal算法：时间复杂度为 O(ElogE)，主要来自边的排序操作。

最短路径：

单源最短路径—用Dijkstra(迪杰斯特拉)算法：

初始化：

从源点 v0 出发，检查所有直达路径（即通过一条边直接到达的路径）。

记录这些路径的长度（如 v0→vk 的权值），未直接连接的路径视为无穷大。

选择最短路径：

从所有已记录的路径中，选择当前长度最短的路径，记为 v0→u。

此步骤确定 u 为当前离源点最近的节点，并将其标记为“已确定最短路径”。

更新路径：

检查节点 u 的所有邻接节点 vk，若存在边 (u,vk)，则尝试更新路径：

计算新路径长度：原路径(v0→u)+边权(u→vk)。

若该值小于当前记录的 v0→vk 的路径长度，则更新为更短的路径 v0→u→vk。

重复上述过程，选择下一个最短路径节点，直到所有节点均被处理。

所有顶点间的最短路径—用Floyd(弗洛伊德)算法：

初始邻接矩阵

初始状态下，用一个矩阵表示各点之间的距离：

直接相连的边使用对应权值

没有直接相连的顶点间距离设为 -（无穷大）

对角线（自身到自身）设为 0

Floyd算法的执行步骤

逐步加入中间节点（A、B、C）进行松弛操作：

先检查是否通过 A 可以更新任意两点间的最短路径。

再检查是否通过 B 可以进一步优化路径。

最后检查是否通过 C 进行最终优化。

如果加入的中间节点能让路径更短，就更新矩阵；否则保持原值。

最终最短路径矩阵

经过所有步骤后，矩阵中的值就是所有顶点对之间的最短路径长度。

右侧的路径表格记录了最短路径的具体走法，例如：

AB → ABC

CA → CAB

BCA（路径变更后出现）

拓扑排序：

AOV网（Activity On Vertex Network）

定义：使用有向图来表示一个工程的各个子工程及其相互制约的关系。

弧（边）表示活动之间的优先约束关系，即哪些活动必须先完成，哪些活动可以同时进行。

应用：适用于拓扑排序，用于确定任务的执行顺序。

aov拓扑排序（成环检测）：

拓扑排序的步骤

选择一个没有前驱（入度为 0）的顶点，并输出。
删除该顶点及所有以它为起点的边，更新图结构。
重复以上步骤，直到所有顶点都被输出。
如果图中仍然存在入度不为 0 的顶点，说明图中存在环，无法进行拓扑排序。

拓扑排序结果结果之一：C1, C2, C3, C4, C5, C7, C9, C10, C11, C6, C12, C8

不同的拓扑排序可能不唯一，这取决于：选择无前驱顶点的顺序不同。如果有多个无前驱顶点，可以按任意顺序选取，因此可能得到多个不同的排序结果。

关键路径：

AOE网（Activity On Edge Network）

定义：也是使用有向图表示工程及其约束关系，但方式不同。

顶点表示活动的起点或终点事件，即一个活动的开始和结束时刻。

应用：适用于关键路径法（CPM），用于计算项目的最短完成时间。

aoe关键路径：

步骤	计算公式	计算方式
计算 ve	ve(j)=max(ve(i)+wi,j)	从起点向前推进
计算 vl	vl(i)=min(vl(j)−wi,j)	从终点向后回溯
计算 e(i)	e(i)=ve(j)	任务最早开始时间
计算 l(i)	l(i)=vl(k)−wj,k	任务最晚开始时间
计算松弛时间	S(i)=l(i)−e(i)	S = 0 表示关键任务
找关键路径	关键活动的集合	形成关键路径