Kruskal算法生成最小生成树
a 问题分析
我们需要使用 Kruskal 算法找到一个包含10个节点和20条边的图的最小生成树。Kruskal算法基于贪心思想，通过不断选择权重最小的边，并确保添加这条边不形成环路，来构建最小生成树。
b 算法设计
Kruskal 算法的关键步骤：
边的排序：
将所有边按照权重升序排序。
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.weight < b.weight;
});sort 函数通过指定排序的范围和比较规则，对容器中的元素进行排序。在这里，它被用于按照边的权重升序排序，以便在Kruskal算法中逐步选择最小权重的边。
edges.begin()和edges.end(): 这两个参数指定了排序的范围，即待排序元素的起始和终止位置。在这里，edges是一个存储边的集合的容器，begin()返回容器的起始迭代器，end()返回容器的终止迭代器。[](const Edge& a, const Edge& b) { return a.weight < b.weight; }: 这是一个 lambda 表达式，它定义了排序的比较规则。lambda 表达式是一个匿名函数，用于在排序过程中比较两个元素的大小。在这里，比较规则是按照边的权重 (weight) 升序排列。const Edge& a和const Edge& b是 lambda 表达式的参数，表示两个待比较的边。return a.weight < b.weight;表示如果边a的权重小于边b的权重，则返回true，否则返回false。这样，sort函数会按照升序的方式对边进行排序。
并查集初始化：
初始化并查集，每个节点单独成为一个集合。
- 并查集（Disjoint Set Union，简称并查集）是一种用于处理集合的数据结构，主要支持两种操作：查找（Find）和合并（Union）。这种数据结构用于解决一些与集合划分相关的问题，特别是在图论和网络连接等领域。
- 基本操作:
- 查找 (Find): 查找元素所属的集合，通常通过找到根节点来确定一个元素所在的集合。这个过程可以帮助判断两个元素是否属于同一集合。
- 合并 (Union): 将两个集合合并为一个新的集合。这个操作通常会将两个集合的根节点连接在一起，以确保它们成为同一个集合。
- 实现细节:
- 通常，可以使用数组来实现并查集。数组的每个元素代表一个集合中的一个元素，数组中的值表示该元素的父节点（或根节点）。初始时，每个元素都是其自己的根节点。
- 为了优化并查集的性能，通常会使用路径压缩和按秩合并这两种技术：
- 路径压缩 (Path Compression): 在进行查找操作时，将查找路径上的所有节点的父节点都直接设为根节点，从而降低树的高度，提高后续查找的效率。
- 按秩合并 (Union by Rank): 在进行合并操作时，将较矮的树合并到较高的树上，从而避免树的过度增长，提高效率。"秩"通常指树的高度或者节点的深度。
边的遍历：
遍历排序后的边，逐步选择边并加入最小生成树，确保不形成环路。
具体实现：
// Kruskal算法
vector<Edge> kruskal(vector<Edge>& edges, int numNodes) {//传入边集、节点数
// 将边按权重升序排序
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b)
//传入开始比较边、终止比较边、lambda表达式（两比较元素）
{
return a.weight < b.weight;//定义比较规则：边权重大小升序排序
});
// 初始化并查集
UnionFind uf(numNodes);//UnionFind(size)
// 存储最小生成树的边
vector<Edge> result;
// 遍历排序后的边
for (const Edge& edge : edges) {
// 检查加入这条边是否会形成环路
if (uf.find(edge.start) != uf.find(edge.end)) {//这条边开始节点与终止节点不在同一集合（子树）
// 不会形成环路，加入最小生成树
result.push_back(edge);
uf.unite(edge.start, edge.end);//将两节点所在子树合并（标记为同一集合）防止形成环路
}
}
return result;
}c 数据结构设计
1. Edge 结构体：
// 边的结构体
struct Edge {
int start, end, weight;//边的开始节点、终止节点、权重
};Edge结构体表示图中的一条边，包含起点、终点和权重。
2. UnionFind 类：
// 并查集的实现
class UnionFind {
public:
UnionFind(int size) : parent(size), rank(size, 0) {
//parent存储各节点的根节点，初始为自身；rank记录各节点作为根节点时树的深度，初始为0
for (int i = 0; i < size; ++i) {
parent[i] = i;//根节点初始化为自身
}
}
int find(int x) {//查找根节点
if (x != parent[x]) {//x的根节点不为自身（存在双亲节点）
parent[x] = find(parent[x]);//将根节点设置为双亲节点的根节点
}
return parent[x];//返回双亲节点/上一级节点
}
void unite(int x, int y) {//合并两子树
int rootX = find(x);//x节点的根节点
int rootY = find(y);//y节点的根节点
if (rootX != rootY) {//x、y不在同一集合（子树）
if (rank[rootX] < rank[rootY]) {
//x所在子树深度小于y所在子树深度
parent[rootX] = rootY;
//将x子树并入y子树以保证合并后深度不增大
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {//x、y所在子树深度相同
parent[rootX] = rootY;//x子树并入y子树
rank[rootY]++;//合并后深度++
}
}
}
private:
vector<int> parent;
vector<int> rank;
};UnionFind类实现了并查集，用于查找节点所在的集合和合并两个集合。find函数用于查找根节点，unite函数用于合并两个集合。- 在构造函数中，
rank数组的初始值都被设置为0。在这里，rank数组的值不是表示节点的深度，而是近似表示树的高度。每个节点初始化时都被认为是一棵只包含自己的树，所以初始高度是0。 - 在
rank数组中，每个元素的值表示树的近似高度。在进行合并操作时，通过比较两棵树的高度，选择将较矮的树连接到较高的树上，以保持树的平衡。这有助于避免树的高度过度增长，维护了并查集的高效性。
d 调试过程
在调试过程中，我们可以逐步运行代码，观察每个步骤的输出，特别是排序后的边、最小生成树的构建过程，以及并查集的状态。通过输出中间结果，可以验证算法是否按预期工作。
e 输出结果
Graph:
0 - 1 : 4
0 - 2 : 1
1 - 3 : 2
1 - 4 : 8
2 - 5 : 3
2 - 6 : 7
3 - 7 : 5
3 - 8 : 1
4 - 9 : 6
5 - 6 : 2
6 - 8 : 6
7 - 9 : 3
8 - 9 : 9
1 - 2 : 2
3 - 4 : 3
5 - 7 : 4
6 - 9 : 7
0 - 3 : 6
2 - 8 : 5
4 - 5 : 4
Edges in the minimum spanning tree:
0 - 2 : 1
3 - 8 : 1
1 - 3 : 2
1 - 2 : 2
5 - 6 : 2
2 - 5 : 3
3 - 4 : 3
7 - 9 : 3
5 - 7 : 4f 源代码
#include <iostream>
#include <vector>
#include <algorithm>//调用sort函数
using namespace std;
// 边的结构体
struct Edge {
int start, end, weight;//边的开始节点、终止节点、权重
};
// 并查集的实现
class UnionFind {
public:
UnionFind(int size) : parent(size), rank(size, 0) {
//parent存储各节点的根节点，初始为自身；rank记录各节点作为根节点时树的深度，初始为0
for (int i = 0; i < size; ++i) {
parent[i] = i;//根节点初始化为自身
}
}
int find(int x) {//查找根节点
if (x != parent[x]) {//x的根节点不为自身（存在双亲节点）
parent[x] = find(parent[x]);//将根节点设置为双亲节点的根节点
}
return parent[x];//返回双亲节点/上一级节点
}
void unite(int x, int y) {//合并两子树
int rootX = find(x);//x节点的根节点
int rootY = find(y);//y节点的根节点
if (rootX != rootY) {//x、y不在同一集合（子树）
if (rank[rootX] < rank[rootY]) {
//x所在子树深度小于y所在子树深度
parent[rootX] = rootY;
//将x子树并入y子树以保证合并后深度不增大
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {//x、y所在子树深度相同
parent[rootX] = rootY;//x子树并入y子树
rank[rootY]++;//合并后深度++
}
}
}
private:
vector<int> parent;
vector<int> rank;
};
// Kruskal算法
vector<Edge> kruskal(vector<Edge>& edges, int numNodes) {//传入边集、节点数
// 将边按权重升序排序
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b)
//传入开始比较边、终止比较边、lambda表达式（两比较元素）
{
return a.weight < b.weight;//定义比较规则：边权重大小升序排序
});
// 初始化并查集
UnionFind uf(numNodes);//UnionFind(size)
// 存储最小生成树的边
vector<Edge> result;
// 遍历排序后的边
for (const Edge& edge : edges) {
// 检查加入这条边是否会形成环路
if (uf.find(edge.start) != uf.find(edge.end)) {//这条边开始节点与终止节点不在同一集合（子树）
// 不会形成环路，加入最小生成树
result.push_back(edge);
uf.unite(edge.start, edge.end);//将两节点所在子树合并（标记为同一集合）防止形成环路
}
}
return result;
}
int main() {
// 创建一个10节点的图
int numNodes = 10;
// 创建边集合，手动设置边的起点、终点和权重
vector<Edge> edges = {
{0, 1, 4},
{0, 2, 1},
{1, 3, 2},
{1, 4, 8},
{2, 5, 3},
{2, 6, 7},
{3, 7, 5},
{3, 8, 1},
{4, 9, 6},
{5, 6, 2},
{6, 8, 6},
{7, 9, 3},
{8, 9, 9},
{1, 2, 2},
{3, 4, 3},
{5, 7, 4},
{6, 9, 7},
{0, 3, 6},
{2, 8, 5},
{4, 5, 4}
};
//输出该图
cout << "Graph:" << endl;
for (const Edge& edge : edges) {
cout << edge.start << " - " << edge.end << " : " << edge.weight << endl;
}
// 运行Kruskal算法
vector<Edge> minSpanningTree = kruskal(edges, numNodes);
// 输出最小生成树的边
cout << "Edges in the minimum spanning tree:" << endl;
for (const Edge& edge : minSpanningTree) {
cout << edge.start << " - " << edge.end << " : " << edge.weight << endl;
}
return 0;
}Dijkstra算法解决带权图最短路径问题
a 问题分析
代码实现了 Dijkstra 算法，用于解决带权图中的单源最短路径问题。通过给定的邻接矩阵表示图，从指定的起始节点出发，计算该起始节点到图中所有其他节点的最短距离。
b 算法设计
1. 初始化
int n = graph.size();
distances.resize(n, INF);- 分析： 获取图的节点数
n，然后初始化距离数组distances，将所有节点的距离初始值设为无穷大（INF）。
2. 构建优先队列
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
distances[start] = 0;
pq.push({0, start});- 分析： 创建一个优先队列
pq，元素为节点和其距离的pair对。将起始节点的距离设置为0，并将该节点放入优先队列。
3. 循环迭代
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
for (int v = 0; v < n; ++v) {
if (graph[u][v] != 0 && distances[v] > distances[u] + graph[u][v]) {
distances[v] = distances[u] + graph[u][v];
pq.push({distances[v], v});
}
}
}- 分析： 不断从优先队列中取出当前距离起点最小的节点
u，然后遍历节点u的邻居。如果通过节点u到达邻居节点v的距离比已知的距离短，更新距离值并将新距离和节点v加入队列。
4. 重复
- 分析： 重复步骤3，直到优先队列为空。在每一步中，队列中的节点都是当前距离起点最小的，确保了每次都选择了当前已知最短路径的节点进行扩展。
c 数据结构设计
1. Graph（图的邻接矩阵表示）
typedef vector<vector<int>> Graph;- 分析：
Graph是一个二维向量，表示图的邻接矩阵。其中graph[u][v]表示从节点u到节点v的边的权重。0 表示没有直接连接。
2. distances（存储节点到起始节点的最短距离）
vector<int> distances;- 分析：
distances是一个一维向量，用于存储每个节点到起始节点的最短距离。初始值为无穷大，后续会在 Dijkstra 算法的执行过程中被更新。
3. pq（优先队列）
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;-
分析：
pq是一个优先队列，用于按照节点的距离从小到大排序。每个队列元素是一个pair<int, int>，表示节点和其距离。通过greater<pair<int, int>>指定比较规则，确保队首元素是最小的。d 调试过程
-
在
dijkstra函数中，使用cout输出中间结果，确保每一步计算都符合预期。 -
考虑边界情况，如图中有没有边、负权边等，以确保算法的鲁棒性。
-
通过多个测试用例验证算法的正确性和效率。
e 输出结果
最终输出各节点到起始节点的最短距离，结果符合预期，表明算法成功计算出了最短路径。
Distance from node 0 to 0: 0
Distance from node 0 to 1: 2
Distance from node 0 to 2: 3
Distance from node 0 to 3: 9
Distance from node 0 to 4: 6f 源代码
#include <iostream>
#include <vector>
#include <queue>//引入优先队列
#include <climits>//引入int型最大值
using namespace std;
#define INF INT_MAX
// 定义图的邻接矩阵表示法
typedef vector<vector<int>> Graph;
//二维向量表示两节点间边的权重，graph[u][v]
// Dijkstra算法实现
void dijkstra(const Graph& graph, int start, vector<int>& distances) {
//传入图、起始节点，起始节点到各节点距离数组
int n = graph.size();//n为节点数
distances.resize(n, INF); // 初始化距离数组，初始值为无穷大
// 优先队列，按距离从小到大排列
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
//pair为其他节点，和该节点到起始节点的距离，构成的对{distance,v}
//优先队列的元素类型为pair，底层容器类型为vector
//定义比较器greater，比较规则为pair，队列顶端将是距离最短的节点pair
distances[start] = 0; // 起始节点到自身的距离为0
pq.push({0, start}); // 将起始节点加入队列，距离为0
while (!pq.empty()) {
int u = pq.top().second; // 取出当前距离起点最小的节点，定为出发点u
pq.pop();
for (int v = 0; v < n; v++) {
if (graph[u][v] != 0 && distances[v] > distances[u] + graph[u][v]) {
// 如果通过当前节点u到节点v的距离比已知的距离短，更新距离值
distances[v] = distances[u] + graph[u][v];
pq.push({distances[v], v}); // 将新距离和节点v加入队列
}
}
}
}
int main() {
// 示例图的邻接矩阵表示
Graph graph = {
{0, 2, 4, 0, 0},
{0, 0, 1, 7, 0},
{0, 0, 0, 0, 3},
{0, 0, 0, 0, 1},
{0, 0, 0, 0, 0}
};
int startNode = 0;
vector<int> distances;
dijkstra(graph, startNode, distances);
// 输出各节点到起始节点的最短距离
for (int i = 0; i < distances.size(); ++i) {
cout << "Distance from node " << startNode << " to " << i << ": ";
if (distances[i] == INF) {
cout << "INF" << endl;
} else {
cout << distances[i] << endl;
}
}
return 0;
}