本文共 1678 字,大约阅读时间需要 5 分钟。
图论基础 - 概念、储存结构与遍历方法
一、概念
图论是研究图的结构、性质及其应用的学科。图主要由顶点和边组成,具体定义如下:
- 顶点 (Vertex):顶点的有穷非空集合,记作 V。
- 边 (Edge) 或 弧 (Arc):顶点之间的关系集合,记作 E 或 E'。
- 无向图:边没有方向,表示为 G。
- 有向图:边具有方向,表示为 G' 或 Digraph (简称 DGraph)。
图的基本术语
顶点数:图中顶点的总数记为 n。 边数:图中边的总数记为 m。 无向完全图:每对顶点之间有一条边,边数为 n(n-1)/2。 有向完全图:每对顶点之间有两条边(一条从A到B,一条从B到A),边数为 n(n-1)。 稀疏图:边数远小于顶点数的平方(即 m < n²)。 稠密图:边数接近或超过顶点数的平方(即 m ≈ n²)。 带权图:边具有权重,用于表示边的重要性或成本。 图的性质
连通图:图中存在一条路径使得任意两个顶点之间都可以相连。 连通分量:无向图中最大连通子图。 强连通图:有向图中任意两个顶点之间都存在路径。 生成树:包含所有顶点且边最少的连通子图,边数为 n-1。
二、图的储存结构
邻接矩阵法
邻接矩阵是图的最常见储存方法,适用于边稠密图。
特点
无向图:邻接矩阵为对称矩阵,边被双重记录。 有向图:邻接矩阵不对称,每条边单独记录。 优点: - 顶点度数直接从矩阵中获取。
- 判断邻接关系简单,仅需访问矩阵对应位置。
- 增加删除边操作简单。
- 存储空间与顶点数相关,与边数无关。
缺点: - 删除顶点需要重构矩阵,操作复杂。
- 统计边数需要遍历整个矩阵,时间复杂度为 O(n²)。
- 空间复杂度为 O(n²)。
邻接矩阵示例
[0, 1, 0, 0][0, 0, 1, 0][0, 0, 0, 1][0, 0, 0, 0]
[0, 1, 0, 1][0, 0, 1, 1][0, 0, 0, 1][0, 0, 0, 0]
邻接表法
邻接表适用于边稀疏图,通过链表存储边。
特点
无向图: - 每个顶点的边存储在链表中。
- 顶点度数等于链表长度。
- 判断邻接关系需要遍历链表。
有向图: - 同一条边在两个顶点的链表中各存储一次。
- 查找反向边较为困难。
优点: - 增加删除边操作直接。
- 度数统计简单。
- 存储空间与顶点数和边数相关。
缺点: 邻接表结构
| data | firstarc |
| adjvex | info | nextarc |
三、图的遍历
深度优先遍历(DFS)
算法描述: - 从起始顶点开始,访问所有未被访问的邻接顶点,递归深入。
- 使用
visited
数组记录访问状态,避免重复访问。
实现示例(邻接表): void DFS(G, v) { 标记 v 为已访问 遍历 v 的所有邻接边 如果邻接顶点未被访问 调用 DFS}
- 时间复杂度:
- 最坏情况: O(n²)(稠密图)。
- 平均情况: O(n)(稀疏图)。
广度优先遍历(BFS)
- 算法描述:
- 从起始顶点开始,层序访问所有邻接顶点。
- 使用队列记录当前层的顶点,逐层扩展。
- 实现示例(邻接表):
void BFS(G, v) { 初始化队列,将 v 加入队列 标记 v 为已访问 while 队列不为空 取出队列顶点 u 遍历 u 的所有邻接边 如果邻接顶点未被访问 标记为已访问 加入队列}
- 时间复杂度:
- 最坏情况: O(n²)(稠密图)。
- 平均情况: O(n + e)(稀疏图)。
四、总结
图论的核心在于理解图的结构及其遍历方法。邻接矩阵和邻接表是两种常见的储存结构,适用于不同场景。无论是深度优先遍历还是广度优先遍历,其核心目标都是访问图中的所有顶点。选择合适的算法和结构,能够有效地解决实际问题。
转载地址:http://xtfg.baihongyu.com/