首页 > 学院 > 开发设计 > 正文

Prim算法的C语言程序

2019-11-14 10:41:22
字体:
来源:转载
供稿:网友

PRim算法是有关图的最小生成树的算法。1957年由美国计算机科学家罗伯特·普里姆(Robert C. Prim)独立发现。

程序来源:Prim's Algorithm。

百度百科:Prim算法。

维基百科:Prim's Algorithm。

需要说明的是,该程序使用了三重循环,其计算速度相当的慢,可以说是不可用的。

C语言程序(去除了原文中非标准的C语言代码):

#include <stdio.h>int a,b,u,v,n,i,j,ne=1;int visited[10]={0},min,mincost=0, cost[10][10];int main(){    printf("/nEnter the number of nodes:");    scanf("%d",&n);    printf("/nEnter the adjacency matrix:/n");    for(i=1;i<=n;i++)        for(j=1;j<=n;j++) {            scanf("%d",&cost[i][j]);            if(cost[i][j] == 0)                cost[i][j] = 999;        }    visited[1]=1;    printf("/n");    while(ne < n)    {        for(i=1,min=999; i<=n; i++)            for(j=1; j<=n; j++)                if(cost[i][j] < min)                    if(visited[i] != 0) {                        min = cost[i][j];                        a = u = i;                        b = v = j;                    }        if(visited[u]==0 || visited[v]==0)        {            printf("/n Edge %d:(%d %d) cost:%d",ne++,a,b,min);            mincost+=min;            visited[b]=1;        }        cost[a][b] = cost[b][a] = 999;    }    printf("/n Minimun cost=%d/n",mincost);}运行结果:

Enter the number of nodes:6Enter the adjacency matrix:0 3 1 6 0 03 0 5 0 3 01 5 0 5 6 46 0 5 0 0 20 3 6 0 0 60 0 4 2 6 0 Edge 1:(1 3) cost:1 Edge 2:(1 2) cost:3 Edge 3:(2 5) cost:3 Edge 4:(3 6) cost:4 Edge 5:(6 4) cost:2 Minimun cost=13


发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表