精华内容
下载资源
问答
  • 最小生成树——Prim算法和Kruscal算法

    千次阅读 2018-04-29 22:21:25
    对于一个带权连通无向图G的不同生成树,各棵树的边上的权值之可能不同,边上的权值之最小的树称为该图的最小生成树。2、最小生成树的应用 比如要在n个城市之间铺设光缆,主要目标是要使这 n 个城市的任意两个...

    1、最小生成树的定义

            一个连通图的生成树是该连通图的一个极小连通子图,它含有图中全部顶点,但只构成一棵树的(n-1)条边。对于一个带权连通无向图G的不同生成树,各棵树的边上的权值之和可能不同,边上的权值之和最小的树称为该图的最小生成树。

    2、最小生成树的应用

            比如要在n个城市之间铺设光缆,主要目标是要使这 n 个城市的任意两个之间都可以通信,但铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

    3、最小生成树的构造算法

            图的邻接矩阵类型定义如下:

    #define N 100
    
    typedef char ElemType;
    
    //adjacency matrix graph
    typedef struct MGraph
    {
    	ElemType vertexes[N];
    	int edges[N][N];
    	int n;
    }MGraph;

    (1)普里姆(Prim)算法

            Prim算法的核心思想是,从一个顶点开始,加入顶点集合,将顶点集合中所有顶点到其他顶点的边作为候选边,每次从候选边中挑选最小权值的边作为生成树的边,然后更新候选边,直到图的所有顶点都被加入为止。其步骤如下:

            ①初始化顶点集合为传入的那个顶点,初始化候选边为该顶点到其他顶点的所有边

            ②重复步骤③,直到图中所有顶点都被加入为止

            ③从候选边中挑选最小权值的边作为生成树的边,此时因为加入了新的顶点,所以需要更新候选边

            代码实现:

    void Prim(MGraph& g, int k)
    {
    	int* w = new int[g.n]; //the least edge weight
    	int* v = new int[g.n]; //vertexes of the least weight
    	for (int i = 0; i < g.n; i++)
    	{
    		w[i] = g.edges[k][i];
    		v[i] = k;
    	}
    	w[k] = 0;
    	for (int cnt = 1; cnt < g.n; cnt++)
    	{
    		//find the min val of w
    		int imin = -1;
    		for (int i = 0; i < g.n; i++)
    		{
    			if (w[i] != 0 && (imin == -1 || w[i] < w[imin]))
    				imin = i;
    		}
    		//print
    		cout << "(" << g.vertexes[v[imin]] << "," << g.vertexes[imin] << ")";
    		//update the least weight
    		w[imin] = 0; 
    		for (int i = 0; i < g.n; i++)
    		{
    			if (g.edges[imin][i] != 0 && g.edges[imin][i] < w[i])
    			{
    				w[i] = g.edges[imin][i];
    				v[i] = imin;
    			}
    		}
    	}
    	delete[] w, v;
    }

            Prim算法包含两重for循环,其时间复杂度为O(n²)。

    (2)克鲁斯卡尔(Kruscal)算法

            Kruscal算法的基本思想是,将图的所有边按权值递增的顺序进行排序,然后每次依次从小到大选择一条边加入到生成树中,但加入的前提是加入这条边后不会构成回路。其步骤如下:

            ①将图的所有边按权值递增的顺序进行排序

            ②重复步骤③,直到图中所有顶点都被加入为止

            ③按照从小到大的顺序选择一条边,如果这条边未使生成树形成回路,就把这条边加入到生成树中

            代码实现如下:

    void Kruscal(MGraph& g)
    {
    	//define the Edge
    	typedef struct Edge
    	{
    		int u, v;
    		int w;
    		Edge(int _u, int _v, int _w) :u(_u), v(_v), w(_w) {}
    	}Edge;
    	//init the edges
    	vector<Edge> v;
    	for (int i = 0; i < g.n; i++)
    	{
    		for (int j = 0; j < g.n; j++)
    		{
    			auto w = g.edges[i][j];
    			if (w != INT16_MAX && w != 0)
    				v.push_back(Edge(i, j, w));
    		}
    	}
    	//sort by weight increment
    	sort(v.begin(), v.end(), [](Edge u, Edge v)->int {
    		return u.w < v.w;
    	});
    	//add all edges if it does not constitute a loop
    	int* set = new int[g.n];
    	for (int i = 0; i < g.n; i++)
    		set[i] = i;
    	vector<Edge>::iterator iter = v.begin();
    	for (int cnt = 0; cnt < g.n - 1; )
    	{
    		if (set[iter->u] != set[iter->v])
    		{
    			cout << "(" << g.vertexes[iter->u] << "," << g.vertexes[iter->v] << ")";
    			cnt++;
    			for (int i = 0; i < g.n; i++)
    			{
    				if (set[i] == set[iter->v])
    					set[i] = set[iter->u];
    			}
    		}
    		iter++;
    	}
    	delete[] set;
    }

            Kruscal算法同样包含两重for循环,其时间复杂度为O(n²),但可以对Kruscal算法做两方面的优化,一是将边集排序改为堆排序,二是用并查集来判断新加入边是否构成回路,优化后Kruscal算法的时间复杂度为O(elog₂e),e为图的所有边。

    4、测试

    求出给定无向带权图的最小生成树。图的定点为字符型,权值为不超过100的整形。

    输入

    第一行为图的顶点个数n
    第二行为图的边的条数e
    接着e行为依附于一条边的两个顶点和边上的权值

    输出

    最小生成树中的边。

    样例输入

    6
    10
    ABCDEF
    A B 6
    A C 1
    A D 5
    B C 5
    C D 5
    B E 3
    E C 6
    C F 4
    F D 2
    E F 6

    样例输出

    (A,C)(C,F)(F,D)(C,B)(B,E)
    (A,C)(D,F)(B,E)(C,F)(B,C)

    代码如下:

    #include <iostream>
    #include <map>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    #define N 100
    
    typedef char ElemType;
    
    //adjacency matrix graph
    typedef struct MGraph
    {
    	ElemType vertexes[N];
    	int edges[N][N];
    	int n;
    }MGraph;
    
    void Prim(MGraph& g, int k)
    {
    	int* w = new int[g.n]; //the least edge weight
    	int* v = new int[g.n]; //vertexes of the least weight
    	for (int i = 0; i < g.n; i++)
    	{
    		w[i] = g.edges[k][i];
    		v[i] = k;
    	}
    	w[k] = 0;
    	for (int cnt = 1; cnt < g.n; cnt++)
    	{
    		//find the min val of w
    		int imin = -1;
    		for (int i = 0; i < g.n; i++)
    		{
    			if (w[i] != 0 && (imin == -1 || w[i] < w[imin]))
    				imin = i;
    		}
    		//print
    		cout << "(" << g.vertexes[v[imin]] << "," << g.vertexes[imin] << ")";
    		//update the least weight
    		w[imin] = 0; 
    		for (int i = 0; i < g.n; i++)
    		{
    			if (g.edges[imin][i] != 0 && g.edges[imin][i] < w[i])
    			{
    				w[i] = g.edges[imin][i];
    				v[i] = imin;
    			}
    		}
    	}
    	delete[] w, v;
    }
    
    void Kruscal(MGraph& g)
    {
    	//define the Edge
    	typedef struct Edge
    	{
    		int u, v;
    		int w;
    		Edge(int _u, int _v, int _w) :u(_u), v(_v), w(_w) {}
    	}Edge;
    	//init the edges
    	vector<Edge> v;
    	for (int i = 0; i < g.n; i++)
    	{
    		for (int j = 0; j < g.n; j++)
    		{
    			auto w = g.edges[i][j];
    			if (w != INT16_MAX && w != 0)
    				v.push_back(Edge(i, j, w));
    		}
    	}
    	//sort by weight increment
    	sort(v.begin(), v.end(), [](Edge u, Edge v)->int {
    		return u.w < v.w;
    	});
    	//add all edges if it does not constitute a loop
    	int* set = new int[g.n];
    	for (int i = 0; i < g.n; i++)
    		set[i] = i;
    	vector<Edge>::iterator iter = v.begin();
    	for (int cnt = 0; cnt < g.n - 1; )
    	{
    		if (set[iter->u] != set[iter->v])
    		{
    			cout << "(" << g.vertexes[iter->u] << "," << g.vertexes[iter->v] << ")";
    			cnt++;
    			for (int i = 0; i < g.n; i++)
    			{
    				if (set[i] == set[iter->v])
    					set[i] = set[iter->u];
    			}
    		}
    		iter++;
    	}
    	delete[] set;
    }
    
    int main()
    {
    	MGraph g;
    	while(cin >> g.n)
    	{
    		//input
    		int e;
    		cin >> e;
    		map<char, int> m;
    		for (int i = 0; i < g.n; i++)
    		{
    			cin >> g.vertexes[i];
    			m[g.vertexes[i]] = i;
    		}
    		for (int i = 0; i < g.n; i++)
    			for (int j = 0; j < g.n; j++)
    				g.edges[i][j] = INT16_MAX;
    		
    		char u, v;
    		int w;
    		for (int cnt = 0; cnt < e; cnt++)
    		{
    			cin >> u >> v >> w;
    			g.edges[m[u]][m[v]] = g.edges[m[v]][m[u]] = w;
    		}
    		//excute
    		Prim(g, 0); cout << endl; //Prim algorithm
    		Kruscal(g); cout << endl; //Kruscal algorithm
    	}
    	return 0;
    }

    参考文献

    [1] 李春葆.数据结构教程.清华大学出版社,2013.

    [2] 最小生成树.百度百科[引用日期2018-04-29].
    展开全文
  • 1.Prim算法(选点) 思想:①设置一个点集合V,表示最小生成树中已经确定的点的集合;设置一个边集合U,表示最小生成树中已经确定的边的集合;(UV是对应起来的), ②在V中点,剩余点中找权值最小的边,将边...

    1.Prim算法(选点)

    思想:①设置一个点集合V,表示最小生成树中已经确定的点的集合;设置一个边集合U,表示最小生成树中已经确定的边的集合;(U和V是对应起来的),
    ②在V中点,和剩余点中找权值最小的边,将边并入U,对应的另一个端点并入V.(注意在找边的时候避免和原来的边产生环)
    ③重复步骤②,直到V中的顶点为所有的顶点,U中的边则为最小生成树上的边。
    时间复杂度O(n^2),适用于点少的图
    例如:下图
    在这里插入图片描述
    先找{1}和{2,3,4,5,6}中权最小的边为(1,3)
    再找{1,3}和{2,4,5,6}中权最小的边为(3,6)
    ······
    代码:

    #include<stdio.h>
    #define MAX_VERTEX_NUM 100
    #define MAX 1e10
    typedef struct{
    	int vexs[MAX_VERTEX_NUM];
    	int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    	int vexnum,arcnum;
    }MGraph;
    struct{
    	int adjvex;
    	int lowcost;
    }closedge[MAX_VERTEX_NUM];
    bool inU[MAX_VERTEX_NUM]; //如果值为1表示vex【i】顶点在U中
    int LocateVex(MGraph G,int v){//返回顶点在图中的位置
    	for(int i=0;i<G.vexnum;i++){
    		if(G.vexs[i]==v)return i;
    	}
    }
    void CreateUDN(MGraph &G){//构造无向网的邻接矩阵
    	int i,j,k,v1,v2,weight;
    	printf("分别输入顶点个数和边的个数:\n");
    	scanf("%d%d",&G.vexnum,&G.arcnum);
    	printf("输入各个顶点:\n");
    	for(i=0;i<G.vexnum;i++)
    	scanf("%d",&G.vexs[i]);
    
    	for(i=0;i<G.vexnum;i++)
    	 for(j=0;j<G.vexnum;j++)
    	  G.arcs[i][j]=MAX;//初始化图,如果两点不通则把值赋为MAX
    
    	printf("分别输入各条边的两个顶点和边的权值:\n");
    	for(k=0;k<G.arcnum;k++){
    		scanf("%d%d%d",&v1,&v2,&weight);
    		i=LocateVex(G,v1);j=LocateVex(G,v2);
    		G.arcs[i][j]=weight;
    		G.arcs[j][i]=weight;
    	}
    }
    int minmum(MGraph G){//返回low_cost最小的
    	int min_cost=MAX;
    	int temp;
    	for(int i=0;i<G.vexnum;i++)
    		if(closedge[i].lowcost<min_cost&&closedge[i].lowcost!=0&&inU[LocateVex(G,closedge[i].adjvex)]){
    			min_cost=closedge[i].lowcost;temp=i;
    		}
    	return temp;
    }
    void MiniSpanTree_PRIM(MGraph G,int u){//找到最小生成树的边并输出
    	int i,j,k;
    	k=LocateVex(G,u);
    	inU[k]=1;// 表示把vex[k]加入到U集合中
    	for(j=0;j<G.vexnum;j++)//初始化,即有一个顶点时U集 到V-U集的最小权值
    	if(j!=k){
    		closedge[j].adjvex=u;
    		closedge[j].lowcost=G.arcs[k][j];
    	}
    	closedge[k].lowcost=0;
    	printf("最小生成树的边为:\n");
    	for(i=1;i<G.vexnum;i++){//U集总共还要加入vexnum-1个顶点
    		k=minmum(G);//当前U到 V-U集最小的一个权值为closedge[k].lowcost
    		inU[k]=1; //将vex[k]加入U集合
    	printf("%d %d\n",closedge[k].adjvex,G.vexs[k]);
    	closedge[k].lowcost=0;
    	for(j=0;j<G.vexnum;j++){//当有新的顶点加入U集时,每个顶点到V-U集的lowcost都要重新赋值
    		if(G.arcs[k][j]<closedge[j].lowcost)//如果新的顶点到j的权值小与未加入新顶点之前的lowcost,则重新赋值
    		{closedge[j].adjvex=G.vexs[k];
    		closedge[j].lowcost=G.arcs[k][j];}
    	}
    	}
    }
    int main(){
    	MGraph G;
    	CreateUDN(G);
    	int u;//最小生成树的起点为u
    	printf("输入生成树的出发点:\n");
    	scanf("%d",&u);
    	MiniSpanTree_PRIM(G,u);
    	return 0;
    }
    
    

    2.Kruskal(选边)

    思想:
    从原图中依次选择权值最小且不与已选的边构成环的边,直到所有顶点都连通
    时间复杂度:O( e * loge )
    适合于求边稀疏的网的最小生成树
    代码

    /* 最小生成树的Kruskal算法 */
     
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
     
    #define MaxSize 20
     
    typedef char VertexType;
     
    typedef struct Graph {		//定义图的邻接矩阵表示法结构
    	VertexType ver[MaxSize+1];
    	int edg[MaxSize][MaxSize];
    }Graph;
     
    typedef struct gEdge {		//定义一个边集结构,用来存储图的所有边信息
    	int begin;
    	int end;
    	int weight;
    }gEdge;
     
    void CreateGraph( Graph *g )		//邻接矩阵法图的生成函数
    {
    	int i = 0;
    	int j = 0;
    	int VertexNum;
    	VertexType Ver;
     
    	printf("请输入图的顶点:\n");
    	while( '\n' != (Ver=getchar()) ) {
    		g->ver[i++] = Ver;
    	}
    	g->ver[i] = '\0';
     
    	VertexNum = strlen(g->ver);
    	printf("请输入相应的的邻接矩阵:\n");
    	for( i=0; i<VertexNum; i++ )
    		for( j=0; j<VertexNum; j++ ) 
    			scanf("%d", &g->edg[i][j]);
    }
     
    void PrintGraph( Graph g )		//打印图的结点标识符和邻接矩阵
    {
    	int i, j;
    	int VertexNum = strlen(g.ver);
    	printf("图的顶点为:\n");
    	for( i=0; i<VertexNum; i++ )
    		printf("%c ", g.ver[i]);
    	printf("\n");
     
    	printf("图的邻接矩阵为:\n");
    	for( i=0; i<VertexNum; i++ ) {
    		for( j=0; j<VertexNum; j++ )
    			printf("%d ", g.edg[i][j]);
    		printf("\n");
    	}
    }
     
    int CalVerNum( Graph g )		//求图的顶点数
    {
    	return strlen(g.ver);
    }
     
    int CalEdgNum( Graph g )		//获取图的边数
    {
    	Graph p = g;
    	int count = 0;
    	int VertexNum = CalVerNum( p );
    	for( int i=0; i<VertexNum; i++ )
    		for( int j=i; j<VertexNum; j++ )		//邻接矩阵对称,计算上三角元素和即可
    			if( 0 != p.edg[i][j] )
    				count++;
    	return count;
    }
     
    gEdge *CreateEdges( Graph g )					//生成图的排序过的边集数组
    {
    	int i, j;
    	int k = 0;
    	int EdgNum = CalEdgNum( g );
    	int VertexNum = CalVerNum( g );
    	gEdge temp;
    	gEdge *p = (gEdge *)malloc(sizeof(gEdge)*EdgNum);	
     
    	for( i=0; i<VertexNum; i++ )				//边集数组初始化,同样只考虑上三角矩阵
    		for( j=i; j<VertexNum; j++ )
    			if( 0 != g.edg[i][j] ) {
    				p[k].begin = i;
    				p[k].end = j;
    				p[k].weight = g.edg[i][j];
    				k++;
    			}
    	
    	for( i=0; i<EdgNum-1; i++ )		        	//对边集数组进行选择排序
    		for( j=i+1; j<EdgNum; j++ )
    			if( p[i].weight > p[j].weight ) {
    				temp = p[i];
    				p[i] = p[j];
    				p[j] = temp;
    			}
     
    	return p;
    }
     
    //Kruskal算法生成MST
    void Kruskal( Graph g )
    {
    	int VertexNum = CalVerNum( g );
    	int EdgNum = CalEdgNum( g );
    	gEdge *p = CreateEdges( g );
    	int *index = (int *)malloc(sizeof(int)*VertexNum);		    
    	//index数组,其元素为连通分量的编号,index[i] = index[j] 表示编号为i 和 j的顶点在同一个连通分量中,反之则不在同一个连通分量
    	int *MSTEdge = (int *)malloc(sizeof(int)*VertexNum-1);		//MSTEdge数组,用来存储已确定的MST的边的编号,共VertexNum-1条边
    	int k= 0;
    	int WeightSum = 0;
    	int IndexBegin, IndexEnd;
     
    	for(int i=0; i<VertexNum; i++ )		//初始化所有index = -1
    		index[i] = -1;
     
    	for( i=0; i<VertexNum-1; i++ ) {
    		for(int j=0; j<EdgNum; j++ ) {
    			if( !(index[p[j].begin]>=0 && index[p[j].end]>=0 && index[p[j].begin]==index[p[j].end]) ) {  //找到当前还没加入到同一个连通分量且权值最下的边
    				MSTEdge[i] = j;		//将其加入到MST中去
     
    				if( (-1 == index[p[j].begin]) && (-1 == index[p[j].end]) )			//该边的两个顶点都没加入过任何一个连通分量
    					index[p[j].begin] = index[p[j].end] = i;	
     
    				else if( (-1 == index[p[j].begin]) && (index[p[j].end] >= 0) ) {	//该边的尾end已在一个连通分量,头begin未加入过任何连通分量
    					index[p[j].begin] = i;
    					IndexEnd = index[p[j].end];
    					for(int n=0; n<VertexNum; n++ )
    						if( index[n] == IndexEnd )
    							index[n] = i;
    				}
     
    				else if( (-1 == index[p[j].end]) && (index[p[j].begin] >= 0) ) {	//该边的头begin已在一个连通分量,尾end未加入过任何连通分量
    					index[p[j].end] = i;
    					IndexBegin = index[p[j].begin];
    					for(int n=0; n<VertexNum; n++ )
    						if( index[n] == IndexBegin )
    							index[n] = i;
    				}
     
    				else {
    					IndexEnd = index[p[j].end];
    					IndexBegin = index[p[j].begin];
    					for(int n=0; n<VertexNum; n++ )								//该边的两个顶点都已经存在于两个不同的连通分量中
    						if( index[n] == IndexBegin || index[n] == IndexEnd )
    							index[n] = i;										//将该连通分量编号全部修改为相同的值
    				}
    				break;
    			}
    		}
    	}
     
    	printf("MST的边为:\n");				//输出MST的边
    	for( i=0; i<VertexNum-1; i++ ) {
    		printf("%c--%c\n", g.ver [p[MSTEdge[i]].begin] , g.ver [p[MSTEdge[i]].end] );
    		WeightSum+=p[MSTEdge[i]].weight;
    	}
    	printf("MST的权值为:%d\n", WeightSum);		//输出MST的权值
    }
     
    int main()
    {
    	Graph g;
    	CreateGraph( &g );
    	PrintGraph( g );
    	Kruskal( g );
    	return 0;
    }
    
    
    展开全文
  • 最小支撑树:prim算法。以点找最短边。 时间复杂度为O(n^2) #include<iostream> #define inf 35535 using namespace std; typedef struct graph { int vn, en; int **arr; }Graph; bool isfull(bool *s,...

    最小支撑树:prim算法。以点找最短边。 时间复杂度为O(n^2)

    #include<iostream>
    #define inf 35535
    using namespace std;
    typedef struct graph
    {
    	int vn, en;
    	int **arr;
    }Graph;
    bool isfull(bool *s, int n)
    {
    	for (int i = 1; i <= n; i++)
    		if (!s[i])
    			return 0;
    	return 1;
    }
    
    void prim(Graph g)
    {
    	int *closest = new int[g.vn + 1];//closest是lowcost中每对最短路径长度的顶点对
    	int *lowcost = new int[g.vn + 1];//lowcost是记录每个顶点与其他顶点的最短路径长度
    	bool *s = new bool[g.vn + 1];//顶点集合
    	for (int i = 1; i <= g.vn; i++)
    	{
    		lowcost[i] = g.arr[1][i];//以顶点1为源点
    		closest[i] = 1;
    		s[i] = 0;
    	}
    	s[1] = 1;
    	while (!isfull(s,g.vn))
    	{
    		int j = 1;
    		int min = inf;
    		for (int i = 2; i <= g.vn; i++)
    		{
    			if (lowcost[i] < min && !s[i])
    			{
    				min = lowcost[i];
    				j = i;
    			}
    			
    		}
    		s[j] = 1;
    		for (int k = 2; k <= g.vn; k++)
    			if (g.arr[j][k] < lowcost[k] && !s[k])
    			{
    				lowcost[k] = g.arr[j][k];
    				closest[k] = j;
    			}
    	}
    	for (int i = 2; i <= g.vn; i++)
    		cout << i << " <-> " << closest[i] << endl;
    	
    }
    int main()
    {
    	int arr[6][6] = {
    		{inf,6,1,5,inf,inf},
    	{6,inf,5,inf,3},
    	{1,5,5,inf,6,4},
    	{5,inf,5,inf,inf,2},
    	{inf,3,6,inf,inf,6},
    	{inf,inf,4,2,6,inf}
    	};
    	Graph g;
    	g.vn = 6;
    	g.arr = new int*[g.vn + 1];
    	for (int i = 1; i <= g.vn; i++)
    		g.arr[i] = new int[g.vn + 1];
    	for (int i = 0; i < g.vn; i++)
    		for (int j = 0; j < g.vn; j++)
    			g.arr[i + 1][j + 1] = arr[i][j];
    	prim(g);
    	system("pause");
    	return 0;
    }

    prim如下图:

    kruskal算法:以边找点,时间复杂度为o(eloge);

    #include<iostream>
    #define  inf   65534
    #define max 128
    using namespace std;
    typedef struct graph
    {
    	int vn;
    	int en;
    	int **arr;
    }Graph;
    typedef struct Edge
    {
    	int u,  v,  w;
    }edge;
    
    Graph *graphinit(int arr[][6], int n)
    {
    	Graph *g = new Graph;
    	g->vn = n;
    	g->arr = new int*[n + 1];
    	for (int i = 1; i <= g->vn; i++)
    		g->arr[i] = new int[n+1];
    	for (int i = 0; i < n; i++)
    		for (int j = 0; j < n; j++)
    			g->arr[i+1][j+1] = arr[i][j];
    	return g;
    }
    edge EDGE(int i, int j, int w)
    {
    	edge e;
    	e.u = i;
    	e.v = j;
    	e.w = w;
    	return e;
    }
    int edges(edge arr[], Graph *g)
    {
    	int k = 0;
    	for (int i = 1; i <= g->vn; i++)
    		for (int j = i + 1; j <= g->vn; j++)
    			if (g->arr[i][j] !=inf )
    				arr[k++] = EDGE(i, j, g->arr[i][j]);
    	return k;
    				
    }
    void bubble(edge arr[], int n)
    {
    	for(int i=n-1;i>=1;i--)
    		for(int j=0;j<i;j++)
    			if (arr[j].w > arr[j + 1].w)
    			{
    				edge temp = arr[j];
    				arr[j] = arr[j + 1];
    				arr[j + 1] = temp;
    			}
    }
    typedef struct UFS
    {
    	int n;
    	int *parent,*root;
    }UFS;
    UFS *UfsInit(int n)
    {
    	UFS *s = new UFS;
    	s->parent = new int[n + 1];
    	s->root = new int[n + 1];
    	s->n = n;
    	for (int i = 1; i <= n; i++)
    	{
    		s->parent[i] = 1;
    		s->root[i] = 1;
    	}
    	return s;
    }
    int UFSfind(int e, UFS *s)
    {
    	int i, j = e;
    	while (!s->root[j]) j = s->parent[j];
    	while (e != j)
    	{
    		i = s->parent[e];
    		s->parent[e] = j;
    		e = i;
    	}
    	return j;
    }
    void UFSunion(int i, int j, UFS *s)
    {
    	int p = UFSfind(i, s);
    	int q = UFSfind(j, s);
    	if (p == q)
    		return;
    	else
    	{
    		if (s->parent[p] >= s->parent[q])
    		{
    			s->parent[p] += s->parent[q];
    			s->parent[q] = p;
    			s->root[q] = 0;
    		}
    		else
    		{
    			s->parent[q] += s->parent[p];
    			s->parent[p] = q;
    			s->root[p] = 0;
    		}
    	}
    }
    void print(edge arr[], int n)
    {
    	for (int i = 0; i < n; i++)
    		cout << arr[i].w << " ";
    	cout << endl;
    }
    void kruscal(Graph *g)
    {
    	int p, q, k = 0;
    	edge arr[max],mrk[max];
    	int e = edges(arr, g);
    	print(arr, e);
    	bubble(arr, e);
    	print(arr, e);
    	UFS *s = UfsInit(g->vn);
    	for (int i = 0; i < e; i++)
    	{
    		p = UFSfind(arr[i].u, s);
    		q = UFSfind(arr[i].v, s);
    		if (p != q)
    		{
    			mrk[k].u = arr[i].u;
    			mrk[k].v = arr[i].v;
    			mrk[k].w = arr[i].w;
    			k++;
    			UFSunion(p, q, s);
    		}
    	}
    	for (int i = 0; i < k; i++)
    		cout << mrk[i].u << " -> " << mrk[i].v << " : " << mrk[i].w << endl;
    	
    }
    int main()
    {
    	int arr[6][6] = {
    		{inf,6,1,5,inf,inf},
    	{6,inf,5,inf,3,inf},
    	{1,5,inf,5,6,4},
    	{5,inf,5,inf,inf,2},
    	{inf,3,6,inf,inf,6},
    	{inf,inf,4,2,6,inf}
    	};
    	Graph *g = graphinit(arr,6);
    	kruscal(g);
    	system("pause");
    	return 0;
    }

     

    展开全文
  • Prim算法的步骤如下: 假设G={V,E}是连通树,其最小生成树T=(U,Et),Et是最小生成树中 变得集合。 初始化:向空树T=(U,Et)中添加图G=(V,E)的任一顶点u0,使U={uo}, ET=空。 循环(重复下列操作直至U=V);从...
    #include<iostram> 
    using namespace std;
    /*
    		Prim算法的步骤如下:
    		假设G={V,E}是连通树,其最小生成树T=(U,Et),Et是最小生成树中
    		变得集合。
    		初始化:向空树T=(U,Et)中添加图G=(V,E)的任一顶点u0,使U={uo},
    		ET=空。
    		循环(重复下列操作直至U=V);从图G中选择满足{(u,v)u属于U, v属
    		于V - U}且具有最小权值的边(u.v),加入树T,置U归于{v},ET=ET归
    		于{(u,v)}。
    */
    
    /*		Prim算法的简单实现,用于求解边稠密的图的最小生成树 
    		其时间复杂度为O(|v|平方)		
    */ 
    void Prim(G,T) {
    	T  =;	//初始化空树
    	U = {w};	//添加在一顶点w
    	while((V-U) !=){		//若树中不含全部节点 (u,v)是使u属于U与v属于(V-U),且权值最小的边;
    		T =  T属于{(u,v)};		//边归入树
    		U = U属于{v};		//顶点归入树 
    	} 
    	 
    }
    
    /*
    		Kruskal算法的步骤如下:
       		假设G=(V,E)是连通图,其最小生成树T=(U, Er)。 .
    		初始化:U=V,ET=空。即每个顶点构成一棵独立的树,T此时是一个仅
    		含|V|个顶点的森林。
    		循环(重复下列操作直至T是一棵树):按G的边的权值递增颇序依
    		次从E-ET中选择一条边,若这条边加入T后不构成回路,则将其加
    		入ET,否则舍弃,直到E中含有n-1条边。
    				Kruskal算法适用于边稀疏而顶点较多的图 
    */
    
    void Kruskal(V,T){
    	T = V;		//初始化树T,仅含顶点
    	nums = n;		//连通分量数
    	while(nums > 1){		//若连通分 
    		从E中取出权值最小的边(v,u);
    		if(v中u属于T中不同的连通分量){
    			T = T属于{(v,u)};		//将此便加入生成树中
    			nums--;		//连通分量数减一 
    		} 
    	} 
    } 
    int main(){
    	return 0;
    }
    
    
    展开全文
  • Kruskal算法&Prim算法区别

    千次阅读 2021-11-17 10:52:06
    Prim算法区别: 贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。 贪心算法的特点是一步一步地进行,常以当前情况为基础根据某个优化测度作最优选择,而不考虑各种可能的整体情况,省去了为找最优...
  • Prim算法和Krusakl算法都是从连通图中寻找最小生成树的算法 Prim算法是直接查找,多次寻找邻边的权重最小值;Kruskal算法采用贪心策略,是需要先对权重排序后查找的。 Kruskal算法在效率上比Prim算法快,因为Krusal...
  • 邻接表prim算法

    2012-02-29 15:16:47
    用邻接表为存储结构的prim算法,程序中包括图的建立,图的深度优先遍历,最小生成树prim算法
  • 详细的c语言实现最小生成树的prim算法和kruskal算法,非常有用的
  • NULL 博文链接:https://128kj.iteye.com/blog/1705936
  • prim算法 //创建最小生成树->村庄的图 class MinTree { //创建图的邻接矩阵 /** * * @param graph 图对象 * @param verxs 图对应的顶点个数 * @param data 图的各个顶点的值 * @param weight ...
  • 学完离散数学数据结构中图的最小生成树算法,对两种经典算法普利姆算法和克鲁斯卡尔算法有一点自己的认识。 Prim普利姆算法:在总的边集合-顶点集合A中,添加与A中顶点相邻的且边权值最小的顶点进入A。算法实现...
  • 主要介绍了C++使用Kruskal和Prim算法实现最小生成树,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • Prim算法 算法实现 算法证明 Kruskal算法 算法实现 算法证明 最小生成树简介 最小生成树(MST):给定一加权无向图,找出它的一颗最小生成树。 定义:图的最小生成树是它的一副含有其所有顶点的...
  • // Prim算法实现(采用邻接表存储).cpp : Defines the entry point for the console application.//#include "stdafx.h"#include "stdafx.h"#include#define MAX 100#define Infinity 65535typedef int WeiType;...
  • prim算法和kruskal算法详解。下面笔者将与大家共同探讨一下这两个经典的算法他们的C++代码实现。 首先我们先看引自百度百科的prim算法的定义:普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索...
  • 2.介绍一下我对书本上prim算法代码实现的理解 1.lowcost数组的作用 2.adjvex数组的作用 3.kruskal算法 3.要源码的直接看这里 1.题目简介 做完之后头发又掉了几根估计,写的代码将近两百行,结果提交上去OJ系统...
  • Prim算法和Kruskal算法都是描述连通图的最小生成树(最小权重生成树),也就是极小连通子图.( 就是在连接原图所有节点的情况下,使边的权值相加最小的通路) Prim算法 Prim算法的思路是随机从图上一个节点出发,选择与...
  • kruscalPrim算法,两种经典的最小生成树算法,编译通过,代码含义明确(C++)
  • prim 把不符合条件的两个岛屿间的权值赋为无穷大,这样,就不会再取这两个岛屿 #include&amp;lt;cstdio&amp;gt; #include&amp;lt;cstring&amp;gt; #include&amp;lt;cmath&amp;gt; #...
  • Prim算法和Kruskal算法介绍

    千次阅读 2020-12-24 17:57:24
    一、Prim算法普利姆(Prim)算法适用于求解无向图中的最小生成树(Minimum Cost Spanning Tree)。下面是Prim算法构造最小生成树的过程图解。 ...
  • Prim算法 Prim算法 主要是从结点出发,需要用到2个数组 path数组保存结点从哪个结点过来 lowcost保存起始结点到其他结点的代价,可以直接读邻接矩阵的内容 path = {-1, 1, 1, 0, 0} lowcost = {0, 10, 5, ∞, ∞} ...
  • 最小生成树的prim算法和kruscal算法

    千次阅读 2006-11-26 00:38:00
    bool MiniSpanTree_Prim(MGraph G, Closedge closedge[], int v0) {  int i, j, k;  for(i = 0; i < G.vexnum; ++i)  {  closedge[i].vertex = v0;  closedge[i].lowcost = G.edges[v0][i]....
  • //一边两点的结构 struct con{ int point1,point2,roadLength; //两个节点(孩子)长度 } map [ 50005 ]; int p[ 1005 ]; bool cmp(con a,con b) { return a.roadLength; } //寻找根节点 ...
  • Prim算法(普里姆算法): 思想:找到所有最短的权值连接的顶点集合,所组成的树是最小生成树。 从某一顶点为起点,逐步找各个顶点上的最小权值的边来构建最小生成树。 首先,从根节点A开始,我们发现A到对所有顶点...
  • 最小生成树-Prim算法和Kruskal算法

    万次阅读 多人点赞 2016-11-18 15:11:38
    Prim算法 1.概览 普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点(英语:Vertex (graph theory)),且其...
  • Prim算法和Kruskal算法浅析 问题描述 举一个实例,画出采用Prim算法构造最小生成树的过程 举一个实例,画出采用Kruskal算法构造最小生成树的过程 理论解析 Prim: 初始化:向空结果树T=(Vt,Et)中添加图G=(V,E)...
  • 【最小生成树】Prim算法和Kruskal算法的区别对比

    万次阅读 多人点赞 2016-12-21 21:59:32
    Prim算法和Kruskal算法都是从连通图中找出最小生成树的经典算法~ 从策略上来说,Prim算法是直接查找,多次寻找邻边的权重最小值,而Kruskal是需要先对权重排序后查找的~ 所以说,Kruskal在算法效率上是比Prim快...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,471
精华内容 588
关键字:

prim算法和kruscal算法的区别

友情链接: agrep4me.zip