大二数据结构（图）

阅读量：375 次

发布时间：2019-03-04

本文共 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²)。

邻接矩阵示例

有向图 G1 邻接矩阵示例：

[0, 1, 0, 0][0, 0, 1, 0][0, 0, 0, 1][0, 0, 0, 0]

无向图 G2 邻接矩阵示例：

[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 的所有邻接边            如果邻接顶点未被访问                标记为已访问                加入队列}