最小生成树之Prim算法

Prim算法:

假设N = (V,{E})是连通网,TE是N上最小生成树中边的集合。算法从U={u0}(u0属于V),TE={}开始,重复执行下述操作:在所有u属于U,v属于V-U的边(u,v)属于E中找到一条代价最小的边(u0,v0)并入集合TE,同时v0并入U,直至U=V为止,此时TE中必有n-1条边,则T=(V,{TE})为N的最小生成树.

为实现这个算法,需附设一个辅助数组closedge,以记录从U到V-U具有最小代价的边。对每个顶点vi属于V-U,在辅助数组中存在一个相应分量closedge[i-1],它包括两个域,lowcost域存储该边的权,vex域存储该边依附的在U中的顶点。

考虑如下无向网:

邻接矩阵:

其最小生成树为:

Prim算法过程(图以邻接矩阵表示,假设从顶点a出发):

1.首先初始化辅助数组,将顶点u纳入U集:

2.迭代n-1次,n为顶点数,每次迭代都调用mininum方法返回一个最小k值,然后输出生成树的边,并将第k顶点纳入u集,最后更新辅助数组。

比如第一次循环时,k = 2(很显然最小权为1=min{6,1,5},序号为2,即k = 2);输出生成树的边(a,c),将邻接矩阵第k顶点纳入U集(顶点c),即将lowcost置0,此时对应的辅助数组如下:

下面将更新辅助数组,即挨个比较辅助数组与邻接表第k行的元素,如果邻接表的对应值小,那么就替换辅助数组值.

此时第一轮循环结束,下面进入第二次循环,此时k = 5......

实现:

/**********************************************
Prim算法求最小生成树
by Rowandjj
2014/7/1
***********************************************/
#include<iostream>
using namespace std;
//---------------------------------------
#define MAX_VERTEX_NUM 20//边的最大值
#define INFINTY 65535//代表无穷大

typedef struct _ARC_
{
    int adj;//顶点关系类型
    char *info;//弧信息
}Arc,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct _GRAPH_
{
    char vexs[MAX_VERTEX_NUM];//顶点向量
    AdjMatrix arcs;//邻接矩阵
    int vexnum,arcnum;//顶点数、弧数
}Graph;

//----------------------------------------
typedef struct _ARRAY_//辅助数组
{
    char adjvex;//存储顶点
    int lowcost;//存储权值
}minside[MAX_VERTEX_NUM];

//----------------------------------------
//图操作
int LocateVex(Graph G,char u);
bool CreateAN(Graph *G);//构建无向网
void Display(Graph G);//打印无向网
//prim算法
void MiniSpanTree_PRIM(Graph G,char u);//用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边
int mininum(minside SZ,Graph G);//求closedge.lowcost的最小正值
//---------------------------------------
int LocateVex(Graph G,char u)
{
    int i;
    for(i = 0; i < G.vexnum; i++)
    {
        if(G.vexs[i] == u)
        {
            return i;
        }
    }
    return -1;
}
bool CreateAN(Graph *G)
{
    int i,j,k;
    int IncInfo;
    char va,vb;//顶点
    int w;//权
    char *info;
    char str[20];

    cout<<"请输入无向网G的顶点数,边数,边是否含其它信息(是:1,否:0):\n";
    cin>>G->vexnum;
    cin>>G->arcnum;
    cin>>IncInfo;

    cout<<"输入顶点的值:";
    //初始化顶点
    for(i = 0; i < G->vexnum; i++)
    {
        cin>>G->vexs[i];
    }
    //初始化邻接矩阵
    for(i = 0; i < G->vexnum; i++)
    {
        for(j = 0; j < G->vexnum; j++)
        {
            G->arcs[i][j].adj = INFINTY;
            G->arcs[i][j].info = NULL;
        }
    }
    cout<<"依次输入每条边的两个顶点及权值"<<endl;
    //初始化边
    for(k = 0; k < G->arcnum; k++)
    {
        cin>>va;
        cin>>vb;
        cin>>w;

        i = LocateVex(*G,va);
        j = LocateVex(*G,vb);

        G->arcs[i][j].adj = w;
        G->arcs[j][i].adj = w;
        if(IncInfo)//弧信息
        {
            cout<<"输入该边的相关信息:";
            cin>>str;
            w = strlen(str)+1;
            if(w)
            {
                info = (char *)malloc(sizeof(char)*(w+1));
                strcpy(info,str);
                G->arcs[i][j].info = G->arcs[j][i].info = info;
            }
        }
    }

    return true;
}
void Display(Graph G)
{
    int i,j;
    cout<<"顶点:";
    for(i = 0; i < G.vexnum; i++)
    {
        cout<<G.vexs[i]<<"    ";
    }
    cout<<"\n邻接矩阵:\n";
    for(i = 0; i < G.vexnum; i++)
    {
        for(j = 0; j < G.vexnum; j++)
        {
            cout<<G.arcs[i][j].adj<<"    ";
        }
        cout<<endl;
    }
    cout<<endl;
}
//---------------------------------------------------------
int mininum(minside SZ,Graph G)
{
    int i = 0,j;
    int min;//存储最小权值
    int k;//存储权值最小的元素在数组中的位置
    while(!SZ[i].lowcost)//忽略lowcost为0的元素
    {
        i++;
    }
    min = SZ[i].lowcost;
    k = i;
    for(j = i+1; j< G.vexnum; j++)
    {
        if(SZ[j].lowcost > 0 && min > SZ[j].lowcost)//忽略lowcost为0的元素
        {
            min = SZ[j].lowcost;
            k = j;
        }
    }
    return k;
}
void MiniSpanTree_PRIM(Graph G,char u)
{
    minside closedge;//辅助数组
    int i,j,k;
    k = LocateVex(G,u);
    if(k==-1)
    {
        return;
    }
    //初始化辅助数组
    for(i = 0; i < G.vexnum; i++)
    {
        if(k != i)
        {
            closedge[i].adjvex = u;//复制顶点
            closedge[i].lowcost = G.arcs[k][i].adj;//复制权
        }
    }
    closedge[k].lowcost = 0;//初始,将第k顶点纳入U集
    cout<<"最小代价生成树的各条边为:\n";
    for(i = 1; i < G.vexnum; i++)//n个顶点的图的最小生成树有n-1条边
    {
        k = mininum(closedge,G);
        cout<<closedge[k].adjvex<<"--->"<<G.vexs[k]<<endl;//输出生成树的边

        closedge[k].lowcost = 0;//第k顶点并入U集

        //更新辅助数组
        for(j = 0; j < G.vexnum; j++)
        {
            if(closedge[j].lowcost > G.arcs[k][j].adj)
            {
                closedge[j].adjvex = G.vexs[k];//更新顶点名
                closedge[j].lowcost = G.arcs[k][j].adj;//更新权
            }
        }
    }
    cout<<endl;
}

//---------------------------------------------------------
int main()
{
    Graph g;
    CreateAN(&g);
    Display(g);
    MiniSpanTree_PRIM(g,'a');
    return 0;
}

测试:

最小生成树之Prim算法,布布扣,bubuko.com

时间: 07-01

最小生成树之Prim算法的相关文章

最小生成树(prim算法,Kruskal算法)c++实现

1.生成树的概念 连通图G的一个子图如果是一棵包含G的所有顶点的树,则该子图称为G的生成树. 生成树是连通图的极小连通子图.所谓极小是指:若在树中任意增加一条边,则将出现一个回路:若去掉一条边,将会使之变成非连通图. 生成树各边的权值总和称为生成树的权.权最小的生成树称为最小生成树. 2.最小生成树的性质用哲学的观点来说,每个事物都有自己特有的性质,那么图的最小生成树也是不例外的.按照生成树的定义,n 个顶点的连通网络的生成树有 n 个顶点.n-1 条边. 3.构造最小生成树,要解决以下两个问题

hihoCoder #1097 最小生成树之Prim算法

原题网址,http://hihocoder.com/problemset/problem/1097 #1097 : 最小生成树一·Prim算法 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 最近,小Hi很喜欢玩的一款游戏模拟城市开放出了新Mod,在这个Mod中,玩家可以拥有不止一个城市了! 但 是,问题也接踵而来——小Hi现在手上拥有N座城市,且已知这N座城市中任意两座城市之间建造道路所需要的费用,小Hi希望知道,最少花费多少就 可以使得任意两座城市都可以通过所建

Hihocoder 之 #1097 : 最小生成树一&#183;Prim算法 (用vector二维 模拟邻接表,进行prim()生成树算法, *【模板】)

#1097 : 最小生成树一·Prim算法 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 最近,小Hi很喜欢玩的一款游戏模拟城市开放出了新Mod,在这个Mod中,玩家可以拥有不止一个城市了! 但是,问题也接踵而来——小Hi现在手上拥有N座城市,且已知这N座城市中任意两座城市之间建造道路所需要的费用,小Hi希望知道,最少花费多少就可以使得任意两座城市都可以通过所建造的道路互相到达(假设有A.B.C三座城市,只需要在AB之间和BC之间建造道路,那么AC之间也是可以通过

hihoCoder - hiho一下 第二十六周 - A - 最小生成树一&#183;Prim算法

题目1 : 最小生成树一·Prim算法 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 最近,小Hi很喜欢玩的一款游戏模拟城市开放出了新Mod,在这个Mod中,玩家可以拥有不止一个城市了! 但是,问题也接踵而来--小Hi现在手上拥有N座城市,且已知这N座城市中任意两座城市之间建造道路所需要的费用,小Hi希望知道,最少花费多少就可以使得任意两座城市都可以通过所建造的道路互相到达(假设有A.B.C三座城市,只需要在AB之间和BC之间建造道路,那么AC之间也是可以通过这两

hihocoder hiho一下 第二十六周 最小生成树一&#183;(Prim算法)

题目1 : 最小生成树一·Prim算法 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 最近,小Hi很喜欢玩的一款游戏模拟城市开放出了新Mod,在这个Mod中,玩家可以拥有不止一个城市了! 但是,问题也接踵而来——小Hi现在手上拥有N座城市,且已知这N座城市中任意两座城市之间建造道路所需要的费用,小Hi希望知道,最少花费多少就 可以使得任意两座城市都可以通过所建造的道路互相到达(假设有A.B.C三座城市,只需要在AB之间和BC之间建造道路,那么AC之间也是可以通过这

hiho一下 第二十六周---最小生成树一&#183;Prim算法

最小生成树一·Prim算法 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 最近,小Hi很喜欢玩的一款游戏模拟城市开放出了新Mod,在这个Mod中,玩家可以拥有不止一个城市了! 但是,问题也接踵而来--小Hi现在手上拥有N座城市,且已知这N座城市中任意两座城市之间建造道路所需要的费用,小Hi希望知道,最少花费多少就可以使得任意两座城市都可以通过所建造的道路互相到达(假设有A.B.C三座城市,只需要在AB之间和BC之间建造道路,那么AC之间也是可以通过这两条道路连通的

最小生成树的Prim算法

构造最小生成树的Prim算法 假设G=(V,E)为一连通网,其中V为网中所有顶点的集合,E为网中所有带权边的集合.设置两个新的集合U和T,其中集合U用于存放G的最小生成树的顶点,集合T用于存放G的最小生成树中的边.令集合U的初值为U={u0}(假设构造最小生成树时是从顶点u0出发),集合T的初值为T={}.Prim算法的思想是:在连通网中寻找一个顶点落入U集,另外一个顶点落入V-U集的这个顶点加入到U集中,然后继续寻找一顶点在U集而另一顶点在V-U集且权值最小的边放入T集;如果不断重复直到U=V

数据结构--图--最小生成树(Prim算法)

构造连通网的最小生成树,就是使生成树的边的权值之和最小化.常用的有Prim和Kruskal算法.先看Prim算法:假设N={V,{E}}是连通网,TE是N上最小生成树中边的集合.算法从U={u0}(uo属于V),TE={}开始,重复执行下述操作:在所有u属于U,v属于V-U的边(u,v)属于E中找到代价最小的一条边(u0,v0)并入集合TE,同时v0并入U,直至U=V为止.此时TE中必有n-1条边,T={V,{TE}}为N的最小生成树.为实现此算法,需另设一个辅助数组closedge,以记录从U

24最小生成树之Prim算法

最小生成树的Prim算法 思想:采用子树延伸法 将顶点分成两类: 生长点--已经在生成树上的顶点 非生长点--未长到生成树上的顶点 使用待选边表: 每个非生长点在待选边表中有一条待选边,一端连着非生长点,另一端连着生长点 步骤: 步骤1)构造初始待选边表,任选一个顶点v作为初始生长点,对其余每个非生长点w(共n-1个),将边(w,v)加进待选边表,如果边(w,v)不存在,则认为边(w,v)的长度是∞. 步骤2)循环n-2遍,非生长点个数k从n-1变到1. ①选择树边. 从待选边表中选出一条最短的