最小生成树算法

[c++]代码库
#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INFINITY 30000    //定义一个权值的最大值
#define MAX_VERTEX_NUM 20 //图的最大顶点数
typedef struct
{
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
    int vexnum,arcnum;                //图的当前顶点和边数
} Graph;
typedef struct
{
    int adjvex;  //某顶点与已构造好的部分生成树的顶点之间权值最小的顶点
    int lowcost; //某顶点与已构造好的部分生成树的顶点之间的最小权值
} ClosEdge[MAX_VERTEX_NUM]; //用普里姆算法求最小生成树时的辅助数组
void CreateGraph ( Graph & ); //生成图的邻接矩阵
void MiniSpanTree_PRIM ( Graph,int ); //用普里姆算法求最小生成树
int  minimum ( ClosEdge,int ); //在普里姆算法中求下一个结点
void main()
{
    Graph G;  //采用邻接矩阵结构的图
    char j='y';
    int u;
    textbackground ( 3 );  //设定屏幕颜色
    textcolor ( 15 );
    clrscr();
//------------------程序解说----------------------------
    printf ( "本程序将演示构造图的最小代价生成树。\n" );
    printf ( "首先输入图的顶点数和弧数.\n格式：顶点数，弧数；例如:4,4\n" );
    printf ( "接着输入各条弧(弧尾,弧头)和弧的权值。\n" );
    printf ( "格式:弧尾，弧头，权值；例如\n1,2,1\n1,3,2\n2,4,3\n3,4,4\n" );
    printf ( "程序将会构造该图的最小代价生成树。\n" );
    printf ( "并显示该最小生成树。\n1,2\n1,3\n2,4\n" );
//------------------------------------------------------
    while ( j!='N'&&j!='n' )
    {
        printf ( "请输入图的顶点和弧数:" );
        scanf ( "%d,%d",&G.vexnum,&G.arcnum ); //输入图的顶点数和边数
        CreateGraph ( G );    //生成邻接矩阵结构的图
        printf ( "从哪一顶点开始:" );
        scanf ( "%d",&u );  //输入普里姆算法中的起始顶点
        MiniSpanTree_PRIM ( G,u ); //普里姆算法求最小生成树
        printf ( "最小代价生成树构造完毕，继续进行吗?(Y/N)" );
        scanf ( " %c",&j );
    }
}
 
void CreateGraph ( Graph &G )
{//构造邻接矩阵结构的图G
    int i,j;
    int start,end,weight;
    for ( i=1; i<=G.vexnum; i++ )
        for ( j=1; j<=G.vexnum; j++ )
            G.arcs[i][j]=INFINITY; //初始化邻接矩阵
    printf ( "输入弧和其权值，格式：弧尾，弧头，权值\n" );
    for ( i=1; i<=G.arcnum; i++ )
    {
        scanf ( "%d,%d,%d",&start,&end,&weight ); //输入边的起点和终点及权值
        G.arcs[start][end]=weight;
        G.arcs[end][start]=weight;
    }
}
void MiniSpanTree_PRIM ( Graph G,int u )
{//从第u个顶点出发构造图G的最小生成树
    ClosEdge closedge;
    int i,j,k;
    printf ( "最小代价生成树:\n" );
    for ( j=1; j<=G.vexnum; j++ ) //辅助数组初始化
        if ( j!=u )
        {
            closedge[j].adjvex=u;
            closedge[j].lowcost=G.arcs[u][j];
        }
    closedge[u].lowcost=0; //初始，U={u}
    for ( i=1; i<G.vexnum; i++ ) //选择其余的G.vexnum-1个顶点
    {
        k=minimum ( closedge,G.vexnum ); //求出生成树的下一个顶点
        printf ( "%d,%d\n",closedge[k].adjvex,k ); //输出生成树的边
        closedge[k].lowcost=0;   //第k顶点并入U集
        for ( j=1; j<=G.vexnum; j++ ) //新顶点并入U后，重新选择最小边
            if ( G.arcs[k][j]<closedge[j].lowcost )
            {
                closedge[j].adjvex=k;
                closedge[j].lowcost=G.arcs[k][j];
            }
    }
}
int minimum ( ClosEdge cl,int vnum )
{//在辅助数组cl[vnum]中选择权值最小的顶点，并返回其位置
    int i;
    int w,p;
    w=INFINITY;
    for ( i=1; i<=vnum; i++ )
        if ( cl[i].lowcost!=0&&cl[i].lowcost<w )
            {w=cl[i].lowcost; p=i;}
    return p;
}
用户注册

用户登录

发表随想

该用户最新代码

编程随想

[c++]代码库

网友评论 (发表评论)

回复评论

发表评论：

评论须知：

扫码下载

输入口令后可复制整站源码
