数据结构之图的应用（1）——最小生成树_图的操作及应用,最小生成树的数据结构代码
赞
踩
在学完图的存储结构和两种遍历后，相信大家对于图也有了自己的理解了吧，下面我们继续来讲讲图的应用方面吧，应用方面其实有很多很多，但课本好像只列举四种——最小生成树，最短路径，拓扑排序和关键路径。下面我们就一一来分享给大家吧。今天这期文章主要分享一下最小生成树。
生成树：是由n个顶点，n-1条边，将一个连通图连接起来，不形成回路
可以分为深度优先生成树和广度优先生成树。
概念：最小生成树（minimum spanning tree）是由n个顶点，n-1条边，将一个连通图连接起来，不形成回路，且使权值最小的结构。
最小生成树的构造：先拓展一下。
我们主要学的最小生成树的算法是Prim（普里姆）算法或kruskal（克鲁斯卡尔）算法。此外还可以用bfs和dfs生成，分别叫bfs生成树和dfs生成树。
1. Prim（普里姆）算法
核心思路：与前面的MST性质有关哦 
首先就是从图中的一个起点a开始，把a加入U集合，然后，寻找从与a有关联的边中，权重最小的那条边并且该边的终点b在顶点集合：（V-U）中，我们也把b加入到集合U中，并且输出边（a，b）的信息，这样我们的集合U就有：{a,b}，然后，我们寻找与a关联和b关联的边中，权重最小的那条边并且该边的终点在集合：（V-U）中，我们把c加入到集合U中，并且输出对应的那条边的信息，这样我们的集合U就有：{a,b,c}这三个元素了，一次类推，直到所有顶点都加入到了集合U。
最后，我们发现六个点都已经加入到集合U了，我们的最小生成树建立完成。
普里姆算法的实现：
代码（这段代码也是借鉴某位大佬写的，特地感谢）：
#include<iostream>
#include<string>
#include<vector>
using namespace std;
//首先是使用邻接矩阵完成Prim算法
struct Graph {
int vexnum; //顶点个数
int edge; //边的条数
int** arc; //邻接矩阵
string* information; //记录每个顶点名称
};
//创建图
void createGraph(Graph& g) {
cout << "请输入顶点数：输入边的条数" << endl;
cin >> g.vexnum;
cin >> g.edge; //输入边的条数
g.information = new string[g.vexnum];
g.arc = new int* [g.vexnum];
int i = 0;
//开辟空间的同时，进行名称的初始化
for (i = 0; i < g.vexnum; i++)
{
g.arc[i] = new int[g.vexnum];
g.information[i] = "v" + std::to_string(i + 1);//对每个顶点进行命名
for (int k = 0; k < g.vexnum; k++)
{
g.arc[i][k] = INT_MAX; //初始化我们的邻接矩阵
}
}
cout << "请输入每条边之间的顶点编号(顶点编号从1开始),以及该边的权重：" << endl;
for (i = 0; i < g.edge; i++) {
int start;
int end;
cin >> start; //输入每条边的起点
cin >> end; //输入每条边的终点
int weight;
cin >> weight;
g.arc[start - 1][end - 1] = weight;//无向图的边是相反的
g.arc[end - 1][start - 1] = weight;
}
}
//打印图
void print(Graph g)
{
int i;
for (i = 0; i < g.vexnum; i++) {
//cout << g.information[i] << " ";
for (int j = 0; j < g.vexnum; j++)
{
if (g.arc[i][j] == INT_MAX)
cout << "∞" << " ";
else
cout << g.arc[i][j] << " ";
}
cout << endl;
}
}
//作为记录边的信息，这些边都是达到end的所有边中，权重最小的那个
struct Assis_array {
int start; //边的终点
int end; //边的起点
int weight; //边的权重
};
//进行prim算法实现，使用的邻接矩阵的方法实现。
void Prim(Graph g, int begin) {
//close_edge这个数组记录到达某个顶点的各个边中的权重最大的那个边
Assis_array* close_edge = new Assis_array[g.vexnum];
int j;
//进行close_edge的初始化，更加开始起点进行初始化
for (j = 0; j < g.vexnum; j++)
{
if (j != begin - 1)
{
close_edge[j].start = begin - 1;
close_edge[j].end = j;
close_edge[j].weight = g.arc[begin - 1][j];
}
}
//把起点的close_edge中的值设置为-1，代表已经加入到集合U了
close_edge[begin - 1].weight = -1;
//访问剩下的顶点，并加入依次加入到集合U
for (j = 1; j < g.vexnum; j++)
{
int min = INT_MAX;
int k;
int index;
//寻找数组close_edge中权重最小的那个边
for (k = 0; k < g.vexnum; k++)
{
if (close_edge[k].weight != -1)
{
if (close_edge[k].weight < min)
{
min = close_edge[k].weight;
index = k;
}
}
}
//将权重最小的那条边的终点也加入到集合U
close_edge[index].weight = -1;
//输出对应的边的信息
cout << g.information[close_edge[index].start]
<< "-----"
<< g.information[close_edge[index].end]
<< "="
<< g.arc[close_edge[index].start][close_edge[index].end]
<< endl;
//更新我们的close_edge数组。
for (k = 0; k < g.vexnum; k++) {
if (g.arc[close_edge[index].end][k] < close_edge[k].weight) {
close_edge[k].weight = g.arc[close_edge[index].end][k];
close_edge[k].start = close_edge[index].end;
close_edge[k].end = k;
}
}
}
}
int main()
{
Graph g;
createGraph(g);//基本都是无向网图，所以我们只实现了无向网图
print(g);
Prim(g, 1);
system("pause");
return 0;
}
程序执行图：
2.kruskal（克鲁斯卡尔）算法：
基本思想 ：按照权值从小到大的顺序选择 n-1 条边，并保证这 n-1 条边不构成回路
具体做法 ：首先构造一个只含 n 个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。
但这种情况下构造出来的最小生成树不是唯一的，因为有些支路权值是一样的。
kruskal（克鲁斯卡尔）算法：
#include <stdio.h>
#define MAXE 100
#define MAXV 100
typedef struct
{
int vex1; //边的起始顶点
int vex2; //边的终止顶点
int weight; //边的权值
}Edge;
void kruskal(Edge E[], int n, int e)
{
int i, j, m1, m2, sn1, sn2, k, sum = 0;
int vset[n + 1];
for (i = 1; i <= n; i++) //初始化辅助数组
vset[i] = i;
k = 1;//表示当前构造最小生成树的第k条边，初值为1
j = 0;//E中边的下标，初值为0
while (k < e)//生成的边数小于e时继续循环
{
m1 = E[j].vex1;
m2 = E[j].vex2;//取一条边的两个邻接点
sn1 = vset[m1];
sn2 = vset[m2];
//分别得到两个顶点所属的集合编号
if (sn1 != sn2)//两顶点分属于不同的集合，该边是最小生成树的一条边
{//防止出现闭合回路
printf("V%d-V%d=%d\n", m1, m2, E[j].weight);
sum += E[j].weight;
k++; //生成边数增加
if (k >= n)//没有边或者找到的边>顶点数减1都退出循环
break;
for (i = 1; i <= n; i++) //两个集合统一编号
if (vset[i] == sn2) //集合编号为sn2的改为sn1
vset[i] = sn1;
}
j++; //无论上一条边是否被收入最下生成树，都要扫描下一条边
//k++与j++的位置不同，k++在循环内部(只有满足条件才能被收入最小生成树)，j++在循环外部
}
printf("the lowest weight=%d\n", sum);
}
void swap(Edge arr[], int low, int high)
{
Edge temp;
temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;
}
int fun(Edge arr[], int low, int high)
{
int key;
Edge lowx;
lowx = arr[low];
key = arr[low].weight;
while (low < high)
{
while (low < high && arr[high].weight >= key)
high--;
if (low < high)
swap(arr, low, high);
//arr[low++]=arr[high];
while (low < high && arr[low].weight <= key)
low++;
if (low < high)
swap(arr, low, high);
//arr[high--]=arr[low];
}
arr[low] = lowx;
return low;
}
void quick_sort(Edge arr[], int start, int end)
{
int pos;
if (start < end)
{
pos = fun(arr, start, end);
quick_sort(arr, start, pos - 1);
quick_sort(arr, pos + 1, end);
}
}
void gen(Edge E[], int vertex, int edge)
{
for (int i = 0; i < edge; i++)
scanf_s("%d%d%d", &E[i].vex1, &E[i].vex2, &E[i].weight);
}
int main()
{
Edge E[MAXE];
int vertex, edge;
//freopen("1.txt","r",stdin);//文件输入
printf("please intput the vertexs and edges:\n");
scanf_s("%d%d", &vertex, &edge);
gen(E, vertex, edge);
quick_sort(E, 0, edge - 1);
kruskal(E, vertex, edge);
}
两种算法比较：
好啦，关于这两种算法的介绍就到这啦，其实这两种算法都有各自的优缺点，理解起来其实不算难，代码可能难看懂一些。以后的日常应用中要根据实际情况来选择用哪种算法合适吧。
本贴为博主亲手整理。如有错误，请评论区指出，一起进步。谢谢大家的浏览.
