3048: 数据结构课程设计

题目描述

输入

暂无

输出

暂无

样例输入

暂无

样例输出

暂无

参考代码

// 10  对给定的网和起点，实现求解最小生成树的Prim算法
#include<stdio.h>
#define max 100
#define maxcost 1000
int m,n;
int graph[max][max];
//邻接矩阵
void creatgraph() 
{
    int i,j,k;
    int cost;
    scanf("%d%d",&m,&n);
    for (i=1;i<=m;i++) 
    {
        for (j=1;j<=m;j++) 
        {
            graph[i][j]=maxcost;
        }
    }
    for (k=1;k<=n;k++) 
    {
        scanf("%d%d%d",&i,&j,&cost);
        graph[i][j]=cost;
        graph[j][i]=cost;
    }
}
void prim() 
{
    int lowcost[max];
    int mst[max];
    //顶点
    int i,j,min,minid,sum=0;
    for (i=2;i<=m;i++) 
    {
        lowcost[i]=graph[1][i];
        mst[i]=1;
    }
    mst[1]=0;
    for (i=2;i<=m;i++) 
    {
        min=maxcost;
        minid=0;
        for (j=2;j<=m;j++) 
        {
            if(lowcost[j]<min&&lowcost[j]!=0) 
            {
                min=lowcost[j];
                minid=j;
            }
        }
        sum=sum+min;
        lowcost[minid]=0;
        for (j=2;j<=m;j++) 
        {
            if (graph[minid][j]<lowcost[j]) 
            {
                lowcost[j]=graph[minid][j];
                mst[j]=minid;
            }
        }
    }
    printf("最小生成树=%d",sum);
}
int main() 
{
    creatgraph();
    prim();
    return 0;
}

解析

暂无