本文共 1127 字，大约阅读时间需要 3 分钟。

图论基础

图是由顶点和边组成的集合，其中，顶点表示数据元素，边表示这些元素之间的关系。根据顶点间的关系，图可以分为树形结构、完全图形结构等。树形结构中，每个元素有且只有一个直接前驱和直接后继，关系为“前驱-后继”；图形结构中，任意两个顶点之间均为邻接关系。

无向图中，边不具有方向，是用无序偶对$(V_i, V_j)$表示。有向图中，边上带有方向，称为弧，用有序偶对$<V_i, V_j>$表示。有向图中，任意两顶点之间有两条弧，方向相反。无向图中任意顶点间有一条边，无向图的边数量可以通过公式$C(n, 2)$计算得出。

图可分为无向图和有向图，每条边可选带权值，形成网或有权图。完全无向图是指每对顶点间均存在边，完全有向图是指每对顶点之间存在方向相反的弧。

图的存储结构

邻接矩阵

邻接矩阵用二维数组表示，大小为$n \times n$，存储图中顶点的邻接信息。矩阵中元素$A[i][j]$表示顶点$i$与顶点$j$是否相连。空间复杂度为$O(n^2)$，访问一个顶点的邻接点的平均时间复杂度为$O(n)$。

邻接表

邻接表由链表或数组构成，存储每个顶点的邻接点。边数为$e$，整个图需要$n + e$个存储单元。访问特定顶点的邻接点的时间复杂度为$O(e/n)$。邻接表是唯一的，取决于输入顺序和边表的插入方式。

邻接矩阵与邻接表的比较

• 空间复杂度：$O(n^2)$（邻接矩阵）$ \leq O(n + e)$（邻接表）
• 时间复杂度：$O(n)$（邻接矩阵）$ \geq O(e/n)$（邻接表）
• 唯一性：邻接矩阵唯一，邻接表非唯一

图的遍历方式

图的遍历是从某一顶点出发，逐层访问未被访问的邻接点的过程。主要有深度优先搜索（DFS）和广度优先搜索（BFS）两种方式：

• 深度优先搜索（DFS）：沿着路径尽可能深入访问顶点。
• 广度优先搜索（BFS）：沿着路径逐层访问顶点，层序遍历。

图的代码实现

图的实现可采用邻接矩阵或邻接表方式。以下是常见的邻接表实现方法：

struct Node {    int label;    list[int> adjacency;}Graph graph = { ... };

其中，Node结构体包含顶点标签和邻接点列表。图的构建函数Graphρού，顶点添加函数addEdge，遍历函数traverse等。

图的应用

最小生成树

通过最短路径连接所有顶点，去除任意一条边后orest保持图连通，计算最小生成树总权重。常用算法有Kruskal和Prim。

两点间最短路径

使用Dijkstra或Floyd算法计算两点间最短路径。

拓扑排序

对图中的DNA关系排序，即对某类依赖关系排序。常用于项目管理和任务安排。