题目描述

求出给定无向带权图的最小生成树。图的定点为字符型，权值为不超过100的整形。在提示中已经给出了部分代码，你只需要完善Prim算法即可。

#include< iostream>
使用命名空间 std;

typedef struct
{
int n;
int e;
字符数据[500];
整型边[500][500];
}图形;

typedef struct
{
int index;
整型成本;
}mincost;

typedef struct
{
int x;
int y;
整型重量;
}边缘;

typedef struct
{
int index;
int 标志;
}F;

void create（Graph &G，int n ，int e）
{
int i，j，k，w;
字符 a，b;
for（i=0;i< n;i++）
cin>>G.data[i];
for（i=0;i< n;i++）
for（j=0;j< n;j++）
{
if（i==j）
G.edge[i][j]=0;
else
G.edge[i][j]=100;
} 

for（k=0;k< e;k++）
{
cin>>a;
辛>>b;
cin>>w;
for（i=0;i< n;i++）
if（G.data[i]==a） break;
for（j=0;j< n;j++）
if（G.data[j]==b） break;

G.edge[i][j]=w;
G.edge[j][i]=w;
}
G.n=n;
G.e=e;
} 

void Prim（Graph &G，int k）
{ 

完成Prim算法

} 

int main（）
{
Graph my;
int n，e;
cin>>n>>e;
create（my，n，e）;
Prim（my，0）;
返回 0;
} 

输入

第一行为图的顶点个数n第二行为图的边的条数e接着e行为依附于一条边的两个顶点和边上的权值

输出

最小生成树中的边。

样例输入

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

样例输出

(A,C)(C,F)(F,D)(C,B)(B,E)

#include<stdio.h>  
#include<algorithm>  
#include<math.h>  
#include<string.h>  
#include<iostream>  
using namespace std;
int mp[20][20], n, e;
char str[20];
 
void Prim()
{
	int a[20];
	int min;
	int b[20], i, j, k;
	for (i = 0; i<n; i++)//给lowcost[]和closest[]置初值  
	{
		a[i] = mp[0][i];
		b[i] = 0;
	}
	for (i = 1; i<n; i++)
	{
		min = 101;
		for (j = 0; j<n; j++)//在(V-U)中找出离U最近的顶点k  
		{
			if (a[j] != 0 && a[j]<min)
			{
				min = a[j];
				k = j;//k记录最近顶点的编号   
			}
		}
		cout << "(" << str[b[k]] << "," << str[k] << ")";
		a[k] = 0;//标记k已经加入U  
		for (j = 0; j<n; j++)//修改数组lowcost和closest  
		{
			if (mp[k][j] != 0 && mp[k][j]<a[j])
			{
				a[j] = mp[k][j];
				b[j] = k;
			}
		}
	}
}
 
int main()
{
	cin >> n >> e >> str;
	memset(mp, 101, sizeof(mp));
	for (int i = 0; i<n; i++)
	{
		mp[i][i] = 0;
	}
	for (int j = 0; j<e; j++)
	{
		char l, r;
		int w;
		cin >> l >> r >> w;
		int t = 0, tt = 0;
		for (int i = 0; i < n; i++) {
			if (l == str[i])t = i;
			if (r == str[i])tt = i;
		}
		mp[t][tt] = w;
		mp[tt][t] = w;
	}
	Prim();
	return 0;
}