欢迎来到尧图网

客户服务 关于我们

您的位置：首页 > 教育 > 培训 > 数据结构《图》

数据结构《图》

2025/2/24 19:48:10 来源：https://blog.csdn.net/qq_56146092/article/details/145739137  浏览:  次   关键词：数据结构《图》

数据结构《图论》

图的性质

一、无向图（Undirected Graph）

  1. 定义

  • 由一组顶点（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） 删除该顶点后图的连通分量数目增加，则该顶点为割点。

  1. 特殊类型
  • 树（Tree）：无环且连通的无向图，满足 ( E = V - 1 )。
  • 森林（Forest）：若干棵互不连通的树的集合。
  • 完全图（Complete Graph）：每对顶点之间均存在一条边，记为 ( K_n )（( n ) 个顶点）。
  • 环图（Cycle Graph）：所有顶点构成一个单一环，满足 ( E = V )。

二、有向图（Directed Graph）

  1. 定义

  • 由一组顶点和一组有向边（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 )，边方向一致。
环：起点和终点相同的路径，且至少包含一条边。

  1. 特殊类型
  • 有向树（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检测负权环、拓扑排序。

四、数学表示与存储

  1. 数学表示

  • 邻接矩阵（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）、任务调度依赖关系、神经网络建模。

查考点

一、基础概念与性质

  1. 顶点与边

    • 顶点集 ( V ) 和边集 ( E )，边的表示为无序对 ( {u, v} )。
    • 简单图：无自环（边 ( {u, u} ) 不允许）且无多重边。
    • 多重图：允许多条边连接同一对顶点。

  2. 度（Degree）

    • 每个顶点的度数 ( d(u) = \text{与该顶点相连的边数} )。
    • 奇点与偶点：度数为奇数的顶点称为奇点，否则为偶点。
    • 握手定理：图中所有顶点的度数之和为偶数（每条边贡献两次度数）。

  3. 连通性

    • 连通图：任意两个顶点之间存在至少一条路径。
    • 连通分量：图的极大连通子图，非连通图的每个子图都是一个连通分量。
    • 强连通分量（仅适用于有向图）：无向图的弱连通性即忽略方向后的连通性。

二、图的遍历

  1. 广度优先搜索（BFS）

    • 层序遍历，从起点出发逐层扩展，记录访问顺序。
    • 应用：寻找最短路径（无权图）、连通分量标记。

  2. 深度优先搜索（DFS）

    • 递归或栈实现，优先探索某一分支到底。
    • 应用：检测环、生成树、拓扑排序（需配合有向图）。

三、特殊图结构

  1. 树与森林

    • 树：无环且连通的无向图，满足 ( E = V - 1 )。
    • 森林：多个互不连通的树的集合。
    • 二叉树：每个节点最多有两个子节点（左、右子节点），前序/中序/后序遍历。

  2. 完全图与环图

    • 完全图：每对顶点间均有一条边（( K_n )）。
    • 环图：所有顶点构成单一环（( C_n )，满足 ( E = V )）。

  3. 欧拉回路与路径

    • 欧拉回路：存在一条回路经过所有边恰好一次，条件是所有顶点度数为偶数。
    • 欧拉路径：存在一条路径经过所有边恰好一次，条件是恰有两个奇点（作为起点和终点）。

四、经典算法

  1. 最小生成树（MST）

    • Prim算法：贪心策略，每次选择当前顶点到生成树的最小边。
    • Kruskal算法：基于边权排序，使用并查集（Union-Find）避免环。

  2. 最短路径算法

    • Dijkstra算法：适用于无权图或边权非负的情况，找到单源最短路径。
    • Floyd-Warshall算法：计算所有顶点对之间的最短路径（多源最短路径）。

  3. 连通分量统计

    • 使用DFS/BFS遍历整个图，标记未访问的顶点，统计连通分量个数。

五、高频题型与解题思路

  1. 理论题

    • 判断图的连通性：通过BFS/DFS遍历后，检查是否所有顶点都被访问。
    • 证明握手定理：利用边对度数的贡献进行归纳或数学推导。

  2. 编程题

    • 构建图的邻接表：无向图需为每条边存储两次（如 ( u \rightarrow v ) 和 ( v \rightarrow u )）。
    • 求最小生成树：实现Kruskal算法（需排序边并用并查集去重）。
    • 检测欧拉回路：统计所有顶点度数是否均为偶数。

  3. 应用题

    • 交通路网建模：城市作为顶点，道路作为边，求解最短路径或最小生成树。
    • 社交网络分析：用户关系建模为无向图，寻找连通分量或社区划分。

六、易错点总结

  1. 无向图的边存储：邻接表中每条边需双向存储，邻接矩阵需保证对称性。
  2. 连通分量与强连通分量：无向图的连通分量无需考虑方向，而有向图的强连通分量需严格满足双向可达。
  3. 度数计算：自环边贡献度数 +1，多重边需逐条计数。

七、推荐练习

  1. 手写代码实现：
    • BFS/DFS遍历无向图。
    • Kruskal算法生成最小生成树。
  2. 在线平台题目：
    • 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) 优点

  1. 查询边的存在性高效：

    • 时间复杂度为 O(1)，适合需要频繁查询边是否存在的场景。

  2. 适合稠密图：

    • 当图的边数接近顶点数平方时，邻接矩阵的空间利用率较高。

  3. 易于实现：

    • 邻接矩阵的实现简单直观，适合初学者理解和实现。

  4. 支持快速修改：

    • 添加、删除或修改边的时间复杂度为 O(1)。

  5. 适合存储带权图：

    • 邻接矩阵可以直接存储边的权重，适合需要处理带权图的场景。

(2) 缺点

  1. 空间复杂度高：

    • 空间复杂度为 O(V²)，对于稀疏图会浪费大量空间。

  2. 遍历邻居效率低：

    • 遍历某个顶点的所有邻居需要 O(V) 时间，即使该顶点的实际邻居很少。

  3. 不适合动态图：

    • 如果图的顶点数动态变化，邻接矩阵需要重新分配和复制数据，效率较低。

  4. 无法高效存储稀疏图：

    • 对于稀疏图，邻接表（Adjacency List）是更优的选择。

4. 适用场景

(1) 适合使用邻接矩阵的场景

  1. 稠密图：

    • 边数接近顶点数平方的图，邻接矩阵的空间利用率高。

  2. 需要频繁查询边的存在性：

    • 例如，某些图算法需要快速判断两个顶点是否相邻。

  3. 带权图：

    • 邻接矩阵可以直接存储边的权重，适合处理带权图。

  4. 小规模图：

    • 当顶点数较少时，邻接矩阵的空间开销可以接受。

(2) 不适合使用邻接矩阵的场景

  1. 稀疏图：

    • 边数远小于顶点数平方的图，邻接矩阵会浪费大量空间。

  2. 大规模图：

    • 当顶点数很大时，邻接矩阵的空间开销会变得不可接受。

  3. 动态图：

    • 顶点数动态变化的图，邻接矩阵的调整成本较高。

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. 总结

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

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

相关资讯

热文排行

最新新闻

推荐新闻

热搜词