最小生成树prime

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

prime算法

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

源代码：

\#include<stdio.h>  
\#include<stdlib.h>  
\#include<string.h>  
\#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][]

[SouthEast]: /images/20220805/9ee139d7dfc14e00b883b16d73cae8f0.png

发表评论取消回复

表情：

评论列表（有 0 条评论，160人围观）

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

相关阅读

相关生成树相关问题（最小生成树变形，次小生成树，最小度限度生成树，极差最小生成树）

生成树相关问题（最小生成树变形，次小生成树，最小度限度生成树，极差最小生成树）视频：[https://www.bilibili.com/video/BV1G64y187ke

Bertha 。/ 2022年09月12日 05:52/ 0 赞/ 215 阅读

相关数据结构——最小生成树之prime算法

include<iostream> include<cstring> include<vector> define INF 0x3f3f3f3f

￡神魔★判官ぃ/ 2022年08月28日 01:47/ 0 赞/ 164 阅读

相关最小生成树prime

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

水深无声/ 2022年08月04日 16:57/ 0 赞/ 161 阅读

相关 poj2031-Building a Space Station（最小生成树，kruskal，prime）

Building a Space Station <table> <tbody> <tr> <td><strong>Time Limit:</strong>

分手后的思念是犯贱/ 2022年08月04日 11:35/ 0 赞/ 135 阅读

相关最小生成树的prime算法

1. /\\ 2. \ 最小生成树的prim[算法][Link 1] 3. \ @author liuy 4. \/ 5. public class

柔情只为你懂/ 2022年07月16日 11:15/ 0 赞/ 166 阅读

相关最小生成树

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

雨点打透心脏的1/2处/ 2022年03月18日 12:28/ 0 赞/ 298 阅读

相关最小生成树详细讲解（Prime算法+Kruskalsuanfa）

生成树一个连通图（如果图中任意两点都是连通的，那么图被称作连通图。如果此图是有向图，则称为强连通图（注意：需要双向都有路径））的生成树是该连通图的一个极小连同子图,它含

忘是亡心i/ 2022年02月18日 13:13/ 0 赞/ 451 阅读

相关 Constructing Roads 最小生成树（prime（）），注意边的处理方式

Problem Description There are N villages, which are numbered from 1 to N, and you shoul

柔光的暖阳◎/ 2022年01月07日 22:37/ 0 赞/ 220 阅读

相关最小生成树

Jungle Roads [http://poj.org/problem?id=1251][http_poj.org_problem_id_1251] Descrip

逃离我推掉我的手/ 2021年11月29日 22:28/ 0 赞/ 434 阅读

相关最小生成树（prime算法）

伪代码 S:当前已经在联通块中的所有点的集合 dist[i] = inf for n 次 t<-S外离S最近的点

桃扇骨/ 2021年06月22日 15:37/ 0 赞/ 499 阅读