最小生成树

1.5k 词

题目描述

最小生成树问题是实际生产生活中十分重要的一类问题。假设需要在n个城市之间建立通信联络网,则连通n个城市只需要n-1条线路。这时,自然需要考虑这样一个问题,即如何在最节省经费的前提下建立这个通信网。

可以用连通网来表示n个城市以及n个城市之间可能设置的通信线路,其中网的顶点表示城市,边表示两个城市之间的线路,赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树,每一棵生成树都可以是一个通信网。现在,需要选择一棵生成树,使总的耗费最小。这个问题就是构造连通网的最小代价生成树,简称最小生成树。一棵生成树的代价就是树上各边的代价之和。

而在常用的最小生成树构造算法中,普里姆(Prim)算法是一种非常常用的算法。以下是其算法的大致结构:

在本题中,读入一个无向图的邻接矩阵(即数组表示),建立无向图并按照以上描述中的算法建立最小生成树,并输出最小生成树的代价。

输入

输入的第一行包含一个正整数n,表示图中共有n个顶点。其中n不超过50。

以后的n行中每行有n个用空格隔开的整数,对于第i行的第j个整数,如果不为0,则表示第i个顶点和第j个顶点有直接连接且代价为相应的值,0表示没有直接连接。当i和j相等的时候,保证对应的整数为0。

输入保证邻接矩阵为对称矩阵,即输入的图一定是无向图,且保证图中只有一个连通分量。

输出

只有一个整数,即最小生成树的总代价。请注意行尾输出换行。

样例输入

1
2
3
4
5
4
0 2 4 0
2 0 3 5
4 3 0 1
0 5 1 0

样例输出

1
6

提示

在本题中,需要掌握图的深度优先遍历的方法,并需要掌握无向图的连通性问题的本质。通过求出无向图的连通分量和对应的生成树,应该能够对图的连通性建立更加直观和清晰的概念。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<stdio.h>
#define N 120
int e[N][N], dis[N], book[N];
int main() {
int i, j, k, m, n, min, count = 0, sum = 0, inf = 99999999;
scanf("%d", &n);
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (i == j)
e[i][j] = 0;
else
e[i][j] = inf;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++) {
scanf("%d", &e[i][j]);
if (i != j && e[i][j] == 0)
e[i][j] = e[j][i] = inf;
}
for (i = 1; i <= n; i++)
dis[i] = e[1][i];
book[1] = 1;
count++;
while (count < n) {
min = inf;
for (i = 1; i <= n; i++) {
if (book[i] == 0 && dis[i] < min) {
min = dis[i];
j = i;
}
}
book[j] = 1;
count++;
sum = sum + dis[j];
for (k = 1; k <= n; k++)
if (book[k] == 0 && dis[k] > e[j][k])
dis[k] = e[j][k];
}
printf("%d\n", sum);
return 0;
}