请用c++写一个最小生成树代码
时间: 2023-03-14 21:08:41 浏览: 59
答:以下是一个用C语言写的最小生成树代码: #include<stdio.h>
#define MAX 20
int n; // 图中顶点数
int cost[MAX][MAX]; // 邻接矩阵
int near[MAX]; // 标记最小生成树中各顶点的最近顶点
int tree[MAX][2]; // 最小生成树
void prim()
{
int i,j,k,min;
for(i=2; i<=n; i++)
{
near[i] = 1;
}
for(i=1; i<=n-1; i++)
{
min = 999;
for(j=2; j<=n; j++)
{
if(near[j] != 0 && cost[j][near[j]] < min)
{
k=j;
min=cost[j][near[j]];
}
}
tree[i][0] = k;
tree[i][1] = near[k];
near[k] = 0;
for(j=2; j<=n; j++)
{
if(near[j] != 0 && cost[j][near[j]] > cost[j][k])
{
near[j] = k;
}
}
}
}