主页 > 手机 >

数据结构《图》

手机
2025-08-26 22:57:02

数据结构《图论》图的性质

一、无向图（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）

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 - B addEdge(&graph, 0, 2); // A - C addEdge(&graph, 1, 3); // B - D addEdge(&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 → 0B → 1C → 2D → 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) 缺点