标题:Prim算法
只看楼主
迷上编程
Rank: 2
等 级:论坛游民
帖 子:140
专家分:86
注 册:2012-3-11
结帖率:83.33%
 问题点数:0 回复次数:1 
Prim算法
用Prim算法求其最小生成树的伪码?该怎么写!!!
搜索更多相关主题的帖子: 算法 
2012-06-21 10:21
qq267165295
Rank: 1
等 级:新手上路
帖 子:21
专家分:2
注 册:2012-1-6
得分:0 
typedef struct
{   
    int     **data;
    int     vertex_num;
    int     edge_num;
} Graph;
//data指向存储数据的存储空间,vertex_num指示顶点的数量,edge_num指示边的数量。



//基于临接矩阵表示的图的Prim算法实现
void Prim(Graph g,int v)
{
    int *flag;
    int i,m,n,min,temp_m,temp_n;

    flag = new int[g.vertex_num];
    memset(flag,0,sizeof(int)*g.vertex_num);

    flag[v]=1;                                    //把顶点v放入集合U
    for(i=0;i<g.vertex_num-1;i++)
    {
        min=INFINITY;
        for(m=0;m<g.vertex_num;m++)
            for(n=0;n<g.vertex_num;n++)
                if((flag[m]+flag[n])==1 && g.data[m][n]<min) // flag[m]+flag[n])==1表示
                {
                    min= g.data[m][n]; //两个顶点中只有一个在集合U中
                    temp_m = m;
                    temp_n = n;
                }
        cout<<temp_m<<"──"<<temp_n<<endl;
        g.data[temp_m][temp_n]=INFINITY;   //不再考虑此边
        flag[temp_m]=1;
        flag[temp_n]=1;
    }

    delete []flag;
}
2012-09-04 09:34



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-371990-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 1.760006 second(s), 8 queries.
Copyright©2004-2025, BCCN.NET, All Rights Reserved