最小生成树prime

水深无声 2022-08-04 16:57 228阅读 0赞

prime算法

每次加入已（加入树集合）结点连着（未加入树）的最短边直至所有结点加入最小生成树

源代码：

#include
#include
#include
#define ssize_t 100
#define max_int 123456789

typedef struct Node
{
int map[ssize_t][ssize_t];
int n_num;
int sum;
}Adjacency_list;

void prime(Adjacency_list *g)
{
int i;
int j;
int k;
int temp;
int *lowcost = (int *)malloc(sizeof(int) * g->n_num);
bool *visited = (bool *)malloc(sizeof(bool) * g->n_num);

memset(visited,false,sizeof(visited));
visited[1] = true;

for(i = 1;i <= g->n_num;i++)
{
lowcost[i] = g->map[1][i];
}

for(i = 2;i <=g->n_num;i++)
{
temp = max_int;

for(j = 2;j <=g->n_num;j++)
{
if(!visited[j] && lowcost[j] < temp)
{
k = j;
temp = lowcost[j];
}
}

visited[k] = true;
g->sum = g->sum + temp;

for(j = 1;j <= g->n_num;j++)
{
if(!visited[j] && lowcost[j] > g->map[k][j])
{
lowcost[j] = g->map[k][j];
}
}

}

}

int main()
{
int i;
int j;
int n;
int m;
int p,q,value;

scanf(“%d%d”,&n,&m);

Adjacency_list t;
t.n_num = n;
t.sum = 0;

for(i = 1;i <= n;i++)
{
for(j = 1;j <= n;j++)
{
t.map[i][j] = max_int;
}
}

for(i = 1;i <= m;i++)
{
scanf(“%d%d%d”,&p,&q,&value);
t.map[p][q] = value;
t.map[q][p] = value;
}

prime(&t);
printf(“%d”,t.sum);
return 0;
}SouthEast

发表评论

表情：
评论列表 （有 0 条评论，228人围观）

还没有评论，来说两句吧...

相关阅读

    相关 最小生成树prime

    prime算法 每次加入已（加入树集合）结点连着（未加入树）的最短边直至所有结点加入最小生成树 源代码： \include<stdio.h> \include<std

    水深无声水深无声/ 0 赞/ 229 阅读

    相关 最小生成树

    问题提出： 要在n个城市间建立通信联络网。顶点：表示城市，权：城市间通信线路的花费代价。希望此通信网花费代价最小。 问题分析： 答案只能从生成树中找，因为要做到任何

    雨点打透心脏的1/2处雨点打透心脏的1/2处/ 0 赞/ 370 阅读