目录
Prim算法求最小生成树
【算法思想】
【算法实现】
【数据结构设计】
【算法步骤】
【输入输出】
【代码示例】
Kruskal算法求最小生成树
【算法思想】
判断是否会产生回路的方法
【算法描述】
【图的存储结构】
【输入输出】
【代码示例】
Prim算法求最小生成树
【算法思想】
普里姆算法在找最小生成树时，将顶点分为两类，一类是在查找的过程中已经包含在树中的（设为 已选集合），剩下的是另一类（设为 待选集合）。
对于给定的连通网，起始状态全部顶点都归为 待选集合。在找最小生成树时，选定任意一个顶点作为起始点，并将之从 待选集合移至已选集合；然后找出 待选集合中到已选集合中的顶点之间权值最小的顶点，将之从 待选集合移至已选集合，如此重复，直到 待选集合中没有顶点为止。
所走过的顶点和边就是该连通图的最小生成树。
【算法实现】
输入：网（带权值的图）
输出：依次访问各个顶点 创建一个辅助数组，每次将当前已选类顶点到待选类顶点的距离填写到数组中。然后从中筛选出权值最小的边的邻接点。
在辅助数组中找出权值最小的边的数组下标，就可以间接找到此边的终点顶点。找到后lowcost标记为0。
【数据结构设计】
- 图的存储结构：由于在算法执行过程中，需要不断读取任意两个顶点之间边的权值，所以，图采用邻接矩阵存储。
- 候选最短边集：设置数组shortEdge[n]表示候选最短边集，数组元素包括adjvex和lowcost两个域，分别表示候选最短边的邻接点和权值。
【算法步骤】
- 初始化两个辅助数组lowcost和adjvex；
- 输出顶点u0，将顶点u0加入集合U中；
- 重复执行下列操作n-1次 3.1 在lowcost中选取最短边，取adjvex中对应的顶点序号k； 3.2 输出顶点k和对应的权值； 3.3 将顶点k加入集合U中； 3.4 调整数组lowcost和adjvex；
【输入输出】
第一行输入顶点的个数n
第二行输入n个顶点的值
第三行输入边的条数m
下面m行依次输入边的起点的值，终点的值和权值。
输出最小生成树，每行输出它的一条边。
【测试数据】
输入：
请输入顶点的个数：6
请依次输入6个顶点的值：
A B C D E F
请输入边的个数：9
请依次输入9个边的起点、终点和权值：
A C 46
A F 19
A B 34
B E 12
E F 26
D E 38
D F 25
C D 17
C F 25
输出：
最小生成树是：
(AF)19
(FC)25
(CD)17
(FE)26
(EB)12
【代码示例】
#include <iostream>
#include <limits.h>
#include <string> // 包含string以便处理顶点的字符表示
#define MAX_V_NUM 20
using namespace std;
struct closedge
{
char adjvex; // 邻接点的字符表示
int lowcost; // 到邻接点的最小权值
};
closedge shortEdge[MAX_V_NUM]; // 存储候选最短边集
class MGraph
{
private:
char vertex[MAX_V_NUM]; // 图的顶点数组
int arc[MAX_V_NUM][MAX_V_NUM]; // 图的邻接矩阵
int vexNum, arcNum; // 顶点数和边数
public:
MGraph(); // 构造函数
void Prim(int start); // 实现Prim算法
};
MGraph::MGraph()
{
cout << "请输入顶点的个数：";
cin >> vexNum;
cout << "请依次输入" << vexNum << "个顶点的值：" << endl;
for (int i = 0; i < vexNum; i++)
{
cin >> vertex[i];
}
cout << "请输入边的个数：";
cin >> arcNum;
char vi, vj;
int w;
// 初始化邻接矩阵
for (int i = 0; i < vexNum; i++)
{
for (int j = 0; j < vexNum; j++)
{
if(i==j)
{
arc[i][j] =0;
}
else
{
arc[i][j]=INT_MAX;
}
}
}
cout << "请依次输入" << arcNum << "个边的起点、终点和权值：" << endl;
for (int i = 0; i < arcNum; i++)
{
cin >> vi >> vj >> w;
arc[vi - 'A'][vj - 'A'] = w;
arc[vj - 'A'][vi - 'A'] = w; // 因为是无向图
}
// 假设从顶点0开始Prim算法
Prim(0);
}
void MGraph::Prim(int start)
{
// 初始化shortEdge数组
for (int i = 0; i < vexNum; i++)
{
shortEdge[i].lowcost = arc[start][i];
shortEdge[i].adjvex = start;
}
shortEdge[start].lowcost = 0;
cout << "最小生成树是：" << endl;
for (int i = 0; i < vexNum - 1; i++)
{
int k = 0;
for (int j = 0; j < vexNum; j++)
{
if(shortEdge[j].lowcost!=0&&shortEdge[j].lowcost!=INT_MAX){
k=j;
break;
}
}
for (int j = 0; j < vexNum; j++){
if (shortEdge[j].lowcost!=0&&shortEdge[k].lowcost>shortEdge[j].lowcost)
{
k =j;
break;
}
}
// 输出最小边
cout << "(" << vertex[shortEdge[k].adjvex] << vertex[k] << ")" << shortEdge[k].lowcost << endl;
// 将找到的最小边标记为0，表示已访问
shortEdge[k].lowcost = 0;
for (int j = 0; j < vexNum; j++)
{
if (arc[k][j]!=0&&arc[k][j] < shortEdge[j].lowcost)
{
shortEdge[j].lowcost = arc[k][j];
shortEdge[j].adjvex = k;
}
}
}
}
int main()
{
MGraph graph;
return 0;
}
Kruskal算法求最小生成树
【算法思想】
将所有边按照权值的大小进行升序排序，然后从小到大一一判断，条件为：如果这个边不会与之前选择的所有边组成回路，就可以作为最小生成树的一部分；反之，舍去。直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。筛选出来的边和所有的顶点构成此连通网的最小生成树。
注意：排序时如果两条边权值相同，起点下标较小边排在前面，保证测试数据的准确。
判断是否会产生回路的方法
1、标记法：在初始状态下给每个顶点赋予不同的标记，对于遍历过程的每条边，其都有两个顶点，判断这两个顶点的标记是否一致，如果一致，说明它们本身就处在一棵树中，如果继续连接就会产生回路；如果不一致，说明它们之间还没有任何关系，可以连接。 假设遍历到一条由顶点 A 和 B 构成的边，而顶点 A 和顶点 B 标记不同，此时不仅需要将顶点 A 的标记更新为顶点 B 的标记，还需要更改所有和顶点 A 标记相同的顶点的标记，全部改为顶点 B 的标记。
2、初始时每个顶点构成一棵生成树，然后每生长一次就将两棵树合并，到最后合并成一棵树。判断两个顶点是否在同一课树中，如果在同一棵树则产生了回路。
判断顶点是否在同一棵树中，可以从顶点出发，寻找树的根结点。如果两个顶点的根结点相同，则属于同一棵树。
【算法描述】
设无向连通网为G＝(V, E)，令G的最小生成树为T＝(U, TE)，其初态为U＝V，TE＝{ }，然后，按照边的权值由小到大的顺序，考察G的边集E中的各条边。
若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。
【图的存储结构】
因为Kruskal算法是依次对图中的边进行操作，因此考虑用边集数组存储图中的边，为了提高查找速度，将边集数组按边上的权排序。
struct EdgeType
{
int from,to; //边依附的两个顶点
int weight; //边上的权值
};
【输入输出】
请输入图的顶点数和边数：
6 9请输入顶点的值：
0 1 2 3 4 5请输入边的起点终点和权值：
1 4 12
2 3 17
0 5 19
2 5 25
3 5 25
4 5 26
0 1 34
3 4 38
0 2 46用Kruskal算法生成最小生成树的生成次序为：
(1,4)12
(2,3)17
(0,5)19
(2,5)25
(4,5)26
【代码示例】
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 10000;
template <class T>
struct EdgeType
{
T from, to; //边依附的两个顶点
int weight; //边上的权值
};
template <class T>
class EdgeGraph
{
private:
char* vertex; //存放图顶点的数组
EdgeType<char>* edge; //存放边的数组
int vertexNum, edgeNum; //图的顶点数和边数
public:
EdgeGraph(int vNum, int eNum);//构造函数
void inputGraph();//输入图
void Kruskal();
int getIndex(char v)
{
for (int i = 0; i < vertexNum; i++) {
if (vertex[i] == v) {
return i;
}
}
return -1; // 如果找不到顶点，返回-1
}
void sorts();
private:
T findRoot(int parent[], T v);//找到树的根
};
template <class T>
EdgeGraph<T>::EdgeGraph(int vNum, int eNum)
{
vertexNum = vNum;
edgeNum = eNum;
vertex = new char[vertexNum];
edge = new EdgeType<T>[edgeNum];
char v;
T f, t;
int w;
cout << "请输入顶点的值：";
for (int i = 0; i < vertexNum; i++)
{
cin >> v;
vertex[i] = v;
}
cout << "请输入边的起点终点和权值：\n";
for (int i = 0; i < edgeNum; i++)
{
cin >> f >> t >> w;
edge[i].from = f;
edge[i].to = t;
edge[i].weight = w;
}
sorts();
}
//对weight排序
// 最开始写的冒泡排序，但是有问题
// 冒泡排序不是对边的数组edge中的元素进行排序，而是对数组的索引进行排序。这意味着数组edge中的元素并没有按照权值从小到大进行排序，而是数组的索引被重新排列，使得具有较小权值的边的索引在前。这并不是Kruskal算法所需要的。
// 需要对边的数组edge中的EdgeType对象按照权值进行排序，而不是对索引进行排序。
// 修正后，使用了C++11的lambda表达式来定义排序准则，即按照weight成员进行比较。这样，edge数组中的EdgeType对象将根据它们的权值进行排序，而不是它们的索引。
template <class T>
void EdgeGraph<T>::sorts()
{
// 使用标准库的sort函数对边按照权值进行排序
sort(edge, edge + edgeNum, [](const EdgeType<T>& a, const EdgeType<T>& b) {
return a.weight < b.weight;
});
}
template <class T>
void EdgeGraph<T>::Kruskal()
{
int parent[MAX] = { 0 };
T vex1, vex2;
sorts();
for (int i = 0; i < vertexNum; i++)
{
parent[i] = -1;
}
for (int num = 0, i = 0; i < edgeNum; i++)
{
//找到所在生成树的根节点
int idx1 = getIndex(edge[i].from);
int idx2 = getIndex(edge[i].to);
vex1 = findRoot(parent, idx1);
vex2 = findRoot(parent, idx2);
if (vex1 != vex2) //如果两个根节点不同，不会构成环
{
cout << "(" << edge[i].from << "," << edge[i].to << ")" << edge[i].weight << endl;
parent[vex2] = vex1;//合并生成树
num++;
if (num == vertexNum - 1) //循环了顶点数-1次，提前返回
return;
}
}
}
//求根节点
template <class T>
T EdgeGraph<T>::findRoot(int parent[], T v)
{
T t = v;
while (parent[t] > -1)
{
t = parent[t];
}
return t;
}
int main()
{
int vNum, eNum;
cout << "请输入图的顶点数和边数：";
cin >> vNum >> eNum;
EdgeGraph<char> edgegraph(vNum, eNum);
cout << "用Kruskal算法生成最小生成树的生成次序为：\n";
edgegraph.Kruskal();
return 0;
}
