必威体育Betway必威体育官网
当前位置:首页 > IT技术

克鲁斯卡尔算法与普里姆算法详解

时间:2019-11-03 06:14:27来源:IT技术作者:seo实验室小编阅读:90次「手机版」
 

克鲁斯卡尔算法

最近数据结构老师讲了好几个算法,今晚上正好有空,所以就来整理一下

一:Kruskal算法思想:直接以边为目标去构建最小生成树,注意只找出n-1条边即可,并且不能形成回路。图的存储结构采用的是边集数组,且权值相等的边在数组中的排练次序是任意的,如果图中的边数较多则此算法会很浪费时间!

二:Prim算法思想:以某一顶点为起点,一点一点的去找各顶点上最小权值的边来构建最小生成树。图的存储结构是邻接矩阵,此方法需要一个顶点集合T,开始的时候为空集,慢慢的会将连通的顶点陆续的加入到集合中,全部顶点都加入集合以后,就得到我们所需要的最小生成树啦!

三:克鲁斯卡尔算法代码实现方法一:

#include "stdio.h"
#include "stdlib.h"
struct edge     
{
	int m;
	int n;
	int d;
}a[5010];      //克鲁斯卡尔算法采用边集数组来存储图

int cmp(const void *a,const void *b) //按升序排列,此过程也可以用快排来实现!
{
	return ((struct edge *)a)->d>((struct edge *)b)->d;
}

int main(void)
{
	int i,n,t,num,min,k,g,x[100];
	printf("请输入顶点的个数:");
	scanf("%d",&n);
	t=n*(n-1)/2;  //n个顶点的无向连通图共有n*(n-1)/2条边

	for(i=1;i<=n;i++)
		x[i]=i;

	printf("请输入每条边的起始端点、权值:/n");
	for(i=0;i<t;i++)
		scanf("%d %d %d",&a[i].m,&a[i].n,&a[i].d); //输入每条边的权值
	qsort(a,t,sizeof(a[0]),cmp);//此过程可以用快排,来将每条边权值从小到大排列起来

	min=num=0;
	for(i=0;i<t && num<n-1;i++)
	{
		for(k=a[i].m;x[k]!=k;k=x[k])  //判断线段的起始点所在的集合
			x[k]=x[x[k]];
		for(g=a[i].n;x[g]!=g;g=x[g])  //判断线段的终点所在的集合
			x[g]=x[x[g]];

		if(k!=g)  //如果线段的两个端点所在的集合不一样
		{
			x[g]=k;
			min+=a[i].d;
			num++;
			printf("最小生成树中加入边:%d %d/n",a[i].m,a[i].n);
		}
	}
	printf("最小生成树的权值为:%d/n",min);
	system("pause");
	return 0;
}

克鲁斯卡尔算法代码实现方法二:

typedef struct          
{        
    char vertex[VertexNum];                                //顶点表         
    int edges[VertexNum][VertexNum];                       //邻接矩阵,可看做边表         
    int n,e;                                               //图中当前的顶点数和边数         
}MGraph; 
 
typedef struct node  
{  
    int u;                                                 //边的起始顶点   
    int v;                                                 //边的终止顶点   
    int w;                                                 //边的权值   
}Edge; 

void kruskal(MGraph G)  
{  
    int i,j,u1,v1,sn1,sn2,k;  
    int vset[VertexNum];                                    //辅助数组,判定两个顶点是否连通   
    int E[EdgeNum];                                         //存放所有的边   
    k=0;                                                    //E数组的下标从0开始   
    for (i=0;i<G.n;i++)  
    {  
        for (j=0;j<G.n;j++)  
        {  
            if (G.edges[i][j]!=0 && G.edges[i][j]!=INF)  
            {  
                E[k].u=i;  
                E[k].v=j;  
                E[k].w=G.edges[i][j];  
                k++;  
            }  
        }  
    }     
    heapsort(E,k,sizeof(E[0]));                            //堆排序,按权值从小到大排列       
    for (i=0;i<G.n;i++)                                    //初始化辅助数组   
    {  
        vset[i]=i;  
    }  
    k=1;                                                   //生成的边数,最后要刚好为总边数   
    j=0;                                                   //E中的下标   
    while (k<G.n)  
    {   
        sn1=vset[E[j].u];  
        sn2=vset[E[j].v];                                  //得到两顶点属于的集合编号   
        if (sn1!=sn2)                                      //不在同一集合编号内的话,把边加入最小生成树   
        {
            printf("%d ---> %d, %d",E[j].u,E[j].v,E[j].w);       
            k++;  
            for (i=0;i<G.n;i++)  
            {  
                if (vset[i]==sn2)  
                {  
                    vset[i]=sn1;  
                }  
            }             
        }  
        j++;  
    }  
}  

四:Prim算法具体实现

#define MAX  100000
#define VNUM  10+1                                             //这里没有ID为0的点,so id号范围1~10

int edge[VNUM][VNUM]={/*输入的邻接矩阵*/};
int lowcost[VNUM]={0};                                         //记录Vnew中每个点到V中邻接点的最短边
int addvnew[VNUM];                                             //标记某点是否加入Vnew
int adjecent[VNUM]={0};                                        //记录V中与Vnew最邻近的点


void prim(int start)
{
     int sumweight=0;
     int i,j,k=0;

     for(i=1;i<VNUM;i++)                                      //顶点是从1开始
     {
        lowcost[i]=edge[start][i];
        addvnew[i]=-1;                                         //将所有点至于Vnew之外,V之内,这里只要对应的为-1,就表示在Vnew之外
     }

     addvnew[start]=0;                                        //将起始点start加入Vnew
     adjecent[start]=start;
                                                 
     for(i=1;i<VNUM-1;i++)                                        
     {
        int min=MAX;
        int v=-1;
        for(j=1;j<VNUM;j++)                                      
        {
            if(addvnew[j]!=-1&&lowcost[j]<min)                 //在Vnew之外寻找最短路径
            {
                min=lowcost[j];
                v=j;
            }
        }
        if(v!=-1)
        {
            printf("%d %d %d\n",adjecent[v],v,lowcost[v]);
            addvnew[v]=0;                                      //将v加Vnew中

            sumweight+=lowcost[v];                             //计算路径长度之和
            for(j=1;j<VNUM;j++)
            {
                if(addvnew[j]==-1&&edge[v][j]<lowcost[j])      
                {
                    lowcost[j]=edge[v][j];                     //此时v点加入Vnew 需要更新lowcost
                    adjecent[j]=v;                             
                }
            }
        }
    }
    printf("the minmum weight is %d",sumweight);
}

五:如果大家觉得这篇博客有问题,欢迎提意见,博主会认真学习哒~

文章最后发布于: 2018-11-28 20:22:07

相关阅读

产品经理职业生涯规划&#038;每个阶段的弯道超越算法

文章主要与大家分享一些关于产品职业生涯中的一些底层认知,希望对你有所帮助~之前的两篇文章《基于Axure的移动端APP产品设计规范

机器学习 | 贝叶斯算法及应用

朴素贝叶斯是基于“特征之间是独立的”这一朴素假设,应用贝叶斯定理的监督学习算法。基于条件概率的贝叶斯定律数学公式朴素贝叶斯

函数奇偶性运算法则,以及复合函数奇偶性判断

下面给你它们四则运算的规律:1奇函数+奇函数=奇函数2奇函数+偶函数=非奇非偶函数(特殊的可能是别的结果,不过特殊时可以用定义判断

KMP算法中next数组、nextval数组的手工计算

刚接触数据结构,对于其中的一些算法都不是很了解,这几天刚在学习串的内容,里面介绍了两种串的模式匹配算法,一种是BF算法(也叫做BoyFri

严惩网站网页标题作弊!百度9月底将推清风算法

A5创业网(admin5.com)9月14日消息,百度站长平台今日发布一则消息称,为保证用户搜索体验、促进搜索生态的良性发展,百度搜索将于9月底

分享到:

栏目导航

推荐阅读

热门阅读