Prim算法的C语言程序

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