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

id="article_content" class="article_content clearfix"> id="content_views" class="markdown_views prism-tomorrow-night">

在这里插入图片描述

摘要

本篇博客系统地介绍了图论的核心内容，深入探讨图的基本概念、存储结构和遍历方法，详细分析了经典的最短路径算法（Dijkstra、Bellman-Ford、Floyd-Warshall）及其适用场景。博客进一步介绍了拓扑排序、连通性检测等基础算法，结合实际应用如任务调度和网络连通分析，为读者提供了清晰的学习路径。在高级算法方面，涵盖了网络流问题（最大流与最小割）、图着色、哈密顿与欧拉路径、NP问题等复杂主题，并探索了大规模图处理与算法优化。实际应用案例展示了图论在通信、交通、社交网络等领域的应用。最后，博客总结了面试中常见的图问题，为读者提供了解决面试题的实用技巧。该博客既适合理论学习，也对实际应用与面试有重要参考价值。

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 
#include 
#include 
#include 
#include 

namespace Lenyiin
{
	// 定义边的结构体, 包含源节点、目标节点和权重
    template 
    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 Matrix_Graph
    {
    private:
        typedef Matrix_Graph Self;
        typedef struct Matrix_Edge 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(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 _vertexs;             // 顶点集合
        std::map _vertexsIndexMap;   // 顶点索引映射
        std::vector> _matrix; // 邻接矩阵的边集合
    };
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

算法	适用图类型	时间复杂度	优点	缺点
`Dijkstra`	无负权边图	`O(Elog⁡V)`	计算效率高，适合单源最短路径问题，适合稀疏图	不支持负权边，不适合多源问题
`Bellman-Ford`	允许负权边的图	`O(V×E)`	支持负权边，能检测负权环，适用于负权边图	速度慢，适合稠密图，无法一次性计算多源最短路径
`Floyd-Warshall`	任意加权图	O(V³)	解决多源最短路径问题，支持负权边，能方便地生成完整的最短路径矩阵	复杂度较高，不适合大规模稀疏图，无法直接检测负权环

摘要

1、引言

1.1、什么是图？

1.2、图的实际应用场景

1.3、博客目标

2、图的基本概念

2.1、图的定义与基本术语

2.2、图的分类

2.3、图的表示方法

2.4、图的基本性质

2.5、图的遍历方式

2.6、图的特殊类型

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

2.8、图的理论基础

2.9、图的实际应用

2.10、图的性质小结

3、图的存储结构

3.1、邻接矩阵（Adjacency Matrix）

3.1.1、概述

3.1.2、特点

3.1.3、邻接矩阵的实现

3.1.4、代码解析

3.2、邻接表（Adjacency List）

3.2.1、概述

3.2.2、特点

3.2.3、邻接表的实现

3.2.4、代码解析

3.3、测试

3.3.1、邻接矩阵测试

3.3.2、邻接表测试

3.4、小结

4、图的遍历算法

4.1、深度优先遍历（DFS）

4.1.1、DFS 原理

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

4.1.3、基于邻接表的 DFS 实现

4.1.4、DFS 的应用

4.2、广度优先遍历（BFS）

4.2.1、BFS 原理

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

4.2.3、基于邻接表的 BFS 实现

4.2.4、BFS 的应用

4.3、测试

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

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

4.4、小结

5、最小生成树算法

5.1、图的最小生成树算法

5.2、Kruskal 算法

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

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

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

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

5.2.5、Kruskal 算法的复杂度分析

5.2.6、复杂案例分析

5.3、Prim 算法

5.3.1、Prim 算法的应用场景

5.3.2、数据结构选择

5.3.3、算法的复杂度分析

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

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

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

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

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

5.3.9、复杂案例分析

5.3.10、Prim 算法的优化

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

5.5、小结

5.5.1、算法原理与流程对比

5.5.2、数据结构选择

5.5.3、复杂度分析

5.5.4、适用场景对比

5.5.5、算法的拓展与优化

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

5.5.7、Kruskal 和 Prim 的互补性

5.5.8、小结

6、最短路径算法

6.1、图的最短路径概述

6.1.1、最短路径的基本概念

6.1.2、最短路径问题的分类