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

数据结构《图》

news 来源：原创 2025/9/17 23:11:06

数据结构《图论》

图的性质

一、无向图（Undirected Graph）

定义

由一组顶点（Vertex）和一组无向边（Edge）构成。
每条无向边用一条无方向的线段连接两个顶点，记为 ( (u, v) )，其中 ( u ) 和 ( v ) 是顶点，且 ( u \neq v )。若允许自环，可表示为 ( (u, u) )。
1. 核心性质
  性质定义与特点

顶点集记为 ( 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 )）和多重边。
1. 核心性质
  性质定义与特点

顶点集记为 ( 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 )）。
- 有向图：每个顶点维护出边列表，边仅存储一次。
1. 存储复杂度
  数据结构空间复杂度（最坏情况）

邻接矩阵 ( 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）
- Prim算法：贪心策略，每次选择当前顶点到生成树的最小边。
- Kruskal算法：基于边权排序，使用并查集（Union-Find）避免环。
最短路径算法
- Dijkstra算法：适用于无权图或边权非负的情况，找到单源最短路径。
- Floyd-Warshall算法：计算所有顶点对之间的最短路径（多源最短路径）。
连通分量统计
- 使用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. 总结

邻接矩阵适合稠密图、带权图以及需要频繁查询边存在性的场景。
邻接表适合稀疏图、大规模图以及需要高效遍历邻居的场景。
在实际应用中，应根据图的特点（稠密或稀疏）和操作需求（查询、遍历、修改等）选择合适的表示方法。