JiaPang's Blog

最小生成树算法

2023/03/01 数据结构与算法 共 5791 字，约 17 分钟

上机实践报告

一、目的

1．熟悉算法设计的基本思想

2．巩固并查集，熟悉最小生成树算法

二、内容与设计思想

  1. 解决OJ上的练习题“水”、“交通”，题目描述如下所述。

  2. 简单描述代码的思路。

*注0：练习题“交通”请用两种算法（ Prim 和 Kruskal ）实现，“水”题只需要选一个更快的实现。

*注1：练习题都只有正确性测试点，不用基于数据做折线图（自己有想法可以自己设计），请至少列出不同实现的代码的时间 。

*注2：可以自己设计测试方式和数据进行比较。

*注3：可以自己额外找编程问题来进行比较。

交通 Description

某市调查城镇交通状况，得到现有城镇道路统计表，表中列出了连接两个城镇需要花费的代价。

目标是使全市任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。

问最少花费多少代价就可以完成工程。

水 Description

夏华献希望把水引入 $N (1 <= N <= 300)$ 个农场，农场的编号是 $1～N$ 。

他将水引入某个农场的方法有两个：

  • 花钱农场中打一口井
  • 花钱建管道连到有水的农场

在农场 $i$ 中打井的费用是 $W_i (1 <= W_i <= 100000)$ 。

把农场 $i$ 和 $j$ 用一根管道相连的费用是 $P_{ij} (1 <= P_{ij} <= 100000, P_{ij} = P_{ji}, P_{ii} = 0)$ 。

请你求出夏华献最少要花多少钱才能够让他的所有农场都有水。

三、使用环境

推荐使用C/C++集成编译环境。

练习地址：**[oj《算法设计与分析》第八次实验课](http://47.100.233.213/contest/98/problems)**（密码40088860）

截止时间：2021年12月05日 23:30

提交地址：算法设计与分析-实践报告8 (jianguoyun.com)

不建议随意改变本文档以上部分的结构，以下部分可以按需扩充。但不要缺少“实验过程”和“总结”。

四、实验过程

交通

交通——prime算法实现

#include <bits/stdc++.h>
using namespace std;

#define MAX 1000
#define MAXCOST 0x7fffffff

int graph[MAX][MAX];

//n为所有顶点个数
int prim(int graph[][MAX], int n)
{
	int lowcost[MAX];
	int pre[MAX]; //pre是用来记录这个点的前驱是哪一个
	int i, j, min, min_next, sum = 0;
	//以第一个结点为开始
	for (i = 2; i <= n; i++)
	{
		lowcost[i] = graph[1][i];
		pre[i] = 1; //这些点的前一个都是第一个点
	}
	pre[1] = 0;
	for (i = 2; i <= n; i++) //需要找n-1条边
	{
		min = MAXCOST;
		min_next = 0;
		for (j = 2; j <= n; j++) //找到要加入的下一个点
		{
			if (lowcost[j] < min && lowcost[j] != 0)
			{
				min = lowcost[j];
				min_next = j; //min_next代表着要加入的下一个最小点
			}
		}
		sum += min;
		lowcost[min_next] = 0;
		//更新lowcost数组
		for (j = 2; j <= n; j++)
		{
			if (graph[min_next][j] < lowcost[j])
			{
				lowcost[j] = graph[min_next][j];
				pre[j] = min_next;
			}
		}
	}
	return sum;
}

int main()
{
	ios::sync_with_stdio(false); //关同步，提高cin / cout效率
	int i, j, k, m, n;
	int cost;
	cin >> m >> n; //m=顶点的个数，n=边的个数
	//初始化图G
	for (i = 1; i <= m; i++)
	{
		for (j = 1; j <= m; j++)
		{
			graph[i][j] = MAXCOST;
		}
	}
	//构建图G
	for (k = 1; k <= n; k++)
	{
		cin >> i >> j >> cost;
		if (cost < graph[i][j])
		{
			graph[i][j] = cost;
			graph[j][i] = cost;
		}
	}
	//求解最小生成树
	cost = prim(graph, m);
	//输出最小权值和
	cout << cost << endl;
	cin >> m;
	return 0;
}

交通——kruskal算法


#include <bits/stdc++.h>
using namespace std;

struct edge
{
    int u, v, w;
} e[10000];

bool cmp(edge a, edge b) //比较两个边的权重
{
    if (a.w < b.w)
        return true;
    else
        return false;
}

//并查集——确定有无回路
int father[10000];
int find(int a)
{
    if (father[a] == a)
        return a;
    return father[a] = find(father[a]);
}

void UNION(int a, int b)
{
    a = find(a);
    b = find(b);
    if (a != b)
        father[a] = b;
}

int main()
{
    int n, m;

    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> e[i].u >> e[i].v >> e[i].w;
    }
    sort(e + 1, e + m + 1, cmp); //把边按边权排序！
    for (int i = 1; i <= n; i++)
        father[i] = i;
    int len_number = 0; //记录添加到最小生成树中的边数——最终=n-1即可 ！！！
    int result = 0;     //记录边权值和
    for (int i = 1; i <= m && len_number < n - 1; i++)
    {
        int u = e[i].u;
        int v = e[i].v;
        if (find(u) == find(v)) //若产生回路，不加这条边
            continue;
        else //否则加这条边
        {
            len_number++; //记录最小生成树中的边数
            UNION(u, v);
            result += e[i].w;
        }
    }
    cout << result;
    cin >> n;
    return 0;
}

两种不同实现的代码的时间对比

IDprime/(ms)kruskal/(ms)
101
232
320
400
523
633
732
800
921
1010

水

prime算法

//用虚拟边，构造一个0结点，将所有点对应的打井值转换到边上，相当于就是最小生成树来做
#include <bits/stdc++.h>
using namespace std;

#define MAX 10000
#define MAXCOST 0x7fffffff

int graph[MAX][MAX];

//n为所有顶点个数
int prim(int graph[][MAX], int n)
{
	int lowcost[MAX];
	int pre[MAX]; //pre是用来记录这个点的前驱是哪一个
	int i, j, min, min_next, sum = 0;
	//以第一个结点为开始
	for (i = 1; i <= n; i++)
	{
		lowcost[i] = graph[0][i];
		pre[i] = 0; //这些点的前一个都是第一个点
	}
	pre[0] = -1;
	for (i = 1; i <= n; i++) //需要找n条边
	{
		min = MAXCOST;
		min_next = 0;
		for (j = 1; j <= n; j++) //找到要加入的下一个点
		{
			if (lowcost[j] < min && lowcost[j] != 0)
			{
				min = lowcost[j];
				min_next = j; //min_next代表着要加入的下一个最小点
			}
		}
		sum += min;
		lowcost[min_next] = 0;
		//更新lowcost数组
		for (j = 1; j <= n; j++)
		{
			if (graph[min_next][j] < lowcost[j])
			{
				lowcost[j] = graph[min_next][j];
				pre[j] = min_next;
			}
		}
	}
	return sum;
}

int main()
{
	ios::sync_with_stdio(false); //关同步，提高cin / cout效率
	int i, j, n, k;
	int cost;
	cin >> n ;//n为点的个数，但我们构造了一个0结点，故0结点加上
	//初始化图G
	for (i = 0; i <= n; i++)
	{
		for (j = 0; j <= n; j++)
		{
			graph[i][j] = MAXCOST;
		}
	}
    for(i=1;i<=n;i++)
    {
        cin>>k;
        graph[i][0]=k;
        graph[0][i]=k;
    }
	//构建图G
	for(i=1;i<=n;i++)
	{
        for(j=1;j<=n;j++)
        {
            cin>>k;
            if(k==0){
                graph[i][j]=MAXCOST;
            }
            else
			graph[i][j]=k;
        }
    }
	//求解最小生成树
	cost = prim(graph, n);
	//输出最小权值和
	cout << cost << endl;
	return 0;
}

kruskal算法


#include <bits/stdc++.h>
using namespace std;

struct edge
{
    int u, v, w;
} e[100000];

bool cmp(edge a, edge b) //比较两个边的权重
{
    if (a.w < b.w)
        return true;
    else
        return false;
}

//并查集——确定有无回路
int father[100000];
//路径压缩优化一下
int find(int a)
{
    if (father[a] == a)
        return a;
    return father[a] = find(father[a]);
}

void UNION(int a, int b)
{
    a = find(a);
    b = find(b);
    if (a != b)
        father[a] = b;
}

int main()
{
    int n, m;
    int k;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> k;
        e[i].u = 0;
        e[i].v = i;
        e[i].w = k;
    }
    int count = n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            cin >> k;
            if (i != j)
            {
                count++;
                e[count].u = i;
                e[count].v = j;
                e[count].w = k;
            }
        }
    sort(e + 1, e + n * n + 1, cmp); //把边按边权排序！
    for (int i = 1; i <= n*n; i++)
        father[i] = i;
    int len_number = 0; 
    int result = 0;    
    for (int i = 1; i <= n * n && len_number < n; i++)
    {
        int u = e[i].u;
        int v = e[i].v;
        if (find(u) == find(v)) //若产生回路，不加这条边
            continue;
        else //否则加这条边
        {
            len_number++; //记录最小生成树中的边数
            UNION(u, v);
            result += e[i].w;
        }
    }
    cout << result;
    cin >> n;
    return 0;
}

对比

IDprime/(ms)kruskal/(ms)
100
200
302
400
514
6310
7515
8722
9628
1011

五、总结

kruscal算法总共选择n-1条边，所使用的贪婪准则是：从剩下的边种选择一条不会产生环路，且有最小消耗的边加入已选择的边的集合内。Prime算法的核心步骤是：在带权连通图中V是包含所有顶点的集合， U已经在最小生成树中的节点，从图中任意某一顶点v开始，此时集合U={v}，重复执行下述操作：在所有u∈U,w∈V-U的边(u,w)∈E中找到一条权值最小的边，将(u,w)这条边加入到已找到边的集合，并且将点w加入到集合U中，当U=V时，就找到了这颗最小生成树。

水题这道题也可以转换成最小生成树的问题是因为：关于在农村自己打井的费用，其实我们可以构造一个0结点，这样自己打井的费用则可以转换成从该地到0结点边上的权重，这样也就是转换成了最小生成树问题。交通问题那道题我们可以发现prime算法与kruskal算法运行时间差别不大，但在水题中明显可以看出prime算法是更快的，通过分析可以发现在图较稀疏和较稠密的，二者时间运行差不多，但是当图较为稀疏时，kruskal算法是优于prime算法的，而当图很稠密时，prime算法是更快更优的。

补充

还有助教所补充的关于连接所有点的最小费用的问题 这道题与前面两道思路其实都是一样的都是最小生成树问题，而这道题中两点之间边上的权值其实就是就是两个点之间的曼哈顿距离，所以这道题多的一步就是我们需要自己算出每条边的权值罢了，剩下的还是可以用两种方法，prime和kruskal算法来求解。

输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
输出：20
解释：

代码除了主函数读入那部分需要修改，还要改权重部分，其他都是一样的

int w = abs(points[i][0]-points[j][0])+abs(points[i][1]-points[j][1]);

文档信息

Search

    Table of Contents