数据结构《图论》
图的性质
一、无向图（Undirected Graph）
- 定义
-
由一组顶点（Vertex）和一组无向边（Edge）构成。
-
每条无向边用一条无方向的线段连接两个顶点，记为 ( (u, v) )，其中 ( u ) 和 ( v ) 是顶点，且 ( u \neq v )。若允许自环，可表示为 ( (u, u) )。
- 核心性质
性质 定义与特点
- 核心性质
顶点集 记为 ( V )，大小为 ( V )。
边集 记为 ( E )，每条边是无序对 ( {u, v} \subseteq V )，大小为 ( E )。若允许多重边，则边可重复出现。
度（Degree） 顶点 ( u ) 的度为与之相连的边的数量，即 ( d(u) = \text{number of edges incident to } u )。无向图中每个边贡献度数 +1。
简单图 不含自环且不含多重边的无向图。
连通性 若两个顶点之间存在至少一条路径，则称它们是连通的；否则属于不同的连通分量（Connected Component）。
桥（Bridge） 若删除某条边后图的连通分量数目增加，则该边为桥。桥是图中唯一的连接两个部分的边。
割点（Articulation Point） 删除该顶点后图的连通分量数目增加，则该顶点为割点。
- 特殊类型
- 树（Tree）：无环且连通的无向图，满足 ( E = V - 1 )。
- 森林（Forest）：若干棵互不连通的树的集合。
- 完全图（Complete Graph）：每对顶点之间均存在一条边，记为 ( K_n )（( n ) 个顶点）。
- 环图（Cycle Graph）：所有顶点构成一个单一环，满足 ( E = V )。
二、有向图（Directed Graph）
- 定义
-
由一组顶点和一组有向边（Directed Edge）构成。
-
每条有向边用箭头表示方向，记为 ( (u, v) )，其中 ( u ) 是起点（Source），( v ) 是终点（Target）。允许自环（( u = v )）和多重边。
- 核心性质
性质 定义与特点
- 核心性质
顶点集 记为 ( V )，大小为 ( V )。
边集 记为 ( E )，每条边是有序对 ( (u, v) \subseteq V \times V )，允许重复边（多重边）。
入度（InDegree） 顶点 ( v ) 的入度为指向它的边的数量，即 ( d_{\text{in}}(v) = \sum_{u \in V} \text{number of edges } (u, v) )。
出度（OutDegree） 顶点 ( u ) 的出度为从它出发的边的数量，即 ( d_{\text{out}}(u) = \sum_{v \in V} \text{number of edges } (u, v) )。
强连通分量（SCC） 若有向图中任意两个顶点均可互相到达，则该子图为强连通分量。强连通分量是极大强连通子图。
弱连通分量 将有向图视为无向图后，其连通性称为弱连通性。
路径与环 路径：顶点序列 ( v_0 \rightarrow v_1 \rightarrow \cdots \rightarrow v_k )，边方向一致。
环：起点和终点相同的路径，且至少包含一条边。
- 特殊类型
- 有向树（DAG中的树结构）：父节点到子节点的单向边构成，无环。
- 竞赛图（Tournament Graph）：每对顶点之间恰好存在一条有向边。
- 完全有向图（Complete Directed Graph）：每对顶点之间存在两条方向相反的有向边，记为 ( \overleftrightarrow{K_n} )。
- 欧拉回路与路径：
- 欧拉回路：存在一条回路，遍历每条边恰好一次且起点=终点，需满足所有顶点的入度=出度。
- 欧拉路径：存在一条路径，遍历每条边恰好一次且起点≠终点，需满足恰有一个顶点出度=入度+1（起点），另一个顶点入度=出度+1（终点）。
三、无向图 vs 有向图的对比
对比维度 无向图 有向图
边方向性 边无方向，( (u, v) \equiv (v, u) )。 边有方向，( (u, v) \neq (v, u) )。
度 每个边贡献顶点度数 +1。 分为入度和出度，每条边仅贡献起点的出度 +1 和终点的入度 +1。
连通性 弱连通性等价于无向图的连通性。 强连通分量是更严格的连通条件。弱连通性需忽略边方向后判断。
环的存在性 环至少需要三个顶点（三角形环）。 可以存在自环（单个顶点的环）。
典型算法 BFS/DFS、最小生成树（Prim/Kruskal）、最短路径（Dijkstra未加权）。 Tarjan算法找强连通分量、BellmanFord检测负权环、拓扑排序。
四、数学表示与存储
- 数学表示
-
邻接矩阵（Adjacency Matrix）：
- 无向图：对称矩阵 ( A_{uv} = A_{vu} )。
- 有向图：非对称矩阵 ( A_{uv} ) 表示边 ( u \rightarrow v ) 是否存在。
-
邻接表（Adjacency List）：
- 无向图：每个顶点维护相邻顶点列表，边存储两次（如 ( u \rightarrow v ) 和 ( v \rightarrow u )）。
- 有向图：每个顶点维护出边列表，边仅存储一次。
- 存储复杂度
数据结构 空间复杂度（最坏情况）
邻接矩阵 ( O(V^2) )
邻接表 ( O(V + E) )
五、应用场景
- 无向图：社交网络关系建模、交通路线规划、分子结构分析。
- 有向图：网页链接分析（PageRank）、任务调度依赖关系、神经网络建模。
查考点
一、基础概念与性质
-
顶点与边
- 顶点集 ( V ) 和边集 ( E )，边的表示为无序对 ( {u, v} )。
- 简单图：无自环（边 ( {u, u} ) 不允许）且无多重边。
- 多重图：允许多条边连接同一对顶点。
-
度（Degree）
- 每个顶点的度数 ( d(u) = \text{与该顶点相连的边数} )。
- 奇点与偶点：度数为奇数的顶点称为奇点，否则为偶点。
- 握手定理：图中所有顶点的度数之和为偶数（每条边贡献两次度数）。
-
连通性
- 连通图：任意两个顶点之间存在至少一条路径。
- 连通分量：图的极大连通子图，非连通图的每个子图都是一个连通分量。
- 强连通分量（仅适用于有向图）：无向图的弱连通性即忽略方向后的连通性。
二、图的遍历
-
广度优先搜索（BFS）
- 层序遍历，从起点出发逐层扩展，记录访问顺序。
- 应用：寻找最短路径（无权图）、连通分量标记。
-
深度优先搜索（DFS）
- 递归或栈实现，优先探索某一分支到底。
- 应用：检测环、生成树、拓扑排序（需配合有向图）。
三、特殊图结构
-
树与森林
- 树：无环且连通的无向图，满足 ( E = V - 1 )。
- 森林：多个互不连通的树的集合。
- 二叉树：每个节点最多有两个子节点（左、右子节点），前序/中序/后序遍历。
-
完全图与环图
- 完全图：每对顶点间均有一条边（( K_n )）。
- 环图：所有顶点构成单一环（( C_n )，满足 ( E = V )）。
-
欧拉回路与路径
- 欧拉回路：存在一条回路经过所有边恰好一次，条件是所有顶点度数为偶数。
- 欧拉路径：存在一条路径经过所有边恰好一次，条件是恰有两个奇点（作为起点和终点）。
四、经典算法
-
最小生成树（MST）
-
最短路径算法
-
连通分量统计
- 使用DFS/BFS遍历整个图，标记未访问的顶点，统计连通分量个数。
五、高频题型与解题思路
-
理论题
- 判断图的连通性：通过BFS/DFS遍历后，检查是否所有顶点都被访问。
- 证明握手定理：利用边对度数的贡献进行归纳或数学推导。
-
编程题
- 构建图的邻接表：无向图需为每条边存储两次（如 ( u \rightarrow v ) 和 ( v \rightarrow u )）。
- 求最小生成树：实现Kruskal算法（需排序边并用并查集去重）。
- 检测欧拉回路：统计所有顶点度数是否均为偶数。
-
应用题
- 交通路网建模：城市作为顶点，道路作为边，求解最短路径或最小生成树。
- 社交网络分析：用户关系建模为无向图，寻找连通分量或社区划分。
六、易错点总结
- 无向图的边存储：邻接表中每条边需双向存储，邻接矩阵需保证对称性。
- 连通分量与强连通分量：无向图的连通分量无需考虑方向，而有向图的强连通分量需严格满足双向可达。
- 度数计算：自环边贡献度数 +1，多重边需逐条计数。
七、推荐练习
- 手写代码实现：
- BFS/DFS遍历无向图。
- Kruskal算法生成最小生成树。
- 在线平台题目：
- LeetCode 1274. Minimum Window Substring（需图遍历思想）。
- 牛客网 1228. 括号生成（树结构的应用）。
通过掌握上述知识点并配合大量练习，可以系统性地应对无向图相关的理论考察和编程问题。
#include <stdio.h>
#include <stdbool.h>#define MAX_VERTICES 4 // 定义最大顶点数// 定义图的结构体
typedef struct {int numVertices; // 顶点数bool adjMatrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵char vertexNames[MAX_VERTICES]; // 顶点名称
} Graph;// 函数声明
void initializeGraph(Graph* graph, int numVertices, char vertexNames[]);
void addEdge(Graph* graph, int src, int dest);
void printAdjMatrix(const Graph* graph); // 使用 const 防止修改// 初始化图
void initializeGraph(Graph* graph, int numVertices, char vertexNames[]) {graph->numVertices = numVertices;// 初始化顶点名称for (int i = 0; i < numVertices; i++) {graph->vertexNames[i] = vertexNames[i];}// 初始化邻接矩阵for (int i = 0; i < numVertices; i++) {for (int j = 0; j < numVertices; j++) {graph->adjMatrix[i][j] = false; // 初始化为 false，表示没有边}}
}// 添加边
void addEdge(Graph* graph, int src, int dest) {// 无向图，需要对称设置graph->adjMatrix[src][dest] = true;graph->adjMatrix[dest][src] = true;
}// 打印邻接矩阵
void printAdjMatrix(const Graph* graph) {printf("邻接矩阵：\n");for (int i = 0; i < graph->numVertices; i++) {for (int j = 0; j < graph->numVertices; j++) {printf("%d ", graph->adjMatrix[i][j]);}printf("\n");}
}int main() {// 定义图的顶点名称char vertexNames[MAX_VERTICES] = { 'A', 'B', 'C', 'D' };// 创建图并初始化Graph graph;initializeGraph(&graph, MAX_VERTICES, vertexNames);// 添加边addEdge(&graph, 0, 1); // A - BaddEdge(&graph, 0, 2); // A - CaddEdge(&graph, 1, 3); // B - DaddEdge(&graph, 2, 3); // C - D// 打印邻接矩阵printAdjMatrix(&graph);return 0;
}
图的表示
在代码中，图是通过邻接矩阵表示的。邻接矩阵是一个二维数组 adjMatrix，其中：
adjMatrix[i][j] = true表示顶点i和顶点j之间有一条边。adjMatrix[i][j] = false表示顶点i和顶点j之间没有边。
对于无向图，邻接矩阵是对称的，即 adjMatrix[i][j] = adjMatrix[j][i]。
顶点编号
在代码中，顶点被编号为：
- A → 0
- B → 1
- C → 2
- D → 3
添加边的操作
addEdge 函数的定义如下：
void addEdge(Graph *graph, int src, int dest) {// 无向图，需要对称设置graph->adjMatrix[src][dest] = true;graph->adjMatrix[dest][src] = true;
}
它的作用是在邻接矩阵中设置两个顶点之间的边。由于是无向图，需要同时设置 adjMatrix[src][dest] 和 adjMatrix[dest][src]。
具体操作分析
1. 添加边 A - B
addEdge(&graph, 0, 1); // A - B
src = 0（A），dest = 1（B）。- 设置
adjMatrix[0][1] = true，表示 A 和 B 之间有一条边。 - 设置
adjMatrix[1][0] = true，表示 B 和 A 之间有一条边。
邻接矩阵更新为：
A [ 0, 1, 0, 0 ]
B [ 1, 0, 0, 0 ]
C [ 0, 0, 0, 0 ]
D [ 0, 0, 0, 0 ]
2. 添加边 A - C
addEdge(&graph, 0, 2); // A - C
src = 0（A），dest = 2（C）。- 设置
adjMatrix[0][2] = true，表示 A 和 C 之间有一条边。 - 设置
adjMatrix[2][0] = true，表示 C 和 A 之间有一条边。
邻接矩阵更新为：
A [ 0, 1, 1, 0 ]
B [ 1, 0, 0, 0 ]
C [ 1, 0, 0, 0 ]
D [ 0, 0, 0, 0 ]
3. 添加边 B - D
addEdge(&graph, 1, 3); // B - D
src = 1（B），dest = 3（D）。- 设置
adjMatrix[1][3] = true，表示 B 和 D 之间有一条边。 - 设置
adjMatrix[3][1] = true，表示 D 和 B 之间有一条边。
邻接矩阵更新为：
A [ 0, 1, 1, 0 ]
B [ 1, 0, 0, 1 ]
C [ 1, 0, 0, 0 ]
D [ 0, 1, 0, 0 ]
4. 添加边 C - D
addEdge(&graph, 2, 3); // C - D
src = 2（C），dest = 3（D）。- 设置
adjMatrix[2][3] = true，表示 C 和 D 之间有一条边。 - 设置
adjMatrix[3][2] = true，表示 D 和 C 之间有一条边。
邻接矩阵更新为：
A [ 0, 1, 1, 0 ]
B [ 1, 0, 0, 1 ]
C [ 1, 0, 0, 1 ]
D [ 0, 1, 1, 0 ]
最终邻接矩阵
经过上述操作后，邻接矩阵如下：
A B C D
A [ 0, 1, 1, 0 ]
B [ 1, 0, 0, 1 ]
C [ 1, 0, 0, 1 ]
D [ 0, 1, 1, 0 ]
可视化图结构
根据邻接矩阵，图的结构可以可视化如下：
A -- B
| \ |
| \ |
C -- D
- A 与 B、C 相连。
- B 与 A、D 相连。
- C 与 A、D 相连。
- D 与 B、C 相连。
总结
addEdge 函数通过修改邻接矩阵来表示顶点之间的边。对于无向图，需要同时设置 adjMatrix[src][dest] 和 adjMatrix[dest][src]。通过多次调用 addEdge，可以逐步构建出完整的图结构。
邻接矩阵的算法分析
邻接矩阵是图的一种常见表示方法，特别适用于稠密图（即边数接近顶点数平方的图）。以下是对邻接矩阵的算法分析以及优劣分析，从时间复杂度、空间复杂度、适用场景等方面进行详细科学分析。
1. 邻接矩阵的定义
邻接矩阵是一个二维数组 matrix，其中：
matrix[i][j] = 1（或权重值）表示顶点i和顶点j之间有一条边。matrix[i][j] = 0（或无穷大）表示顶点i和顶点j之间没有边。
对于无向图，邻接矩阵是对称的；对于有向图，邻接矩阵不一定对称。
2. 算法分析
(1) 空间复杂度
- 邻接矩阵的空间复杂度为 O(V²)，其中
V是顶点数。 - 无论图中实际有多少条边，邻接矩阵都需要存储
V × V个元素。 - 对于稀疏图（边数远小于顶点数平方），邻接矩阵会浪费大量空间。
(2) 时间复杂度
查询两个顶点之间是否有边
- 时间复杂度为 O(1)。
- 直接访问
matrix[i][j]即可判断顶点i和顶点j之间是否有边。
遍历某个顶点的所有邻居
- 时间复杂度为 O(V)。
- 需要遍历该顶点对应的整行或整列，检查哪些位置的值为
1。
添加或删除一条边
- 时间复杂度为 O(1)。
- 直接修改
matrix[i][j]和matrix[j][i]（无向图）即可。
初始化邻接矩阵
- 时间复杂度为 O(V²)。
- 需要初始化一个
V × V的二维数组。
3. 优劣分析
(1) 优点
-
查询边的存在性高效：
- 时间复杂度为 O(1)，适合需要频繁查询边是否存在的场景。
-
适合稠密图：
- 当图的边数接近顶点数平方时，邻接矩阵的空间利用率较高。
-
易于实现：
- 邻接矩阵的实现简单直观，适合初学者理解和实现。
-
支持快速修改：
- 添加、删除或修改边的时间复杂度为 O(1)。
-
适合存储带权图：
- 邻接矩阵可以直接存储边的权重，适合需要处理带权图的场景。
(2) 缺点
-
空间复杂度高：
- 空间复杂度为 O(V²)，对于稀疏图会浪费大量空间。
-
遍历邻居效率低：
- 遍历某个顶点的所有邻居需要 O(V) 时间，即使该顶点的实际邻居很少。
-
不适合动态图：
- 如果图的顶点数动态变化，邻接矩阵需要重新分配和复制数据，效率较低。
-
无法高效存储稀疏图：
- 对于稀疏图，邻接表（Adjacency List）是更优的选择。
4. 适用场景
(1) 适合使用邻接矩阵的场景
-
稠密图：
- 边数接近顶点数平方的图，邻接矩阵的空间利用率高。
-
需要频繁查询边的存在性：
- 例如，某些图算法需要快速判断两个顶点是否相邻。
-
带权图：
- 邻接矩阵可以直接存储边的权重，适合处理带权图。
-
小规模图：
- 当顶点数较少时，邻接矩阵的空间开销可以接受。
(2) 不适合使用邻接矩阵的场景
-
稀疏图：
- 边数远小于顶点数平方的图，邻接矩阵会浪费大量空间。
-
大规模图：
- 当顶点数很大时，邻接矩阵的空间开销会变得不可接受。
-
动态图：
- 顶点数动态变化的图，邻接矩阵的调整成本较高。
5. 与邻接表的对比
| 特性 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间复杂度 | O(V²) | O(V + E) |
| 查询边的存在性 | O(1) | O(degree(V)) |
| 遍历邻居 | O(V) | O(degree(V)) |
| 添加边 | O(1) | O(1) |
| 删除边 | O(1) | O(degree(V)) |
| 适合的图类型 | 稠密图 | 稀疏图 |
| 实现复杂度 | 简单 | 较复杂 |
6. 总结
- 邻接矩阵适合稠密图、带权图以及需要频繁查询边存在性的场景。
- 邻接表适合稀疏图、大规模图以及需要高效遍历邻居的场景。
- 在实际应用中，应根据图的特点（稠密或稀疏）和操作需求（查询、遍历、修改等）选择合适的表示方法。
