数据结构（四）———

1. 无向图与有向图

1.1 定义

无向图：边是无方向的，用(顶点, 顶点)表示边
有向图：边（称为 “弧”）是有方向的，用<弧尾, 弧头>表示方向

2. 连通图

2.1 连通的定义

在无向图中，若从顶点v到顶点w存在路径，则称v到w是连通的。

2.2 连通图的定义

若图中任意两个顶点都连通，则称此图为连通图。

3. 完全图

3.1 定义

具有最多边数的图称为完全图。

3.2 边数公式

无向完全图（n 个顶点）：边数最大值为n(n-1)/2。
有向完全图（n 个顶点）：边数最大值为n(n-1)。

4. 路径与回路

4.1 路径

从一个顶点出发，经过一系列边到达另一个顶点的顶点序列。

4.2 路径长度

路径上包含的边的条数。

4.3 回路（环）

起点和终点相同的路径

5. 简单路径与简单回路

5.1 简单路径

路径中不出现重复顶点的路径

5.2 简单回路

除起点和终点外，其余顶点不重复出现的回路。

6. 顶点的度

6.1 无向图的度

顶点关联的边的数目。

6.2 有向图的度

入度：箭头指向该顶点的边的数目。
出度：从该顶点出发的边的数目。

7. 度与边的关系

7.1 无向图

所有顶点的度之和 = 边数 × 2（每条边关联 2 个顶点）。

7.2 有向图

所有顶点的出度之和 = 入度之和 = 弧的数量（每条弧对应 1 个出度和 1 个入度）。

8. 子图

8.1 定义

若图H满足：

10. 强连通图与强连通分量

10.1 强连通图（有向图）

在有向图中，若每一对顶点 v 和 w 之间，从 v 到 w、从 w 到 v 都存在路径，则称该有向图为强连通图。

10.2 强连通分量

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

11. 生成树

11.1 定义

包含图中全部顶点的极小连通子树（“极小” 指边数最少）。

11.2 核心特征

若图有 n 个顶点，则生成树恰好有n-1条边（足够构成树的最少边数）。

12. 边的权与网

12.1 边的权

图中每条边标注的、代表特定含义的数值（如距离、成本）。

12.2 网（带权图）

边上带有权值的图，也称为带权图。

13. 图的存储结构

13.1 邻接矩阵

13.1.1 无向图的邻接矩阵

13.1.2 有向图的邻接矩阵

13.1.3 带权图的邻接矩阵

13.2 邻接表

13.2.1 无向图的邻接表

顶点集V(H)是原图G顶点集V(G)的子集；
边集E(H)是原图G边集E(G)的子集；则称H是G的子图。
9. 连通分量

9.1 定义（无向图）

无向图中的极大连通子图称为连通分量，需满足：

是原图的子图；
自身是连通图；
包含尽可能多的顶点（无法再添加原图其他顶点仍保持连通）；
包含依附于这些顶点的所有边。
用二维数组存储边的关系：若顶点Vi与Vj相邻，则matrix[i][j] = 1（无向图矩阵是对称的）；
同时需维护一个 “顶点数组” 存储顶点信息。
用二维数组存储边的方向：若存在从Vi到Vj的弧，则matrix[i][j] = 1（矩阵不一定对称）；
可通过矩阵行 / 列统计顶点的出度 / 入度。
若顶点Vi到Vj有边，matrix[i][j] = 权值；
无边时用∞（无穷大）表示，顶点自身到自身用0表示。
结构：由 “顶点数组”+“链表” 组成；
- 顶点数组：每个元素存储顶点信息，同时指向一个链表；
- 链表：存储该顶点的所有邻接顶点（无向图中，一条边会在两个顶点的链表中各存一次）；
特点：链表中邻接顶点的顺序可灵活调整。

13.2.2 有向图的邻接表

结构：与无向图邻接表类似（顶点数组 + 链表）；
特点：链表中仅存储从当前顶点出发的邻接顶点（即表示 “出边”）；

13.3 逆邻接表

13.3.1 定义

针对有向图的存储结构，链表中存储指向当前顶点的邻接顶点（即表示 “入边”）；

13.2.3 带权有向图的邻接表

结构：在有向图邻接表的基础上，链表节点增加 “权值” 字段；

13.3.3 带权有向图的逆邻接表（扩展）

逻辑：链表节点同时存储 “入边的邻接顶点” 和 “对应权值”，用于快速统计顶点的入边及权值；
特点：与带权邻接表对应，仅存储方向为 “指向当前顶点” 的边信息。

13.4 十字链表

13.4.1 适用场景

用于存储有向图，可同时高效管理 “出边” 和 “入边”。

13.4.2 结构组成

顶点结构：包含 3 个字段
- data：顶点数据；
- firstin：入边链表的表头指针；
- firstout：出边链表的表头指针。
边结构：包含 4 个字段
- tailvex：边的弧尾（起点）顶点下标；
- headvex：边的弧头（终点）顶点下标；
- headlink：指向同一弧头的下一条边；
- taillink：指向同一弧尾的下一条边。

13.4.3 核心特点

一条边会同时出现在 “弧尾顶点的出边链表” 和 “弧头顶点的入边链表” 中，形成 “十字交叉” 的链表结构，便于同时遍历入边和出边。

13.5 邻接多重表

13.5.1 适用场景

用于存储无向图，解决邻接表中 “一条边存储两次” 的冗余问题。

13.5.2 结构组成

边结构包含 4 个字段：
- ivex/jvex：边连接的两个顶点下标；
- ilink：指向与ivex相连的下一条边；
- jlink：指向与jvex相连的下一条边。

13.5.3 核心特点

一条边仅存储一次，通过ilink和jlink分别关联两个顶点的邻接边，避免冗余存储。

14. 图的遍历

14.1 深度优先搜索（DFS）

14.1.1 核心思想

“不撞南墙不回头”：从起始顶点出发，优先访问未访问的邻接顶点，直到无法前进时回溯，继续访问其他邻接顶点。

14.1.2 连通分量关联

对于非连通无向图，执行 DFS 的次数 = 图的连通分量数。

14.2 广度优先搜索（BFS）

14.2.1 核心思想

“层层扩散”：从起始顶点出发，先访问当前顶点的所有未访问邻接顶点（一层），再依次访问这些邻接顶点的邻接顶点（下一层）。

14.2.2 实现方式（邻接矩阵版代码逻辑）

1void bfs(Mat_Graph G) {
2    int i = 0;
3    visited[i] = 1; // 标记起始顶点已访问
4    printf("%c\n", G.vertex[i]); // 输出顶点
5    queue[rear] = i; rear++; // 起始顶点入队
6    while (front != rear) { // 队列非空
7        i = queue[front]; front++; // 队首顶点出队
8        for (int j = 0; j < G.vertex_num; j++) { // 遍历所有邻接顶点
9            if (G.arc[i][j] == 1 && visited[j] == 0) { // 邻接且未访问
10                visited[j] = 1;
11                printf("%c\n", G.vertex[j]);
12                queue[rear] = j; rear++; // 入队
13            }
14        }
15    }
16}
17

14.2.3 连通分量关联

对于非连通无向图，执行 BFS 的次数 = 图的连通分量数。

十字链表与邻接多重表的存储效率需结合图的类型（有向 / 无向） 与操作场景判断，二者空间复杂度均为 O (|V|+|E|)，但单条边 / 弧的存储开销、操作效率存在差异。以下是分场景的结论与对比：

核心结论

有向图场景：十字链表存储效率更高。它能同时高效管理出边与入边，单条弧仅存 1 个节点，避免逆邻接表的冗余，且入 / 出边查询与增删更高效。
无向图场景：邻接多重表存储效率更高。它将无向边仅存 1 个节点，避免邻接表 “一条边存两次” 的冗余，边的增删改只需操作 1 个节点，空间与时间开销更低。
通用对比：二者空间复杂度同级，但十字链表的顶点与弧节点指针更多（顶点含 firstin/firstout，弧含 headlink/taillink），单节点内存开销略高于邻接多重表；邻接多重表边节点指针更少，更适合无向图的边操作密集场景。

详细对比表（含存储与操作效率）

对比维度	十字链表	邻接多重表
适用场景	仅用于有向图，适合需频繁处理入 / 出边的场景	仅用于无向图，适合需频繁增删边、避免冗余的场景
空间复杂度	O(	V	+	E	)，单弧 1 个节点，顶点双指针、弧 4 字段	O(	V	+	E	)，单无向边 1 个节点，顶点单指针、边 4 字段
单节点开销	顶点：data+firstin+firstout；弧：tailvex+headvex+headlink+taillink，指针多	顶点：data+firstedge；边：ivex+jvex+ilink+jlink，指针少
边 / 弧存储	有向图中每条弧仅存 1 次，无冗余	无向图中每条边仅存 1 次，无邻接表的双向冗余
查询效率	入边 / 出边可通过 firstin/firstout 快速遍历，效率高	需遍历顶点的边链表找相邻边，效率与十字链表同级
增删效率	增删弧需同时维护出边与入边链表，逻辑较复杂	增删边仅需修改 1 个边节点的指针，操作更高效

关键原因

结构适配性：十字链表为有向图设计，天然适配 “入 / 出边分离” 的特性，解决邻接表查入度低效、逆邻接表查出入边需双表的问题。
冗余控制：邻接多重表针对无向图 “边无方向” 的特点，用 1 个边节点关联两个顶点，避免邻接表的双向存储冗余，边操作更简洁。
指针开销：十字链表的双指针设计虽提升有向图操作效率，但单节点内存开销略高；邻接多重表指针更少，无向图场景下整体更经济。

15. 最小生成树

15.1 普里姆（Prim）算法

15.1.1 核心思想

“从顶点出发，逐步扩张”：以某一顶点为起点，每次选择已选顶点集合与未选顶点集合之间权值最小的边，将对应的未选顶点加入已选集合，直到覆盖所有顶点。

15.1.2 实现逻辑（邻接矩阵版代码）

1void prim(Mat_Graph* G) {
2    int i, j, k;
3    int min;
4    int weight[MAXSIZE]; // 存储候选边的权值
5    int vex_index[MAXSIZE]; // 存储候选边的起点（下标为终点）
6
7    // 初始化：从顶点0（A）开始
8    weight[0] = 0; 
9    vex_index[0] = 0;
10    for (i = 1; i < G->vertex_num; i++) {
11        weight[i] = G->arc[0][i]; // 初始候选边为顶点0到各顶点的权值
12        vex_index[i] = 0;
13    }
14
15    // 迭代选择n-1条边（生成树边数=顶点数-1）
16    for (int i = 1; i < G->vertex_num; i++) {
17        min = MAX; // 初始化最小权值为无穷大
18        j = 0; k = 0;
19        // 找到当前候选边中权值最小的边
20        while (j < G->vertex_num) {
21            if (weight[j] != 0 && weight[j] < min) {
22                min = weight[j];
23                k = j; // k为选中的终点
24            }
25            j++;
26        }
27        // 输出选中的边（起点-终点）
28        printf("(%c, %c)\n", G->vertex[vex_index[k]], G->vertex[k]);
29        weight[k] = 0; // 标记该顶点已加入生成树
30
31        // 更新候选边：用新加入顶点的边替换原有更大的权值
32        for (j = 0; j < G->vertex_num; j++) {
33            if (weight[j] != 0 && G->arc[k][j] < weight[j]) {
34                weight[j] = G->arc[k][j];
35                vex_index[j] = k;
36            }
37        }
38    }
39}
40

15.2 克鲁斯卡尔（Kruskal）算法

15.2.1 核心思想

“从边出发，按权值排序”：将所有边按权值从小到大排序，依次选择边，若该边的两个顶点不在同一连通分量中，则加入生成树，直到覆盖所有顶点（避免环）

《数据结构（四）————图》是转载文章，点击查看原文。

数据结构（四）————图