当前位置：首页 > news >正文

《 C++ 修炼全景指南：十七》彻底攻克图论！轻松解锁最短路径、生成树与高效图算法

news 2024/10/27 1:24:40

在这里插入图片描述

摘要

1、引言

1.1、什么是图？

图（Graph）是计算机科学和离散数学中一种重要的数据结构，用来表示一组对象之间的关系。一个图由顶点（也称为节点，Vertex）和边（Edge）组成。顶点表示实体，而边则表示实体之间的关联或连接关系。根据边的性质，图可以分为无向图和有向图。在无向图中，边没有方向，表示顶点之间的双向关系；在有向图中，边有方向，表示顶点之间的单向关系。此外，边可以具有权重，用来表示顶点之间关系的强度或成本，从而构成加权图。

通过图结构，我们可以自然地建模和解决许多现实世界中的复杂问题。因此，掌握图的基本结构与相关算法是理解和解决各类复杂关系型问题的关键。

1.2、图的实际应用场景

图作为一种强大的抽象工具，在各类实际场景中得到了广泛的应用。例如：

社交网络：在社交网络中，用户可以被表示为图中的顶点，用户之间的好友关系可以被表示为图中的边。基于这种表示，社交网络公司可以使用图算法来推荐好友、检测社区或计算影响力。
地图与路径规划：在地图应用中，地点可以被看作顶点，地点之间的道路或航线可以被看作边。通过图算法，如最短路径算法，导航软件能够为用户提供最优路线。
通信网络：在互联网或通信网络中，服务器、路由器等设备可以被看作顶点，连接设备的通信链路可以被看作边。通过分析图结构，可以进行网络优化、流量管理和故障检测。
化学分子结构：在化学领域，分子中的原子可以被看作顶点，原子之间的化学键可以被看作边。基于分子的图表示，可以研究分子结构、化合物分析以及新材料设计。

除了以上的应用，图还广泛应用于推荐系统、图像处理、人工智能、交通网络等众多领域。因此，图及其相关算法不仅具有重要的理论意义，还具备广泛的实用价值。

1.3、博客目标

本博客的目标是为读者提供一个全面的图论学习指南，帮助理解图的基本概念和重要算法，并展示如何在实际问题中应用这些知识。我们将从图的基本结构开始，逐步深入讨论图的各种表示方法，并探索图的核心算法，如广度优先搜索（BFS）、深度优先搜索（DFS）、最短路径算法（如 Dijkstra、Bellman-Ford）、最小生成树算法（如 Prim、Kruskal），以及图的高级技术，如拓扑排序和网络流等。

在博客的后半部分，我们将深入探讨图算法的优化技巧，并分析如何在大规模图数据中提高算法的效率。此外，我们还会讨论一些动态图算法，以及实际开发中的应用场景，帮助读者掌握应对复杂图问题的技巧。

通过阅读此博客，您将能够系统地掌握图论的理论基础、核心算法及其优化技巧，并理解这些算法在真实世界中的应用场景。无论是初学者还是有经验的开发者，您都可以通过此博客提升对图论的理解和应用能力。

2、图的基本概念

2.1、图的定义与基本术语

图 (Graph) 是一个用于表示实体（顶点）之间关系（边）的抽象数据结构，广泛用于数学、计算机科学、网络分析等领域。图通常用 G=(V,E) 表示，其中 V 是顶点的集合，E 是边的集合。顶点表示对象，边表示对象之间的关系。通过边连接的两个顶点之间存在关联或依赖关系，这种关系可以是双向的，也可以是单向的。

根据连接方式和边的属性，图具有不同的特征和分类。理解图的基本概念和分类有助于我们灵活选择合适的图结构来建模不同类型的实际问题。

基本术语：

顶点（Vertex）：图的基本组成单位，用来表示对象或实体。在编程中，顶点通常用整数或特定的标签表示。
边（Edge）：连接两个顶点的关系。边可以有方向（有向图）或无方向（无向图），并可能附带权重（如距离、成本等）。
邻接：两个顶点之间直接有边连接时称为邻接。
度（Degree）：无向图中某顶点的度表示与其相连的边的数量；有向图中分为入度和出度，表示指向该顶点和从该顶点出发的边数。
路径（Path）：从一个顶点到另一个顶点的边序列。
回路（Cycle）：路径的起点和终点相同，且路径中的顶点不重复。

2.2、图的分类

根据边的性质和方向性，图可以分为多种类型：

无向图（Undirected Graph）和有向图（Directed Graph）：
- 无向图：在无向图中，边没有方向，因此两个顶点间的边可以双向通行。例如，社交网络中两人互相认识可以表示为无向边。用 (u,v) 表示一条无向边。
- 有向图：在有向图中，边有方向，只允许从起点流向终点。若顶点 A 到顶点 B 有一条边 (A,B)，则仅表示从 A 到 B 的关系。典型应用如网络传输、网页链接等。用 (u→v) 表示一条有向边。
加权图（Weighted Graph）和非加权图（Unweighted Graph）：
- 加权图：在加权图中，边附带权重（weight），用于表示两顶点间的成本、距离或强度。常用于路径最优化问题，如地图中的最短路径。
- 非加权图：在非加权图中，边没有权重，通常表示顶点之间的简单关系。
简单图（Simple Graph）和多重图（Multigraph）：
- 简单图：简单图中每对顶点之间最多只有一条边，且不包含顶点自身的环。
- 多重图：多重图允许同一对顶点之间存在多条边，通常表示两实体间的多种关系。
稀疏图（Sparse Graph）和稠密图（Dense Graph）：
- 稀疏图：当图中的边数远少于顶点数的平方时，称为稀疏图。在很多应用场景中，图数据稀疏性有利于提高存储和计算效率。
- 稠密图：稠密图中边数接近顶点数的平方。稠密图通常会增加存储和计算复杂度，但在某些应用场景中提供了丰富的关系信息。
连通图（Connected Graph）和非连通图（Disconnected Graph）：
- 连通图：无向图中，任意两顶点之间至少有一条路径。
- 强连通图和弱连通图：在有向图中，若任意两顶点间都有路径，则为强连通图；若去掉方向后为连通图，则为弱连通图。

2.3、图的表示方法

图的表示方式决定了图的存储空间和访问效率，常用的图表示方法包括邻接矩阵、邻接表和边列表。

邻接矩阵（Adjacency Matrix）：

邻接矩阵使用一个 ∣V∣×∣V∣ 的二维数组来表示顶点之间的连接关系，其中 ∣V∣是顶点数量。若顶点 i 和 j 之间存在边，则 matrix[i][j]=1（或权重值）；否则为 0。在加权图中，矩阵中的值可以表示权重。
- 优点：可以快速 (O(1) 时间) 判断两顶点是否相连，适用于稠密图。
- 缺点：空间复杂度高，适用于边数较多的场景。对于稀疏图来说，存储效率低。
邻接表（Adjacency List）：

邻接表为每个顶点建立一个列表，列表包含所有与该顶点相连的顶点。对于加权图，每条边还可以附加权重。
- 优点：高效存储稀疏图，空间复杂度为 O(∣V∣+∣E∣) 。
- 缺点：查询两顶点的连接需要遍历邻接表，适合边查询不频繁的场景。
边列表（Edge List）：

边列表存储图中所有边的集合，每条边包含两个顶点及其权重（加权图）。这种方式适用于仅需要遍历边的场景。
- 优点：存储简单，适合图遍历算法，如最小生成树算法。
- 缺点：查询顶点连接信息效率低，不适合频繁查询的应用场景。

2.4、图的基本性质

连通性（Connectivity）：
- 连通图：在无向图中，若任意两顶点间至少有一条路径，则称该图为连通图。
- 强连通图：在有向图中，若任意两顶点之间均存在路径，则为强连通图。
- 弱连通图：在有向图中，仅当无视边的方向后图为连通图，则称该图为弱连通图。
度（Degree）：
- 顶点的度：无向图中，顶点的度为连接的边数。在有向图中，顶点的度分为入度（入射的边数）和出度（出射的边数）。
- 图的度性质：无向图中，所有顶点的度之和为图中边数的两倍（即 2∣E∣）。在有向图中，入度和出度的总和等于边数。
路径（Path）和回路（Cycle）：
- 路径：从一个顶点到另一个顶点的边序列称为路径，路径上的顶点和边不能重复。
- 回路：起点和终点相同的路径，若路径中的顶点不重复，则为简单回路。图中的回路是判断图结构的重要依据。例如，有向无环图（DAG）是一类特殊图，没有回路，适合拓扑排序。
连通分量（Connected Components）：
- 无向图的连通分量是极大连通子图，每个分量内任意两顶点互相连通。连通分量可用于划分图结构，帮助理解独立的关系群体。
- 在有向图中，连通性可细分为强连通分量和弱连通分量。
图的生成树（Spanning Tree）：
- 无向连通图的生成树是一棵包含所有顶点且边数最小的连通子图。生成树的特性是连接所有顶点而无回路。
- 在加权图中，最小生成树（MST）是权重和最小的生成树，常用于最小成本路径规划。

2.5、图的遍历方式

深度优先搜索（DFS）：
- 从起始顶点出发，沿着每条路径深入遍历，直到无法继续，再回溯到上一层继续。DFS 使用递归或栈实现。
- 应用：连通分量检测、拓扑排序、强连通分量求解、图的回路检测。
广度优先搜索（BFS）：
- 从起始顶点出发，优先遍历每层的相邻节点，层层推进，直至遍历完整个连通分量。BFS 使用队列实现。
- 应用：最短路径搜索（无权图）、连通性检测、图的层次结构分析。

2.6、图的特殊类型

无环图（Acyclic Graph）：
- 有向无环图（DAG）：一类特殊的有向图，没有回路。DAG 常用于依赖关系建模，如任务调度、版本控制等。
树（Tree）：
- 树是无环连通图，具有唯一的路径连接任意两个顶点。树是最简单的连通图结构，是生成树、最小生成树等概念的基础。
双连通图（Biconnected Graph）：
- 若无向图中任意删除一个顶点，图依然连通，则称为双连通图。双连通图在网络稳定性和冗余设计中非常有用。

2.7、图的存储与访问性能分析

时间复杂度：
- 使用邻接矩阵进行邻接检测需要 O(1) 时间，但邻接表可能需要 O(∣V∣)。
- DFS 和 BFS 的时间复杂度通常为 O(∣V∣+∣E∣) ，适用于邻接表表示的图。
空间复杂度：
- 邻接矩阵的空间复杂度为 O(∣V∣²)，适合稠密图。
- 邻接表的空间复杂度为 O(∣V∣+∣E∣) ，适合稀疏图。

2.8、图的理论基础

Eulerian 图：
- 欧拉路径（Eulerian Path）：访问每条边恰好一次的路径。一个连通无向图具有欧拉路径的条件是，至多有两个奇数度的顶点。
- 欧拉回路（Eulerian Circuit）：起点与终点相同的欧拉路径。连通无向图具有欧拉回路的条件是所有顶点的度均为偶数。欧拉图在路径规划和回路检测中有重要应用。
Hamiltonian 图：
- 哈密顿路径（Hamiltonian Path）：访问每个顶点恰好一次的路径。
- 哈密顿回路（Hamiltonian Circuit）：起点与终点相同的哈密顿路径。哈密顿图问题是一个经典的 NP 完全问题，广泛应用于图论和组合优化研究。
平面图（Planar Graph）：
- 可以在平面上画出且边不相交的图称为平面图。平面图的一个重要性质是，满足 ∣E∣≤3∣V∣−6 。
- 平面图应用于地图绘制、网络布局等场景。它提供了拓扑学的基础理论，常用于研究图的嵌入与可视化。
Bipartite Graph（二分图）：
- 图的顶点集可以划分为两个不相交的子集，且每条边的两个端点分属不同子集的图。
- 二分图广泛用于匹配算法，社交网络中的关系图建模，以及网络流问题的分解。其核心性质是无奇数环。

2.9、图的实际应用

图的概念在多个实际应用场景中起到了核心作用：

社交网络：用户和关系可以表示为图，帮助分析用户间关系、推荐系统、影响力传播。
路由和导航系统：地图和路径规划常用有向加权图表示，广泛用于导航算法（如 Dijkstra、A*）。
网络流量分析：通信网络可以建模为图，用于优化流量、检测网络瓶颈和网络安全分析。
生物信息学：生物体的基因组、蛋白质交互网络等可用图建模，以便进行模式匹配、进化分析。
任务调度与依赖关系：项目管理和任务调度中，依赖关系图用于确定任务顺序和优化执行时间。

2.10、图的性质小结

图作为一类基础数据结构，覆盖了算法研究的诸多方面。本节通过详细讨论图的概念、分类、表示方式及应用场景，希望为读者提供图结构的深入理解，为下面进一步的图算法学习打下坚实基础。无论是社交网络中的社区检测，还是网络图中的最短路径计算，图的结构与性质决定了算法的效率和实现方式。在接下来的章节中，将详细介绍各类图算法，包括路径查找、最小生成树和流网络算法等，以便更全面地掌握图的应用能力。

3、图的存储结构

在图论和图算法的应用中，合理选择图的存储结构对于算法效率和代码的简洁性至关重要。图的存储结构主要有两种：邻接矩阵（Adjacency Matrix）和邻接表（Adjacency List）。接下来，我们将分别介绍这两种存储方式的原理、优缺点及其在 C++ 中的具体实现，以帮助读者深入理解它们的适用场景和实现细节。

3.1、邻接矩阵（Adjacency Matrix）

3.1.1、概述

邻接矩阵是一种使用二维矩阵存储图的顶点与边关系的方式。假设有一个图 G = (V, E)，其中 V 表示顶点集，E 表示边集。对于一个有 n 个顶点的图，邻接矩阵使用一个 n x n 的二维数组 matrix，其中每个元素 matrix[i][j] 表示从顶点 i 到顶点 j 的边权值。如果 i 到 j 之间没有边，则 matrix[i][j] 设置为一个特殊值（通常是 0 或 ∞，取决于是否是有权图）。

3.1.2、特点

空间消耗：邻接矩阵的空间复杂度为 O(V²)，因此对顶点较多、边较少的稀疏图不太友好，但对于稠密图（边数接近顶点数平方）的表示效率较高。
快速访问：可以在 O(1) 时间内判断两个顶点之间是否存在边，适用于需要频繁查询顶点对间连接状态的情况。
适用场景：邻接矩阵适用于稠密图或顶点较少的图结构，以及频繁需要查询边是否存在的情况。

3.1.3、邻接矩阵的实现

为了增强实现的通用性和代码复用性，我们使用了模板类，以支持任意类型的顶点和权值，并在 C++ 中定义了有向图和无向图的支持。以下代码展示了邻接矩阵在 C++ 中的实现。

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <stdexcept>namespace Lenyiin
{// 定义边的结构体, 包含源节点、目标节点和权重template <class W>struct Matrix_Edge{size_t _srcIndex; // 源节点索引size_t _dstIndex; // 目标节点索引W _weight;        // 边的权重Matrix_Edge(size_t srcIndex, size_t dstIndex, const W &weight): _srcIndex(srcIndex), _dstIndex(dstIndex), _weight(weight){}bool operator>(const Matrix_Edge &e) const{return _weight > e._weight;}};// vertex 顶点// edge 边// weight 权重// 定义邻接矩阵类模板template <class V, class W, W MAX_W = INT32_MAX, bool Direction = false>class Matrix_Graph{private:typedef Matrix_Graph<V, W, MAX_W, Direction> Self;typedef struct Matrix_Edge<W> EdgeNode;public:// 默认构造函数Matrix_Graph() = default;~Matrix_Graph() {}// 图的创建// 1. IO 输入 --- 不方便测试, OJ 中更适合// 2. 图结构关系写到文件, 读取文件// 3. 手动添加边// 构造函数, 接收顶点数组和顶点数量Matrix_Graph(const V *vertexs, int vertexsSize){_vertexs.resize(vertexsSize);for (int i = 0; i < vertexsSize; i++){_vertexs[i] = vertexs[i];_vertexsIndexMap[vertexs[i]] = i;}_matrix.resize(vertexsSize, std::vector<W>(vertexsSize, MAX_W));}// 获取顶点的索引int GetVertexIndex(const V &vertex){auto it = _vertexsIndexMap.find(vertex);if (it != _vertexsIndexMap.end()){return it->second;}else{throw std::invalid_argument("非法顶点");}}// 添加边void _AddEdge(size_t srcIndex, size_t dstIndex, const W &weight){_matrix[srcIndex][dstIndex] = weight;if (!Direction){_matrix[dstIndex][srcIndex] = weight;}}// 外部接口, 接收源顶点和目标顶点以及边权重void AddEdge(const V &src, const V &dst, const W &weight){int srcIndex = GetVertexIndex(src);int dstIndex = GetVertexIndex(dst);_AddEdge(srcIndex, dstIndex, weight);}// 删除边void RemoveEdge(const V &src, const V &dst){int srcIndex = GetVertexIndex(src);int dstIndex = GetVertexIndex(dst);_matrix[srcIndex][dstIndex] = MAX_W;if (!Direction){_matrix[dstIndex][srcIndex] = MAX_W;}}// 显示邻接矩阵void Display(){for (size_t i = 0; i < _vertexs.size(); i++){std::cout << "[" << i << "]" << _vertexs[i] << std::endl;}std::cout << std::endl;// 矩阵// 横下标std::cout << "  ";for (int i = 0; i < _vertexs.size(); i++){std::cout << i << " ";}std::cout << std::endl;for (int i = 0; i < _matrix.size(); i++){// 纵下标std::cout << i << " ";for (int j = 0; j < _matrix[i].size(); ++j){// std::cout << _matrix[i][j] << " ";if (_matrix[i][j] == MAX_W){std::cout << "* ";}else{std::cout << _matrix[i][j] << " ";}}std::cout << std::endl;}std::cout << std::endl;}private:std::vector<V> _vertexs;             // 顶点集合std::map<V, int> _vertexsIndexMap;   // 顶点索引映射std::vector<std::vector<W>> _matrix; // 邻接矩阵的边集合};
}

3.1.4、代码解析

模板类 Matrix_Graph：图的模板类支持灵活的数据类型，MAX_W 定义了边的权重上限。
数据成员：
- _vertexs 存储顶点信息，_vertexsIndexMap 提供顶点到索引的映射，以便快速查找。
- _matrix 使用二维向量作为邻接矩阵，存储边的权重。
成员函数：
- GetVertexIndex：根据顶点值返回其索引，用于边的操作。
- AddEdge 和 RemoveEdge：添加和删除边的函数，支持有向图和无向图。
- Display：展示图的结构，以方便调试和查看图的具体情况。

3.2、邻接表（Adjacency List）

3.2.1、概述

邻接表是一种使用链表或其他动态数据结构存储图的顶点及其相邻边的结构。每个顶点维护一个链表，链表中包含其所有直接相邻的顶点信息。邻接表是一种更适合存储稀疏图的方式，即边数较少的图结构。

3.2.2、特点

空间效率高：邻接表仅需存储实际存在的边，因此空间复杂度为 O(V + E)。
动态性强：相较于邻接矩阵，邻接表在插入和删除顶点或边时更灵活。
适用场景：适合存储稀疏图，或在需要高效遍历顶点相邻节点时使用。

3.2.3、邻接表的实现

以下代码展示了邻接表的实现，其中使用链表节点表示边，每个顶点持有指向邻接表链表头的指针。

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <stdexcept>namespace Lenyiin
{template <class W>struct Table_Edge{int _srcIndex;int _dstIndex;const W &_weight;Table_Edge<W> *_next;Table_Edge(int srcIndex, int dstIndex, const W &weight): _srcIndex(srcIndex), _dstIndex(dstIndex), _weight(weight), _next(nullptr){}};template <class V, class W, bool Direction = false>class Table_Graph{private:typedef struct Table_Edge<W> EdgeNode;public:Table_Graph(V *vertexs, int vertexsSize){_vertexs.resize(vertexsSize);for (int i = 0; i < vertexsSize; i++){_vertexs[i] = vertexs[i];_vertexsIndexMap[vertexs[i]] = i;}_linkTable.resize(vertexsSize, nullptr);}int GetVertexIndex(const V &vertex){auto it = _vertexsIndexMap.find(vertex);if (it != _vertexsIndexMap.end()){return it->second;}else{throw std::invalid_argument("非法顶点");}}void AddEdge(const V &src, const V &dst, const W &weight){int srcIndex = GetVertexIndex(src);int dstIndex = GetVertexIndex(dst);// srcIndex -> dstIndexEdgeNode *newnode = new EdgeNode(srcIndex, dstIndex, weight);newnode->_next = _linkTable[srcIndex];_linkTable[srcIndex] = newnode;// dstIndex -> srcIndexif (!Direction){EdgeNode *newnode = new EdgeNode(dstIndex, srcIndex, weight);newnode->_next = _linkTable[dstIndex];_linkTable[dstIndex] = newnode;}}void Display(){// 顶点for (size_t i = 0; i < _vertexs.size(); i++){std::cout << "[" << i << "]->" << _vertexs[i] << std::endl;}std::cout << std::endl;for (size_t i = 0; i < _linkTable.size(); ++i){std::cout << _vertexs[i] << "[" << i << "]->";EdgeNode *cur = _linkTable[i];while (cur){std::cout << _vertexs[cur->_dstIndex] << ":" << cur->_dstIndex << ":" << cur->_weight << "->";cur = cur->_next;}std::cout << "nullptr" << std::endl;}std::cout << std::endl;}private:std::vector<V> _vertexs;            // 顶点集合std::map<V, int> _vertexsIndexMap;  // 顶点索引映射std::vector<EdgeNode *> _linkTable; // 类似哈希桶结构的邻接表};
}

3.2.4、代码解析

结构体 Table_Edge：用于定义邻接表中的边节点，包含源和目标顶点索引以及权重信息。
邻接表类 Table_Graph：包括对邻接表的管理操作。

GetVertexIndex：返回给定顶点的索引。
- AddEdge：在邻接表中插入边，支持有向图和无向图。
Display：展示图结构，格式为每个顶点指向的链表。

3.3、测试

3.3.1、邻接矩阵测试

#include "Greaph.h"int main()
{Lenyiin::Matrix_Graph<char, int, INT32_MAX> g1("0123", 4); // 无向图g1.AddEdge('0', '1', 1);g1.AddEdge('0', '3', 4);g1.AddEdge('1', '3', 2);g1.AddEdge('2', '3', 8);g1.AddEdge('2', '1', 5);g1.AddEdge('2', '0', 3);std::cout << "无向图" << std::endl;g1.Display();Lenyiin::Matrix_Graph<char, int, INT32_MAX, true> g2("0123", 4); // 有向图g2.AddEdge('0', '1', 1);g2.AddEdge('0', '3', 4);g2.AddEdge('1', '3', 2);g2.AddEdge('2', '3', 8);g2.AddEdge('2', '1', 5);g2.AddEdge('2', '0', 3);std::cout << "\n有向图" << std::endl;g2.Display();return 0;
}

测试结果

3.3.2、邻接表测试

#include "Greaph.h"int main()
{std::string strs[] = {"张三", "李四", "王五", "赵六"};Lenyiin::Table_Graph<std::string, int> g1(strs, sizeof(strs) / sizeof(std::string)); // 无向图g1.AddEdge("张三", "李四", 10);g1.AddEdge("张三", "王五", 20);g1.AddEdge("王五", "赵六", 30);std::cout << "无向图" << std::endl;g1.Display();Lenyiin::Table_Graph<std::string, int, true> g2(strs, sizeof(strs) / sizeof(std::string)); // 有向图g2.AddEdge("张三", "李四", 10);g2.AddEdge("张三", "王五", 20);g2.AddEdge("王五", "赵六", 30);std::cout << "\n有向图" << std::endl;g2.Display();return 0;
}

测试结果

3.4、小结

在本章节中，我们深入探讨了图的两种主要存储结构——邻接矩阵和邻接表，分析了它们各自的优缺点和适用场景。总结如下：

邻接矩阵适合稠密图的表示，尤其是当图中的顶点数量较多且连接较为紧密时。由于邻接矩阵是一种二维数组，它能够在常数时间 O(1) 内判断任意两点之间是否存在边，从而使其在快速查询边的存在性方面表现优越。然而，邻接矩阵的空间复杂度为 O(V^2)，当图是稀疏图时，会占用大量冗余空间，导致内存效率低下。对于静态图，即结构固定且不需要频繁增删顶点或边的图结构，邻接矩阵的实现是一个理想的选择。
邻接表更适合表示稀疏图，即边相对顶点较少的图结构。在邻接表中，每个顶点只存储实际连接的边，这使得邻接表的空间复杂度为 O(V + E)，较为高效。邻接表特别适用于需要频繁遍历顶点相邻边的图算法，例如广度优先搜索（BFS）和深度优先搜索（DFS），以及那些侧重于查找特定节点的连接关系的算法。此外，邻接表在需要动态增删边时更加灵活和高效。
性能和适用场景的对比：
- 邻接矩阵在需要频繁查询边存在性的情况下表现较好，但在稀疏图上会造成较高的空间浪费。
- 邻接表在边数远小于顶点数的稀疏图上更为高效，尤其是在遍历邻接节点和边操作时可以节省大量空间。
实现与代码复用：
- 我们通过模板实现了图的邻接矩阵和邻接表类，这样的设计具有通用性，支持不同的数据类型。
- 对于代码的封装，我们在实现中考虑了有向图和无向图的支持，使其适用于更广泛的图类型。

选择合适的存储结构不仅能提高图算法的效率，还能让代码更简洁、易于维护。开发者在选择邻接矩阵或邻接表时，应根据图的特性、算法需求和内存限制等多方面权衡，以达到最优效果。通过本章节的学习，相信读者对图的存储结构已有了更深入的理解，并能在实践中灵活应用。

4、图的遍历算法

在图的处理和分析中，遍历是核心操作之一。无论是检测图的连通性、查找路径，还是应用在图的其他问题上，遍历算法都扮演着关键角色。图的遍历方法主要分为两种：深度优先遍历（Depth-First Search, DFS） 和 广度优先遍历（Breadth-First Search, BFS）。在本小节中，我们将深入分析这两种遍历算法的原理、实现方式及应用场景，并展示如何在邻接矩阵和邻接表的图结构上实现这些算法。

4.1、深度优先遍历（DFS）

深度优先遍历是一种递归或栈式的遍历方法，类似于树的前序遍历。在 DFS 中，遍历从一个起始顶点出发，不断向前深入访问相邻的未访问节点，直到所有可能路径都走完。DFS 的特点是 “优先深入”，因此适用于查找图中所有可能的路径以及连通性检测。

4.1.1、DFS 原理

从起始节点开始，将其标记为已访问。
访问起始节点的所有邻接节点，对于每个未访问的邻接节点递归地执行 DFS。
当所有邻接节点都访问完毕后，返回上一个节点，继续尝试访问其他未访问的邻接节点。
当所有节点都被访问过，则遍历结束。

4.1.2、基于邻接矩阵的 DFS 实现

以下是 DFS 算法在邻接矩阵和邻接表结构上的实现。

在邻接矩阵中，DFS 通过矩阵的行标识节点，并在遍历时利用矩阵中的边值来决定相邻节点。

#include <iostream>
#include <vector>namespace Lenyiin {template <class V, class W, W MAX_W = INT32_MAX>class Matrix_Graph {public:// 其他省略 ...// 深度优先搜索void DFS(const V &src){std::vector<bool> visited(_vertexs.size(), false);size_t srcIndex = GetVertexIndex(src);_DFS(srcIndex, visited);std::cout << std::endl;}void _DFS(size_t srcIndex, std::vector<bool> &visited){std::cout << srcIndex << ":" << _vertexs[srcIndex] << std::endl;visited[srcIndex] = true;// 找到一个 src 相邻的且没有访问过的点, 去往深度遍历for (int i = 0; i < _matrix.size(); i++){if (_matrix[srcIndex][i] != MAX_W && !visited[i]){_DFS(i, visited);}}}private:// 其他省略 ...};
}

4.1.3、基于邻接表的 DFS 实现

在邻接表中，DFS 使用链表遍历每个节点的相邻节点，避免了不必要的检查，空间复杂度相对更低。

#include <iostream>
#include <vector>
#include <list>namespace Lenyiin {template <class V, class W>class Table_Graph {public:// 其他省略 ...// 深度优先搜索void DFS(const V &src){std::vector<bool> visited(_vertexs.size(), false);int srcIndex = GetVertexIndex(src);_DFS(srcIndex, visited);std::cout << std::endl;}void _DFS(int srcIndex, std::vector<bool> &visited){std::cout << srcIndex << ":" << _vertexs[srcIndex] << std::endl;visited[srcIndex] = true;EdgeNode *cur = _linkTable[srcIndex];while (cur){if (!visited[cur->_dstIndex]){_DFS(cur->_dstIndex, visited);}cur = cur->_next;}}private:// 其他省略 ...};
}

4.1.4、DFS 的应用

连通性检测：DFS 可用于检查图的连通性。对于无向图，可以通过 DFS 从一个节点遍历所有能访问的节点，如果遍历结束后还有未访问的节点，则图为非连通图。
环检测：在无向图和有向图中，DFS 可用于检测环的存在。通过记录访问状态并判断反向边的存在，可以识别图中的环。

4.2、广度优先遍历（BFS）

广度优先遍历是一种层次遍历方法，类似于树的层次遍历。BFS 从起始节点出发，依次访问所有相邻节点，然后再从这些相邻节点开始，依次访问它们的相邻节点，以此类推。

4.2.1、BFS 原理

将起始节点加入队列并标记为已访问。
当队列不为空时，从队首取出一个节点，访问该节点的所有未访问邻接节点，并将这些节点加入队列。
继续以上过程，直到队列为空，则遍历结束。

4.2.2、基于邻接矩阵的 BFS 实现

BFS 的实现同样可以基于邻接矩阵和邻接表，主要区别在于使用队列来管理节点的访问顺序。

#include <iostream>
#include <vector>
#include <queue>namespace Lenyiin {template <class V, class W, W MAX_W = INT32_MAX>class Matrix_Graph {public:// 其他省略 ...// 广度优先void BFS(const V &src){std::vector<bool> visited(_vertexs.size(), false);size_t srcIndex = GetVertexIndex(src);std::queue<int> q;q.push(srcIndex);visited[srcIndex] = true;size_t n = _matrix.size();while (!q.empty()){int levelSize = q.size();while (levelSize--){int curIndex = q.front();q.pop();std::cout << curIndex << ":" << _vertexs[curIndex] << " ";for (size_t i = 0; i < n; i++){if (_matrix[curIndex][i] != MAX_W && !visited[i]){q.push(i);visited[i] = true;}}}std::cout << std::endl;}std::cout << std::endl;}private:// 其他省略 ...};
}

4.2.3、基于邻接表的 BFS 实现

#include <iostream>
#include <vector>
#include <list>
#include <queue>namespace Lenyiin {template <class V, class W>class Table_Graph {public:// 其他省略 ...// 广度优先搜索void BFS(const V &src){std::vector<bool> visited(_vertexs.size(), false);int srcIndex = GetVertexIndex(src);std::queue<int> q;q.push(srcIndex);visited[srcIndex] = true;while (!q.empty()){int curIndex = q.front();q.pop();std::cout << curIndex << ":" << _vertexs[curIndex] << " ";EdgeNode *cur = _linkTable[curIndex];while (cur){int neighbor = cur->_dstIndex;if (!visited[neighbor]){q.push(neighbor);visited[neighbor] = true;}cur = cur->_next;}}std::cout << std::endl;}private:// 其他省略 ...};
}

4.2.4、BFS 的应用

最短路径：BFS 可用于无权图中寻找最短路径。在无向无权图中，从起点执行 BFS 可以找到起点到每个节点的最短路径。
层次遍历：BFS 逐层遍历图的节点，因此适用于需要层次结构的图算法，例如查找从一个节点到另一个节点的最小步骤数。

4.3、测试

4.3.1、邻接矩阵的图的遍历测试

int main()
{std::string strs[] = {"A", "B", "C", "D", "E", "F", "G", "H", "I"};Lenyiin::Table_Graph<std::string, int> g(strs, sizeof(strs) / sizeof(std::string));g.AddEdge("A", "B", 1);g.AddEdge("A", "C", 1);g.AddEdge("A", "D", 1);g.AddEdge("B", "E", 1);g.AddEdge("B", "C", 1);g.AddEdge("C", "F", 1);g.AddEdge("D", "F", 1);g.AddEdge("E", "G", 1);g.AddEdge("F", "H", 1);g.AddEdge("H", "I", 1);g.Display();g.DFS("A");g.BFS("A");return 0;
}

图连通示意图

测试结果：

4.3.2、邻接表的图的遍历测试

int main()
{std::string strs[] = {"A", "B", "C", "D", "E", "F", "G", "H", "I"};Lenyiin::Table_Graph<std::string, int> g(strs, sizeof(strs) / sizeof(std::string));g.AddEdge("A", "B", 1);g.AddEdge("A", "C", 1);g.AddEdge("A", "D", 1);g.AddEdge("B", "E", 1);g.AddEdge("B", "C", 1);g.AddEdge("C", "F", 1);g.AddEdge("D", "F", 1);g.AddEdge("E", "G", 1);g.AddEdge("F", "H", 1);g.AddEdge("H", "I", 1);g.Display();std::cout << "邻接矩阵的深度优先搜索顺序:\n";g.DFS("A");std::cout << "邻接矩阵的广度优先搜索顺序:\n";g.BFS("A");return 0;
}

测试结果：

4.4、小结

在本章节中，我们探讨了图的两种遍历算法——深度优先搜索（DFS） 和 广度优先搜索（BFS），并在邻接矩阵和邻接表的两种存储结构上进行了实现。这两种遍历方法各有优劣，DFS 在查找路径和连通性方面表现优异，而 BFS 更适合最短路径和层次遍历。理解这两种算法的实现和应用，可以为后续深入研究复杂图算法奠定坚实基础。

5、最小生成树算法

5.1、图的最小生成树算法

在图论中，最小生成树 (Minimum Spanning Tree, MST) 是一个无向加权图的一个子集，它包含图中所有节点的树结构，并且通过最小的边权值形成一个无环的连通子图。对于无向连通图，其最小生成树的边数为 V−1，其中 V 表示节点数。最小生成树在网络设计（如电网布局、交通路线等）中具有广泛应用。常见的最小生成树算法包括 Kruskal 算法 和 Prim 算法，本文将基于邻接矩阵和邻接表分别实现并解析这两种算法。

最小生成树的定义与性质：

在无向加权图中，最小生成树具有以下性质：

生成树包含图中所有的顶点。
生成树的边数为 V-1，其中 V 为图的顶点数。
生成树是无环的连通子图。
生成树的总权重最小。

5.2、Kruskal 算法

Kruskal 算法是一种贪心算法，用于在无向加权图中构建最小生成树（MST）。算法的核心思想是按权重从小到大选择边，确保在没有形成环的前提下将其添加到生成树中。以下是算法的执行步骤：

对边按权重排序：将图中所有边按权重从小到大排序。
并查集：使用并查集（Union-Find）结构来检测环。
逐步加入边：从最小权重的边开始，依次加入生成树（若不会形成环），直到加入 V-1 条边。

Kruskal 算法通常适用于边稀疏的图，因为它只需要维护边集的排序，而不要求对顶点做邻接操作。这使得 Kruskal 在 边数远小于顶点数的图中效率较高。特别是对于网络设计（如公路、通信网络），该算法可以帮助找到低成本的连接方案。

对并查集不熟悉的可以阅读我的这篇技术博客：《 C++ 修炼全景指南：十五》突破算法极限：并查集如何轻松搞定最棘手的连通性问题？

5.2.1、基于邻接矩阵的 Kruskal 算法的实现

// 最小生成树
W Kruskal(Self &minTree)
{// 初始化size_t n = _vertexs.size();minTree._vertexs = _vertexs;minTree._vertexsIndexMap = _vertexsIndexMap;minTree._matrix.resize(n, std::vector<W>(n, MAX_W));std::priority_queue<EdgeNode, std::vector<EdgeNode>, std::greater<EdgeNode>> minque;for (size_t i = 0; i < n; i++){for (size_t j = 0; j < i; j++){if (_matrix[i][j] != MAX_W){minque.push(EdgeNode(i, j, _matrix[i][j]));}}}// 选出 n-1 条边std::vector<int> ufs(n, -1);int size = n - 1;W sumW = W();while (!minque.empty()){EdgeNode min = minque.top();minque.pop();int srcIndex = min._srcIndex;int dstIndex = min._dstIndex;while (ufs[srcIndex] != -1){srcIndex = ufs[srcIndex];}while (ufs[dstIndex] != -1){dstIndex = ufs[dstIndex];}if (srcIndex != dstIndex){std::cout << _vertexs[min._srcIndex] << "->" << _vertexs[min._dstIndex] << ":" << min._weight << std::endl;minTree._AddEdge(min._srcIndex, min._dstIndex, min._weight);ufs[srcIndex] = dstIndex;sumW += min._weight;--size;}else{std::cout << "构成环: " << _vertexs[min._srcIndex] << "->" << _vertexs[min._dstIndex] << ":" << min._weight << std::endl;}}if (size != 0){std::cout << "图不连通";return W();}return sumW;
}

5.2.2、基于邻接矩阵的 Kruskal 算法的测试

int main()
{const char *str = "abcdefghi";Lenyiin::Matrix_Graph<char, int> g(str, strlen(str));g.AddEdge('a', 'b', 4);g.AddEdge('a', 'h', 8);// g.AddEdge('a', 'h', 9);g.AddEdge('b', 'c', 8);g.AddEdge('b', 'h', 11);g.AddEdge('c', 'i', 2);g.AddEdge('c', 'f', 4);g.AddEdge('c', 'd', 7);g.AddEdge('d', 'f', 14);g.AddEdge('d', 'e', 9);g.AddEdge('e', 'f', 10);g.AddEdge('f', 'g', 2);g.AddEdge('g', 'h', 1);g.AddEdge('g', 'i', 6);g.AddEdge('h', 'i', 7);g.Display();Lenyiin::Matrix_Graph<char, int> kminTree;std::cout << "Kruskal:" << std::endl;std::cout << g.Kruskal(kminTree) << "\n\n";kminTree.Display();
}

测试结果：

5.2.3、基于邻接表的 Kruskal 算法的实现：

// 最小生成树
W Kruskal(Self &minTree)
{// 初始化size_t n = _vertexs.size();minTree._vertexs = _vertexs;minTree._vertexsIndexMap = _vertexsIndexMap;minTree._linkTable.resize(n, nullptr);std::priority_queue<EdgeNode, std::vector<EdgeNode>, std::greater<EdgeNode>> minque;for (int i = 0; i < n; i++){EdgeNode *cur = _linkTable[i];while (cur){minque.push(EdgeNode(cur->_srcIndex, cur->_dstIndex, cur->_weight));cur = cur->_next;}}// 选出 n - 1 条边std::vector<int> ufs(n, -1);int size = n - 1;W sumW = W();while (!minque.empty()){EdgeNode min = minque.top();minque.pop();int srcIndex = min._srcIndex;int dstIndex = min._dstIndex;while (ufs[srcIndex] != -1){srcIndex = ufs[srcIndex];}while (ufs[dstIndex] != -1){dstIndex = ufs[dstIndex];}if (srcIndex != dstIndex){std::cout << _vertexs[min._srcIndex] << "->" << _vertexs[min._dstIndex] << ":" << min._weight << std::endl;minTree._AddEdge(min._srcIndex, min._dstIndex, min._weight);ufs[srcIndex] = dstIndex;sumW += min._weight;--size;}else{std::cout << "构成环: " << _vertexs[min._srcIndex] << "->" << _vertexs[min._dstIndex] << ":" << min._weight << std::endl;}}if (size != 0){std::cout << "图不连通";return W();}return sumW;
}

在以上代码中，KruskalMST 方法使用了并查集结构来检测环，并确保生成的树连通。AddEdge 方法用于构造图的边集，生成图的最小生成树。

5.2.4、基于邻接表的 Kruskal 算法的测试

int main()
{const char *str = "abcdefghi";Lenyiin::Table_Graph<char, int> g(str, strlen(str));g.AddEdge('a', 'b', 4);g.AddEdge('a', 'h', 8);g.AddEdge('b', 'c', 8);g.AddEdge('b', 'h', 11);g.AddEdge('c', 'i', 2);g.AddEdge('c', 'f', 4);g.AddEdge('c', 'd', 7);g.AddEdge('d', 'f', 14);g.AddEdge('d', 'e', 9);g.AddEdge('e', 'f', 10);g.AddEdge('f', 'g', 2);g.AddEdge('g', 'h', 1);g.AddEdge('g', 'i', 6);g.AddEdge('h', 'i', 7);g.Display();Lenyiin::Table_Graph<char, int> kminTree;std::cout << "Kruskal:" << std::endl;std::cout << g.Kruskal(kminTree) << "\n\n";kminTree.Display();
}

测试结果：

5.2.5、Kruskal 算法的复杂度分析

时间复杂度：
- 边排序：O(Elog⁡E) ，其中 E 是边的数量。
- 并查集操作：每次合并和查找的均摊复杂度是 O(α(V))，其中 α 为阿克曼函数的反函数。
- 综合复杂度：O(Elog⁡E+Eα(V)) ，其中 Elog⁡E 为主要开销。
空间复杂度：需要存储边列表和并查集，空间复杂度为 O(E+V) 。

5.2.6、复杂案例分析

图中存在负权边：Kruskal 算法可直接处理负权边，无需特殊处理。
多连通分量：在非连通图上运行时，Kruskal 算法会找到一个生成森林而非单棵树。
边界条件：对于无边或仅有单节点的图，算法应处理特例，确保代码的鲁棒性。

5.3、Prim 算法

Prim 算法是另一种用于构建无向加权图最小生成树（MST）的贪心算法。它的核心思想是从一个起始顶点开始，不断地扩展到权重最小且未加入生成树的邻接边，直到生成树包含了所有顶点。它与 Kruskal 算法不同，Prim 是基于顶点而不是边的选择，适用于稠密图，即边较多的图。

初始化：选取任意顶点作为生成树的起点。
选择最小边：从当前生成树的边中选择权重最小且不构成环的边，加入生成树。
重复步骤2：直到生成树包含所有顶点。

5.3.1、Prim 算法的应用场景

Prim 算法广泛用于网络设计（如电网、通信网络等），尤其适用于稠密图，因为它在每步只选择与当前生成树直接相连的最小边，避免了遍历整个边集。相比于 Kruskal，Prim 更适合于具有较多边的图，因为它在寻找最小权重边的过程中可以利用优先队列进行优化。

5.3.2、数据结构选择

邻接表或邻接矩阵：邻接矩阵适用于稠密图（如电路设计），而邻接表适用于稀疏图。Prim 算法可以用邻接矩阵实现，但在稀疏图中使用邻接表搭配最小优先队列效果更佳。

最小优先队列（Min-Heap）：使用优先队列可以快速找到与生成树相连的最小权重边。一般选择最小堆实现，更新相邻顶点的最短距离时可以高效地调整堆结构。

5.3.3、算法的复杂度分析

时间复杂度：
- 使用邻接矩阵实现的 Prim 算法：O(V²) ，其中 V 为顶点数量，适用于密集图。
- 使用邻接表 + 最小堆（Min-Heap）实现的 Prim 算法：O((V+E)log⁡V) ，其中 E 是边的数量。这是稀疏图的高效实现。
空间复杂度：需要维护邻接表或邻接矩阵、最小堆和辅助数组（如记录节点是否在生成树内），空间复杂度为 O(V+E) 。

5.3.4、邻接表与邻接矩阵实现的选择

邻接矩阵实现的 Prim 适用于边较多的图，而在边稀疏的图中，使用邻接表搭配最小堆能显著提高效率。邻接表的结构可以让我们遍历每个节点的直接邻居，这比遍历整个边集更加高效。

5.3.5、基于邻接矩阵的 Prim 算法的实现

// 最小生成树
W Prim(Self &minTree, const W &src)
{size_t srcIndex = GetVertexIndex(src);size_t n = _vertexs.size();minTree._vertexs = _vertexs;minTree._vertexsIndexMap = _vertexsIndexMap;minTree._matrix.resize(n, std::vector<W>(n, MAX_W));std::set<int> X;std::set<int> Y;X.insert(srcIndex);for (size_t i = 0; i < n; i++){if (i != srcIndex){Y.insert(i);}}// 从 X -> Y 集合中连接的边里面选出最小的边std::priority_queue<EdgeNode, std::vector<EdgeNode>, std::greater<EdgeNode>> minque;// 先把 src 连接的边放到 minque 中for (size_t i = 0; i < n; i++){if (_matrix[srcIndex][i] != MAX_W){minque.push(EdgeNode(srcIndex, i, _matrix[srcIndex][i]));}}size_t size = n - 1;W sumW = W();while (!minque.empty()){EdgeNode min = minque.top();minque.pop();if (X.find(min._dstIndex) != X.end()){// 构成环std::cout << "构成环: " << _vertexs[min._srcIndex] << "->" << _vertexs[min._dstIndex] << ":" << min._weight << std::endl;continue;}minTree._AddEdge(min._srcIndex, min._dstIndex, min._weight);std::cout << _vertexs[min._srcIndex] << "->" << _vertexs[min._dstIndex] << ":" << min._weight << std::endl;X.insert(min._dstIndex);Y.erase(min._dstIndex);sumW += min._weight;--size;if (size == 0){break;}// 更新 minquefor (auto it = Y.begin(); it != Y.end(); it++){int y = *it;if (_matrix[min._dstIndex][y] != MAX_W){minque.push(EdgeNode(min._dstIndex, y, _matrix[min._dstIndex][y]));}}}if (size != 0){std::cout << "图不连通";return W();}return sumW;
}

5.3.6、基于邻接矩阵的 Prim 算法的测试

int main()
{const char *str = "abcdefghi";Lenyiin::Matrix_Graph<char, int> g(str, strlen(str));g.AddEdge('a', 'b', 4);g.AddEdge('a', 'h', 8);// g.AddEdge('a', 'h', 9);g.AddEdge('b', 'c', 8);g.AddEdge('b', 'h', 11);g.AddEdge('c', 'i', 2);g.AddEdge('c', 'f', 4);g.AddEdge('c', 'd', 7);g.AddEdge('d', 'f', 14);g.AddEdge('d', 'e', 9);g.AddEdge('e', 'f', 10);g.AddEdge('f', 'g', 2);g.AddEdge('g', 'h', 1);g.AddEdge('g', 'i', 6);g.AddEdge('h', 'i', 7);g.Display();Lenyiin::Matrix_Graph<char, int> pminTree;std::cout << "Prim:" << std::endl;std::cout << g.Prim(pminTree, 'a') << "\n\n";pminTree.Display();// for (size_t i = 0; i < strlen(str); i++)// {//     std::cout << "Prim 从 " << str[i] << " 开始:" << std::endl;//     std::cout << g.Prim(pminTree, str[i]) << "\n\n";// }
}

测试结果：

5.3.7、基于邻接表的 Prim 算法的实现

// 最小生成树
W Prim(Self &minTree, const W &src)
{size_t srcIndex = GetVertexIndex(src);size_t n = _vertexs.size();minTree._vertexs = _vertexs;minTree._vertexsIndexMap = _vertexsIndexMap;minTree._linkTable.resize(n, nullptr);std::set<int> X;std::set<int> Y;X.insert(srcIndex);for (size_t i = 0; i < n; i++){if (i != srcIndex){Y.insert(i);}}// 从 X -> Y 集合中连接的边里面选出最小的边std::priority_queue<EdgeNode, std::vector<EdgeNode>, std::greater<EdgeNode>> minque;// 先把 src 连接的边放到 minque 中EdgeNode *cur = _linkTable[srcIndex];while (cur){minque.push(EdgeNode(cur->_srcIndex, cur->_dstIndex, cur->_weight));cur = cur->_next;}size_t size = n - 1;W sumW = W();while (!minque.empty()){EdgeNode min = minque.top();minque.pop();if (X.find(min._dstIndex) != X.end()){// 构成环std::cout << "构成环: " << _vertexs[min._srcIndex] << "->" << _vertexs[min._dstIndex] << ":" << min._weight << std::endl;continue;}minTree._AddEdge(min._srcIndex, min._dstIndex, min._weight);std::cout << _vertexs[min._srcIndex] << "->" << _vertexs[min._dstIndex] << ":" << min._weight << std::endl;X.insert(min._dstIndex);Y.erase(min._dstIndex);sumW += min._weight;--size;if (size == 0){break;}// 更新 minqueEdgeNode *cur = _linkTable[min._dstIndex];while (cur){if (Y.find(cur->_dstIndex) != Y.end()){minque.push(EdgeNode(cur->_srcIndex, cur->_dstIndex, cur->_weight));}cur = cur->_next;}}if (size != 0){std::cout << "图不连通";return W();}return sumW;
}

以上代码展示了 Prim 算法的完整实现。PrimMST 方法从指定顶点 start 开始，使用优先队列来选择权重最小的边，扩展生成树。

5.3.8、基于邻接表的 Prim 算法的测试

int main()
{const char *str = "abcdefghi";Lenyiin::Table_Graph<char, int> g(str, strlen(str));g.AddEdge('a', 'b', 4);g.AddEdge('a', 'h', 8);g.AddEdge('b', 'c', 8);g.AddEdge('b', 'h', 11);g.AddEdge('c', 'i', 2);g.AddEdge('c', 'f', 4);g.AddEdge('c', 'd', 7);g.AddEdge('d', 'f', 14);g.AddEdge('d', 'e', 9);g.AddEdge('e', 'f', 10);g.AddEdge('f', 'g', 2);g.AddEdge('g', 'h', 1);g.AddEdge('g', 'i', 6);g.AddEdge('h', 'i', 7);g.Display();Lenyiin::Table_Graph<char, int> pminTree;std::cout << "Prim:" << std::endl;std::cout << g.Prim(pminTree, 'a') << "\n\n";pminTree.Display();// for (size_t i = 0; i < strlen(str); i++)// {//     std::cout << "Prim 从 " << str[i] << " 开始:" << std::endl;//     std::cout << g.Prim(pminTree, str[i]) << "\n\n";// }
}

测试结果：

5.3.9、复杂案例分析

负权边：Prim 算法可以处理负权边，只需确保不形成负环。
多连通分量：对于非连通图，可以修改 Prim 算法以构建最小生成森林。可从任一顶点开始应用 Prim，并重复该过程直至覆盖所有连通分量。
边界条件：需要考虑只有一个顶点或无边的图结构。确保算法在这些情况下返回正确的结果，保持鲁棒性。

5.3.10、Prim 算法的优化

最小堆优化：在稀疏图中使用最小堆来快速找到最小权重边，确保每次查找的复杂度为 O(log⁡V)O(\log V)O(logV)。
启发式改进：可在特定应用场景中使用启发式，例如在地理网络中使用空间距离作为初始排序策略，减少后续查找时间。

综上，Prim 算法提供了一种通过贪心方法构建最小生成树的有效手段。利用优先队列和邻接表的结构，Prim 算法在稠密图中的效率显著优于 Kruskal。同时，结合上述优化和细节分析，可以进一步提高算法的应用广度与实用性。

5.4、Prim 算法与 Kruskal 算法的比较

时间复杂度：在稠密图中，Prim 的 O(V²) 复杂度更具优势；而 Kruskal 更适用于稀疏图的边集排序。
连接检查方式：Prim 通过直接连接当前生成树的边进行扩展，不需要额外的连通分量检查；Kruskal 则需要并查集辅助管理连通性。
适用场景：Prim 更适合于有大量边的网络设计，而 Kruskal 通常适合于相对较少边的图。

5.5、小结

Kruskal 和 Prim 是构建无向加权图最小生成树（MST）的两大经典贪心算法。虽然两者的目标相同，但在实现方式、数据结构选择、适用场景、复杂度和细节处理上各具特点。以下将从多个角度详细比较并总结两者的特性和适用性。

5.5.1、算法原理与流程对比

Kruskal 算法：基于边的贪心策略，从全局视角出发，将图中的所有边按权重升序排序，逐步加入生成树，避免形成环，直到树包含 V−1条边。算法核心在于边的选择顺序和连通性检查，常采用并查集数据结构来高效判断不同连通分量的合并。
Prim 算法：Prim 通过顶点扩展生成树，逐步添加与当前生成树相连的最小权重边。它从起始顶点出发，利用优先队列逐步选择最小权重边来扩展生成树，每次都从当前树的邻接边集中选取边，而无需对全局边集进行排序。这使得 Prim 在稠密图中效率较高。

5.5.2、数据结构选择

Kruskal 算法的数据结构：
- 边集：需要全局访问边集并对其排序，适合存储在数组或向量中。
- 并查集：高效管理节点连通性，帮助判断边的加入是否形成环。并查集的路径压缩和按秩合并优化使得查询和合并操作达到近乎常数时间复杂度 O(α(V))。
Prim 算法的数据结构：
- 邻接表/邻接矩阵：在稠密图中更倾向使用邻接矩阵，而在稀疏图中使用邻接表。邻接表可以有效减少冗余访问，配合优先队列实现。
- 最小堆（优先队列）：常用最小堆实现优先队列，快速选择最小权重边，并更新邻接顶点的最短距离。

5.5.3、复杂度分析

时间复杂度：
- Kruskal 算法：主要耗时在对边集的排序，复杂度为 O(Elog⁡E) ；而并查集的操作由于路径压缩和按秩合并的优化，可视为 O(Elog⁡V) 。
- Prim 算法：在邻接矩阵实现中，每次选择最小权重边的过程为 O(V²) ；而在稀疏图中使用邻接表 + 最小堆优化，复杂度可降低为 O((V+E)log⁡V) 。
空间复杂度：两者在存储图结构时的空间复杂度均为 O(V+E) ，但 Kruskal 需要额外的并查集空间，而 Prim 需要优先队列。

5.5.4、适用场景对比

Kruskal 的优势：适合边较少的稀疏图，尤其是当边集规模较小时，Kruskal 的边排序优势明显，并查集也可以高效管理连通性。因此，Kruskal 通常应用于边稀疏且不容易出现多重边的场景中，如网络协议设计和路径优化问题。
Prim 的优势：在稠密图中表现出色。由于 Prim 每次仅选择与生成树相连的最小边，无需全局排序，且与优先队列配合可进一步降低复杂度。因此，Prim 常用于网络设计、传输和图像处理等稠密图场景，能够在不需全部遍历边的情况下快速得到生成树。

5.5.5、算法的拓展与优化

Kruskal 算法的拓展：在带有负权边和多连通分量的图中，Kruskal 可以通过对边集的特殊排序处理形成最小生成森林。此外，借助并查集的启发式优化，能加速边的连通性检查。对于特殊应用场景，Kruskal 还能与启发式搜索结合，解决部分多维优化问题。
Prim 算法的拓展：Prim 能处理负权边，通过起始点设置，可以生成最小生成森林。结合启发式和空间距离优化，Prim 常用于几何图形中的距离最小化问题，并能在3D建模和路径计算等领域中提供较高的计算效率。

5.5.6、实现的技术要点与难点

Kruskal 的实现要点：边集排序和并查集操作是 Kruskal 的关键。并查集的路径压缩和按秩合并优化使得算法复杂度大幅降低，同时确保了连通性管理的高效性。实现时要特别注意避免重复加入边、控制边集操作顺序。
Prim 的实现要点：在 Prim 中，使用最小堆来保持最小权重边的高效访问是重点。具体实现时需控制堆的更新和出堆操作，确保邻接顶点的最小权重值准确。为了避免冗余计算，还需确保每个顶点仅进入生成树一次，这要求优先队列的构造与维护非常高效。

5.5.7、Kruskal 和 Prim 的互补性

尽管 Kruskal 和 Prim 的算法思想和操作细节不同，它们在应用中却可以互为补充。在图设计过程中，可根据边密度灵活选择合适的算法；在分布式计算和网络优化中，Kruskal 能高效构建稀疏连通图，而 Prim 则擅长快速处理密集连通图。在多连通分量的图中，结合两者的特性可以优化最小生成森林的构造。

5.5.8、小结

Kruskal 和 Prim 算法各自针对不同的图结构和应用场景提供了高效的最小生成树构建方式。Kruskal 适合稀疏图，通过并查集保证了快速的连通性检查，而 Prim 适用于稠密图，结合最小堆能减少不必要的边访问。在实际应用中，两者的组合使用可以实现更灵活高效的图结构优化。这两种算法不仅在图论中具有重要地位，同时还在网络、通信、图像处理等领域中发挥了重要作用，深入理解并应用两者有助于在复杂问题中找到更优解。

下面内容近两天更新完毕

6、最短路径算法

Dijkstra算法：
- 算法原理：贪心算法的本质。
- 技术实现与优化：使用优先队列提升效率。
- 应用场景：网络路由、交通导航等。
Bellman-Ford算法：
- 支持负权边的图。
- 技术细节：迭代与边松弛过程。
Floyd-Warshall算法：
- 适用于全局最短路径计算。
- 动态规划思想及其实现。
A*算法：
- 启发式搜索，结合贪心算法和Dijkstra算法的优势。
应用场景：游戏AI、路径规划。

7、连通性问题

强连通分量：
- Kosaraju算法与Tarjan算法。
- 实现过程及其在有向图中的应用。
割点与桥：
- 割点和桥的定义与其对图结构的影响。
- 深入分析如何使用DFS寻找割点与桥。
双连通分量：基于Tarjan算法的实现。

8、二分图与匹配

什么是二分图？：定义和性质。
最大匹配问题：
- 匈牙利算法：深度优先搜索的应用。
- Hopcroft-Karp算法：时间优化实现。
二分图的应用：工作分配、图像分割等。

9、图的高级算法

网络流：
- 最大流问题：Ford-Fulkerson算法及其改进版Edmonds-Karp算法。
- 最小割定理与其应用。
- Dinic算法：时间复杂度的优化。
图的颜色问题：
- 图的着色：贪心算法与回溯法。
- NP问题：图着色问题的复杂度分析。
哈密顿路径与欧拉路径：
- 介绍这两类路径的区别和算法实现。
NP完全问题与启发式解法。

10、图算法的优化与大规模图处理

并行计算与分布式图处理：
- 讨论如何使用并行和分布式方法处理超大规模图。
- Google的Pregel模型和Apache Giraph介绍。
图的压缩表示：稀疏矩阵压缩、CSR（Compressed Sparse Row）等存储方式。
动态图算法：支持边动态添加和删除的图算法。

11、实际应用与案例分析

社交网络中的应用：好友推荐算法、社区发现算法。
交通网络中的应用：路径规划与导航。
物联网（IoT）中的图模型：设备之间的连通性与数据流动优化。
其他应用：基因网络分析、网页排名（PageRank）、化学分子分析等。

12、面试中的常见图问题

图遍历相关问题：如图的连通分量检查、路径搜索。
最短路径问题：Dijkstra的变体问题。
最小生成树问题：结合Kruskal与Prim的实际应用。
图的连通性问题：如何快速判断图中某两点是否连通。

13、总结

图算法的广泛应用：总结图算法在各行各业中的关键作用。
学习与优化图算法的建议：通过实践和深入理解提高对图算法的掌握。
后续阅读与研究方向：推荐一些高级文献和教材。

uskal 适合稀疏图，通过并查集保证了快速的连通性检查，而 Prim 适用于稠密图，结合最小堆能减少不必要的边访问。在实际应用中，两者的组合使用可以实现更灵活高效的图结构优化。这两种算法不仅在图论中具有重要地位，同时还在网络、通信、图像处理等领域中发挥了重要作用，深入理解并应用两者有助于在复杂问题中找到更优解。

下面内容近两天更新完毕

6、最短路径算法

Dijkstra算法：
- 算法原理：贪心算法的本质。
- 技术实现与优化：使用优先队列提升效率。
- 应用场景：网络路由、交通导航等。
Bellman-Ford算法：
- 支持负权边的图。
- 技术细节：迭代与边松弛过程。
Floyd-Warshall算法：
- 适用于全局最短路径计算。
- 动态规划思想及其实现。
A*算法：
- 启发式搜索，结合贪心算法和Dijkstra算法的优势。
应用场景：游戏AI、路径规划。

7、连通性问题

强连通分量：
- Kosaraju算法与Tarjan算法。
- 实现过程及其在有向图中的应用。
割点与桥：
- 割点和桥的定义与其对图结构的影响。
- 深入分析如何使用DFS寻找割点与桥。
双连通分量：基于Tarjan算法的实现。

8、二分图与匹配

什么是二分图？：定义和性质。
最大匹配问题：
- 匈牙利算法：深度优先搜索的应用。
- Hopcroft-Karp算法：时间优化实现。
二分图的应用：工作分配、图像分割等。

9、图的高级算法

网络流：
- 最大流问题：Ford-Fulkerson算法及其改进版Edmonds-Karp算法。
- 最小割定理与其应用。
- Dinic算法：时间复杂度的优化。
图的颜色问题：
- 图的着色：贪心算法与回溯法。
- NP问题：图着色问题的复杂度分析。
哈密顿路径与欧拉路径：
- 介绍这两类路径的区别和算法实现。
NP完全问题与启发式解法。