1363 - 算法7-9：最小生成树
最小生成树问题是实际生产生活中十分重要的一类问题。假设需要在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时，自然需要考虑这样一个问题，即如何在最节省经费的前提下建立这个通信网。
可以用连通网来表示n个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，需要选择一棵生成树，使总的耗费最小。这个问题就是构造连通网的最小代价生成树，简称最小生成树。一棵生成树的代价就是树上各边的代价之和。
而在常用的最小生成树构造算法中，普里姆（Prim）算法是一种非常常用的算法。以下是其算法的大致结构：
<span style="font-family:宋体;">在本题中，读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法建立最小生成树，并输出最小生成树的代价。</span>
<span></span>
Input
输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。
以后的n行中每行有n个用空格隔开的整数，对于第i行的第j个整数，如果不为0，则表示第i个顶点和第j个顶点有直接连接且代价为相应的值，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。
输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图，且保证图中只有一个连通分量。
Output
只有一个整数，即最小生成树的总代价。请注意行尾输出换行。
Examples
Input
4 0 2 4 0 2 0 3 5 4 3 0 1 0 5 1 0
Output
6
Hint
在本题中，需要掌握图的深度优先遍历的方法，并需要掌握无向图的连通性问题的本质。通过求出无向图的连通分量和对应的生成树，应该能够对图的连通性建立更加直观和清晰的概念。
Solution C
#include<stdio.h> #define MAX_VERTEX_NUM 100 int parent[MAX_VERTEX_NUM]; typedef struct { int weight; int begin; int end; }Edge; int Find(int *parent,int f) { while(parent[f]>0) f=parent[f]; return f; } int main() { int N,num,k=0,sum=0,m,n; Edge edges[MAX_VERTEX_NUM*MAX_VERTEX_NUM],temp; scanf("%d",&N); for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { scanf("%d",&num); if(num!=0&&i<j) { edges[k].weight=num; edges[k].begin=i; edges[k].end=j; k++; } } } for(int i=0;i<k;i++) { for(int j=i;j<k;j++) { if(edges[i].weight>edges[j].weight) { temp.weight=edges[i].weight; temp.begin=edges[i].begin; temp.end=edges[i].end; edges[i].weight=edges[j].weight; edges[i].begin=edges[j].begin; edges[i].end=edges[j].end; edges[j].weight=temp.weight; edges[j].begin=temp.begin; edges[j].end=temp.end; } } } for(int i=0;i<N;i++) { parent[i]=0; } for(int i=0;i<k;i++) { n=Find(parent,edges[i].begin); m=Find(parent,edges[i].end); if(n!=m) { parent[n]=m; sum+=edges[i].weight; } } printf("%d\n",sum); return 0; }
Solution C++
#include <cstdio> #include <cstdlib> const int MAXN = 50; // 最大顶点数 const int INF = 1000000000; // 作为标记的无穷大值 int mat[MAXN][MAXN]; // 无向图的邻接矩阵 int mind[MAXN]; // 辅助数组 int v[MAXN]; // 标记顶点是否被访问过的数组 int n; // 顶点的个数 int prim() { int ret = 0, i, j, k; for (i = 0; i<n; i++) { mind[i] = INF; v[i] = 0; } for (mind[j = 0] = 0; j < n; j++) { for (k = -1, i = 0; i < n; i++) { if (!v[i] && (k == -1 || mind[i] < mind[k])) { k = i; } } v[k] = 1; ret += mind[k]; for (i = 0; i < n; i++) { if (!v[i] && mat[k][i] < mind[i]) { mind[i] = mat[k][i]; } } } return ret; } int main() { scanf("%d", &n); for (int i = 0;i < n;i++) { // 读入无向图的邻接矩阵 for (int j = 0;j < n;j++) { scanf("%d", &mat[i][j]); if (mat[i][j] == 0) mat[i][j] = INF; } } printf("%d\n", prim()); return 0; }
Hint
在本题中，需要掌握图的深度优先遍历的方法，并需要掌握无向图的连通性问题的本质。通过求出无向图的连通分量和对应的生成树，应该能够对图的连通性建立更加直观和清晰的概念。