| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 684 人关注过本帖
标题: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
快速回复:Prim算法
数据加载中...
 
   



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

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