图论基础复习【并查集 | 图遍历 | 最小生成树

博客主页：花果山~程序猿-CSDN博客

文章分栏：高阶数据结构_花果山~程序猿的博客-CSDN博客

关注我一起学习，一起进步，一起探索编程的无限可能吧！让我们一起努力，一起成长！

一，并查集

查找

合并

应用题

二，图

图的基本概念

图的存储结构

1.邻接矩阵

优势

缺点

2.邻接表

优势

图的遍历（邻接矩阵）

1.广度优先遍历

2.深度优先遍历

三，最小生成树

Kruskal算法

Prim算法

两种算法为什么能保证得到最小生成树？

前提

四，最短路径

1.Dijkstra算法

2.Bellman-Ford算法

3.floyd-warshall算法

嗨！收到一张超美的图，愿你每天都能顺心！

一，并查集

并查集（Union-Find）是一种数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。它在算法中非常有用，尤其是在图论中处理连通性问题时。

并查集能够高效地支持两种操作：

查找（Find）：确定元素属于哪一个子集。它可以用来确定两个元素是否位于同一个子集中。
合并（Union）：将两个子集合并成一个单一的集合。

关于理解 树与树之间的合并：

1.当数据量比较少时，让一个树的根作为另一棵树的子树，并修改val值即可。

2.如果按照1方法进行树与树之间合并，当数据量比较大时，调用查找获取所在树时，需要经历多次"跳跃"，因此在该情况下，应将子树拆散，直接作为孩子，提高效率（这也是路径压缩的算法思路）。

查找

寻找到目标的根下标

size_t GetRoot(size_t order)
{
	    int root = order;
		while (_union_set[root] >= 0)
		{
			root = _union_set[root];
		}
		
		// 开始向上压缩---数据量打时采用压缩算法
		while (_union_set[order] >= 0)
		{
			int parent = _union_set[order];
			_union_set[order] = root;
			order = parent;
		}
		return root;
}

合并

    void _union(size_t a, size_t b)
	{
        a = GetRoot(a);
        b = GetRoot(b);
        if (a == b) return; // 相同树，不合并
		if (a > b)
			swap(a, b);

		_union_set[a] += _union_set[b];
		_union_set[b] = a;

	}

应用题

LCR 116. 省份数量 - 力扣（LeetCode）

990. 等式方程的可满足性 - 力扣（LeetCode）

二，图

图是一种非线性数据结构，它由顶点（Vertices）和边（Edges）组成，用于表示对象之间的多对多关系。图在许多领域都有广泛的应用，比如社交网络分析、路由算法、编译器优化等。

图的基本概念

顶点（Vertex/Node）：图中的基本单位，代表一个实体。
边（Edge）：连接两个顶点的线，表示这两个顶点之间存在某种关系。
有向图（Directed Graph）：边是有方向的，从一个顶点指向另一个顶点。

无向图（Undirected Graph）：边是没有方向的，表示两个顶点是相互连接的。

加权图（Weighted Graph）：每条边上都关联有一个权重值，通常用来表示成本或距离，这个可以灵活多变的。
路径（Path）：一系列相连的边，构成从一个顶点到另一个顶点的路线。
连通图（Connected Graph）：对于无向图，如果任意两个顶点之间都存在一条路径，则称该图为连通图；
对于有向图，若存在一条从任何顶点到其他所有顶点的路径，则称为强连通图。
环（Cycle）：一条起始顶点和结束顶点相同的路径。
度（Degree）：与某个顶点相连的边的数量。在有向图中分为入度（进入顶点的边数）和出度（离开顶点的边数）。

图的存储结构

1.邻接矩阵

因为图中既有节点，又有边(节点与节点之间的关系)，因此， 在图的存储中，只需要保存：节点和边关系即可。节点保存比较简单，只需要一段连续空间即可，那边关系该怎么保存呢？

注意：

如果边带有权值，并且两个节点之间是连通的，上图中的边的关系就用权值代替，如果 两个顶点不通，则使用 无穷大代替。

优势

邻接矩阵适合稠密图，即：相同成本下，边(关系越复杂)越多，矩阵利用率越高。
矩阵能在O（1）内判断两顶点的关系，并获取到权值。

缺点

无法快速获取一个顶点所连接的所有顶点——O（n），遍历一层。

框架图：如下

具体代码：

Graph/Graph.hpp · 逆光/Cpp - 码云 - 开源中国

2.邻接表

邻接表：使用数组表示顶点的集合，使用 链表表示边的关系。

优势

适合稀疏图(边少 | 关系简单)
适合查找一个顶点的所有关系 ——O(1)效率

框架：

具体代码：

Graph/Graph.hpp · 逆光/Cpp - 码云 - 开源中国

总结：两数据结构相辅相成，互为互补关系；

图的遍历（邻接矩阵）

给定一个图 G 和其中任意一个顶点 v0 ，从 v0 出发，沿着图中各边访问图中的所有顶点，且每个顶 点仅被遍历一次 。 " 遍历 " 即对结点进行某种操作的意思 。

1.广度优先遍历

难点：

1. 如何处理好一次存储层顶点？——采用队列保存层顶点，这里下标代表顶点。

2. 如何避免重复访问顶点？ ——采用set思想，访问顶点就标记，避免形成环。

// 层序遍历————默认从0开始层序遍历
        void BFS(const V &v)
        {
            auto index = GetIndex(v);

            queue<int> q;                
            vector<bool> _set(_vertices.size(), false);

            q.push(index);
            cout << _vertices[index] << "->";
            _set[index] = true;
            while (q.empty() != true)
            {
                int tmp = q.front();
                q.pop();
                // 获取所有连接点,并判断载入队列
                int time = 0;
                while (time < _matrix[tmp].size())
                {
                    if (_matrix[tmp][time] != INT_MAX && _set[time] == false)
                    {
                        q.push(time);
                        cout << _vertices[time] << " ";
                        _set[time] = true;
                    }
                    time++;
                }
                cout << "->";
            }
            cout << endl;
        }

2.深度优先遍历

深度优先遍历较广度，逻辑难度复杂，代码简单。在效率方面，在深度较深时，效率下降，甚至会出现栈溢出现象。

方法：递归

void _dfs(int index, vector<bool> &_set)
{
    cout << _vertices[index] << "--";
    for (int i = 0; i < _matrix[index].size(); i++)
    {
       if (_set[i] != true && _matrix[index][i] != INT_MAX)
       {
            _set[i] = true;
            _dfs(i, _set);
       }
    }
}

        void DFS(const V &v)
        {
            auto index = GetIndex(v);
            vector<bool> _set(_vertices.size(), false);
            _set[index] = true;
            _dfs(index, _set);
            cout << endl;
        }

具体代码见代码仓库：

Graph/Graph.hpp · 逆光/Cpp - 码云 - 开源中国

三，最小生成树

在连通图中，有n 个顶点，如果通过 n - 1将这n个顶点连接起来，那个形成的树就是生成树。

最小生成树的三个准则：

只能使用图中的边来构造最小生成树
只能使用恰好n-1条边来连接图中的n个顶点
选用的n-1条边不能构成回路

Kruskal算法

此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边（贪心算法），加入到最小生成树的边集合（并查集中）里。

思路解析：

把图中的所有边按权值从小到大排序（这里采用优先级队列 + 仿函数，也可以采用其他容器 + 排序）；
把图中的n个顶点看成独立的n棵树组成的森林；
按权值从小到大选择边，所选的边连接的两个顶点v1,v2。 v1与 v2 应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。
重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。

代码：

W Kruskal(Graph<V, W>& minfree)
        {
            priority_queue<edge, vector<edge>, greater<edge>> greater_queue;
            // 队列载入边信息
            for (int i = 0; i < _matrix.size(); i++)
            {
                for (int j = 0; j < _matrix[i].size(); j++)
                {
                    if (i >= j && _matrix[i][j] != INT_MAX)
                        greater_queue.push(edge(i, j, _matrix[i][j]));
                }
            }

            size_t sum_edge = 0;
            W sum_w = W();
            // 初始化并查集
            UnionFindSet it(_vertices.size());

            int time = _vertices.size() - 1;
            // 只连接 n - 1次，判断该无向图是否有最小生成树
            while (sum_edge < time)
            {
                edge tmp = greater_queue.top();
                // 防止出现闭环，原理：并查集同树
                if (it.IsSameRoot(tmp._v1, tmp._v2))
                {
                    greater_queue.pop();
                    continue;
                }
                // cout << _vertices[tmp._v1] << "->" << _vertices[tmp._v2] << ": " << tmp._w << endl;
                //单独构建一个外部最小生成树
                minfree.size_t_addedge(tmp._v1, tmp._v2, tmp._w);
                it._union(tmp._v1, tmp._v2);
                greater_queue.pop();
                sum_w += tmp._w;
                sum_edge++;
            }

            // cout << "w : " << sum_w << endl;
            // cout << "sum_edge : " << sum_edge << endl;
            // cout << "_vertice : " << _vertices.size() << endl;

            // 经过n - 1次连接边，如果所有顶点都在树中，则有最小生成树；
            // 如何判断？ 并查集，由于我们实现了压缩路径算法，所以所有孩子只有一个根。
            int root = it.GetRoot(0);
            for (int i = 1; i < it.size(); i++)
            {   
                // 如果根不相同，说明还有孤岛顶点，即不是最小生成树
                if (root != it.GetRoot(i))
                    return W();
            }
            return sum_w;
        }

具体代码 & 测试用例，见代码仓库：

Graph/Graph.hpp · 逆光/Cpp - 码云 - 开源中国

Prim算法

普里姆算法其实是在U和V-U两个阵营中不停的找一条最短的（代价最低的）可连通的边，然后将该边附着的在V-U阵营中的顶点加入U阵营中。

思路解析:

需要两个容器负责X, Y集合的快速插入 & 检测存在功能（这里我采用set<size_t>）
选择一个初始顶点加入到生成树中。
初始化一个优先队列（或最小堆），存储不在生成树中的顶点及其到当前生成树的最小边权。
从未加入生成树的顶点中选择一个与生成树相连的边权最小的顶点，加入到生成树中。
更新优先队列，反映新加入顶点带来的影响。
重复步骤 4 和 5 直到所有顶点都被加入到生成树中。直到优先级队列中没有边为止；如果记录的 边数量 == 顶点 - 1 （n - 1）则为最小生成树

下面采用另一位大佬的图解：

代码:

W Prim(Graph<V, W> &minfree, const V &start)
        {
            size_t ptr = GetIndex(start);
            set<size_t> X;
            set<size_t> Y;
            for (int i = 0; i < _vertices.size(); i++)
                Y.insert(i);

            priority_queue<edge, vector<edge>, greater<edge>> greater_queue;

            // 先载入开始顶点
            X.insert(ptr);
            Y.erase(ptr);
            // 队列载入与顶点相连边的顶点信息
            for (int i = 0; i < _matrix.size(); i++)
            {
                if (_matrix[ptr][i] != INT_MAX)
                    greater_queue.push(edge(ptr, i, _matrix[ptr][i]));
            }

            size_t edge_sum = 0;
            W w_sum = 0;

            while (greater_queue.empty() != true)
            {
                edge tmp = greater_queue.top();
                if (X.find(tmp._v1) != X.end() && X.find(tmp._v2) != X.end())
                {
                    greater_queue.pop();
                    continue;
                }
                // 不都在X中都载入
                size_t new_X;
                if (X.find(tmp._v1) == X.end())
                    new_X = tmp._v1;
                else
                    new_X = tmp._v2;
                // cout << _vertices[tmp._v1] << "->" << _vertices[tmp._v2] << ": " << tmp._w << endl;
                minfree.size_t_addedge(tmp._v1, tmp._v2, tmp._w);
                greater_queue.pop();
                w_sum += tmp._w;
                edge_sum++;
                X.insert(new_X);
                Y.erase(new_X);

                for (int i = 0; i < _matrix.size(); i++)
                {
                    if (_matrix[new_X][i] != INT_MAX)
                        greater_queue.push(edge(new_X, i, _matrix[new_X][i]));
                }
            }

            // cout << "w : " << w_sum << endl;
            // cout << "sum_edge : " << edge_sum << endl;
            // cout << "_vertice : " << _vertices.size() << endl;
            if (edge_sum != _vertices.size() - 1)
                return W();
            return w_sum;
        }

具体代码 & 测试用例，见代码仓库：

Graph/Graph.hpp · 逆光/Cpp - 码云 - 开源中国

两种算法为什么能保证得到最小生成树？

这两种算法都基于贪心策略，但在理论上已经被证明能够找到最小生成树。这是因为最小生成树问题满足贪心选择性质和最优子结构性质。也就是说，在每一步中选择当前最优解（局部最优解），最终能得到全局最优解。

前提

只要图中的边权是非负的，Kruskal 算法和 Prim 算法就能正确地找到最小生成树。如果存在负权边，那么最小生成树的概念就不再适用，因为负权边可能会导致循环，从而使得没有明确的最小生成树。

四，最短路径

最短路径问题：从在带权有向图 G 中的 某一顶点出发，找出一条通往另一顶点 的 最短路径 ，最短也就是沿路径各边的权值总和达到最小。

1.Dijkstra算法

特点：Dijkstra算法存在的问题是不支持图中带负权路径，如果带有负权路径，则可能会找不到一些路径的最短路径。

时间复杂度：O(N^2)

算法原理可以查看该作者博客，通俗易懂：

【看完必懂】Dijkstra算法（附案例详解） - 知乎

流程图：

代码：

void Dijkstra(const V &v)
        {
            vector<W> dij_vec(_vertices.size(), INT_MAX);
            vector<bool> exist(_vertices.size(), true);

            int exist_sum = _vertices.size();
            auto start_index = GetIndex(v);

            dij_vec[start_index] = 0;
            exist[start_index] = false;
            exist_sum--;

            while (exist_sum > 0)
            {
                // 在未被标记顶点内寻找
                for (int i = 0; i < _matrix[start_index].size(); i++)
                {
                    if (exist[i] && _matrix[start_index][i] != INT_MAX)
                    {
                        dij_vec[i] = min(dij_vec[i], (_matrix[start_index][i] + dij_vec[start_index]));
                    }
                        
                }
                // 开始删除目前最小值
                //获取最小值下标
                int index = -1;
                size_t min_index = INT_MAX;
                for (int i = 0; i < dij_vec.size(); i++)
                {
                    if (exist[i] && dij_vec[i] < min_index)
                    {
                        min_index = dij_vec[i];
                        index = i;
                    }
                }
                // 删除已经确定的顶点
                if (index != -1)
                {
                //    cout << "delete: " << _vertices[index] << endl;
                    exist[index] = false;
                    start_index = index;
                    exist_sum--;
                }        
            }

            cout << "结果：" << endl;
            for (int i = 0; i < dij_vec.size(); i++)
            {
                cout << _vertices[i] << " min:" << dij_vec[i] << endl;
            }
        }

全部代码，见代码仓库：

Graph/Graph.hpp · 逆光/Cpp - 码云 - 开源中国

2.Bellman-Ford算法

bellman—ford算法可以解决负权图的单源最短路径问题

特点：

适用于含有负权边的图（Dijkstra不适用）
简单粗暴，但效率慢（N^3）
如果对应路径存在负权回路则没有最短路径（可用于判断图中是否存在负权回路）

基本步骤

初始化数据：
- 对于所有顶点 dist[v] = ∞。
- dist[s] = 0，s是起始点。
松弛操作：
- 对图中的每条边(u, v)，执行松弛操作。松弛操作检查是否满足dis[u] + w < dis[v]。如果存在，则更新v的最短路径估计值。
- 这个过程重复进行V-1次（V是顶点数）。
检查负权环：
- 再次对所有的边执行松弛操作。如果能够进一步减少某个顶点的距离，正常情况不会超过V-1次，则说明存在一个从该顶点出发可以无限降低路径长度的环路，即存在一个权重之和为负的环路。

代码：

void Bellman_Ford(const V &v)
        {
            vector<W> bell_vec(_vertices.size(), INT_MAX);
            vector<size_t> last_index(_vertices.size(), -1);
            auto start_index = GetIndex(v);

            bell_vec[start_index] = 0;
            last_index[start_index] = 0;
            int n = _vertices.size();

            for (int z = 0; z < n; z++)
            {
                for (int i = 0; i < n; i++)
                {
                    for (int j = 0; j < n; j++)
                    {
                        if (_matrix[i][j] != INT_MAX && bell_vec[i] + _matrix[i][j] < bell_vec[j])
                        {
                            bell_vec[j] = bell_vec[i] + _matrix[i][j];
                            last_index[j] = i;
                        }
                    }
                }
            }

           for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (_matrix[i][j] != INT_MAX && bell_vec[i] + _matrix[i][j] < bell_vec[j])
                    {
                        return false;
                    }
                }
            }

           return true;
        }

3.floyd-warshall算法

loyd-Warshall算法是一种解决全网最短路径问题（All-Pairs Shortest Path, APSP）的动态规划算法。它可以在有向或无向图中找到任意两点之间的最短路径，即使图中包含负权重的边也可以处理。

特点

适用于密集图或当需要知道所有顶点对之间的最短路径时使用（在稀疏图非负权图上，不如多次调用dijkstra速度快）
代码简单，逻辑暴力，时间复杂度——O(n^3)
无法解决负权回路问题

以下是Floyd-Warshall算法的主要步骤：

初始化距离矩阵：
- 对于所有顶点对(i, j)，如果(i, j)直接相连，则d[i][j]设置为边的权重。
- 如果i = j，则d[i][j] = 0。
- 否则，如果不存在直接连接，则d[i][j]设置为无穷大（+∞）。
动态规划：
- 逐步考虑每一个顶点k作为中间顶点，尝试通过k来改进i到j之间的最短路径。
- 使用以下更新规则：对于每一对顶点(i, j)，如果d[i][k] + d[k][j] < d[i][j]，则更新d[i][j]为d[i][k] + d[k][j]。
- 以上更新操作对所有可能的k（从1到n，n为顶点数）进行迭代。

代码：

void Floyd_warshall()
        {
            vector<vector<W>> dis;
            vector<vector<int>> parentpath;
            int n = _vertices.size();

            dis.resize(n);
            parentpath.resize(n);
            // 初始化权值图
            // 初始化父路径图
            for (int i = 0; i < n; i++)
            {
                dis[i].resize(n, INT_MAX);
                parentpath[i].resize(n, -1);
            }

            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (_matrix[i][j] != INT_MAX)
                    {
                        dis[i][j] = _matrix[i][j];
                        // 默认i->j就是最短路径，所以j的上一级就是i
                        parentpath[i][j] = i;
                    }

                    if (i == j)
                        dis[i][j] = 0;
                }   
            }

            // 用k作为中转点，试图获取i->k->j的最短路径
            for (int k = 0; k < n; k++)
            {
                for (int i = 0; i < n; i++)
                {
                    for (int j = 0; j < n; j++)
                    {
                        if (dis[i][k] != INT_MAX && dis[k][j] != INT_MAX && dis[i][k] + dis[k][j] < dis[i][j])
                        {
                            dis[i][j] = dis[i][k] + dis[k][j];
                            parentpath[i][j] = parentpath[k][j];
                        }
                    }
                }
            }

        }