prim算法 求最小生成树 1075
生成树 贪心
求出给定无向带权图的最小生成树。图的定点为字符型，权值为不超过100的整形。在提示中已经给出了部分代码，你只需要完善Prim算法即可。
Description
第一行为图的顶点个数n
第二行为图的边的条数e
接着e行为依附于一条边的两个顶点和边上的权值
第二行为图的边的条数e
接着e行为依附于一条边的两个顶点和边上的权值
Input
最小生成树中的边。
Output
| 1 2 3 4 5 6 7 8 9 10 11 12 13 | 6 10 ABCDEF A B 6 A C 1 A D 5 B C 5 C D 5 B E 3 E C 6 C F 4 F D 2 E F 6 |
Sample Input
| 1 | (A,C)(C,F)(F,D)(C,B)(B,E) |
#include<stdio.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<string.h>
using namespace std;
#define mem(x,y) memset(x,y,sizeof(x))
int maps[105][105];
char dian[1000];
void pri(int n, int e)
{
int disx[1000];
int close[1000];
for (int i = 0; i < e; i++)
{
disx[i] = maps[0][i];
close[i] = 0;
}
for (int i = 1; i < n; i++)
{
int min = 0xfff, k;
for (int j = 0; j < n; j++)
{
if (disx[j] != 0 && disx[j] < min)
{
k = j;
min = disx[j];
}
}
cout << '(' << dian[close[k]] << ',' << dian[k] << ')';
disx[k] = 0;
for (int j = 0; j < n; j++)
{
if (maps[k][j] != 0 && maps[k][j] < disx[j])
{
disx[j] = maps[k][j];
close[j] = k;
}
}
}
}
int main()
{
int n;
int e;
while (cin >> n)
{
cin >> e;
scanf("%s", dian);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
maps[i][j] = i == j ? 0 : 0xfff;
}
}
for (int i = 0; i < e; i++)
{
char from, to;
int dis;
cin >> from >> to >> dis;
maps[from - 'A'][to - 'A'] = dis;
maps[to - 'A'][from - 'A'] = dis;
}
pri(n, e);
}
return 0;
}
