`
hm4123660
  • 浏览: 282436 次
  • 性别: Icon_minigender_1
  • 来自: 广州
博客专栏
Dea4ce76-f328-3ab2-b24a-fb268e1eeb75
数据结构
浏览量:69994
社区版块
存档分类
最新评论

最小生成树详解

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

下面开始最小生成树的学习。首先需要清楚一些概念。

 

生成树的定义:连通图G的一个子图如果是一棵包含G的所有顶点的树,则该子图称为G生成树。
              生成树是连通图的极小连通子图

所谓极小是指:若在树中任意增加一条边,则将出现一个回路;若去掉一条边,将会使之变成

连通图。 

 

最小生成树的定义:带权图对应的生成树, 生成树各边的权值总和称为生成树的权。权最小的生

树称为最小生成树

 

明白了概念之后,就开始学习使用Prim算法(普里姆算法)来生成最小二叉树。

首先我们要生成最小二叉树的无向图如下所示:

 

 

 

当然,我们先要把这个无向图数据化,让计算机可以理解这个图,我们这次使用邻接矩阵来数据化此无向图

即用个二维数组表示:

#define INF 100000 //表示不可到达

#define MAXSIZE 6 //表示图的结点个数

//邻接矩阵存储图的信息
int map[MAXSIZE][MAXSIZE]={
	{0,4,2,3,INF,INF},
	{4,0,5,4,3,INF},
	{2,5,0,1,INF,2},
	{3,4,1,0,6,2},
	{INF,3,INF,6,0,4},
	{INF,INF,2,2,4,0}
};

 

 Prim()算法

 基本思想:假设G=(V,E)是连通的,TE是G上最小生成树中边的集合。算法从U={u0}(u0∈V)、TE={}开始。重复执行下列操作:

   在所有u∈U,v∈V-U的边(u,v)∈E中找一条权值最小的边(u0,v0)并入集合TE中,同时v0并入U,直到V=U为止。

   此时,TE中必有n-1条边,T=(V,TE)为G的最小生成树。

   Prim算法的核心:始终保持TE中的边集构成一棵生成树

 

上面的基本思想看起来非常费解,为了更好的理解,我们一步步进行说明:

我们首先定义一个存储最小生成树的结构体:

 

//用来存储最小生成树的边和权值
struct path
{
	int start;//起点
	int end;  //终点
	int weight; //权值
};

 

 我们定义一个结构体path数组lowcost来存放候选边,此算法的难点就在lowcost数组的更新与选择。

path lowcost[MAXSIZE];//邻近点(未被标记)的最小距离

 

为了详细说明lowcost数组的更新与选择,我在画图上画出了步骤如下



 

理解了图中的原理的话,那么Prim()算法的代码就能写出来了,代码如下:

 

 

//普里姆算法--最小生成树
void Prim(path section[],int v)//v起始点
{
	path lowcost[MAXSIZE];//邻近点(未被标记)的最小距离

	path tree[MAXSIZE-1];  //存放最小生成树

	int visited[MAXSIZE]={0};  //已经访问的结点为1

	path min;

	for(int i=0;i<MAXSIZE;i++)
	{
		lowcost[i].weight=map[v][i];
		lowcost[i].start=v;	
		lowcost[i].end=i;
	}

	//循环查找路径,查找次数为结点数减1
	for(int j=0;j<MAXSIZE-1;j++)
	{
		//获取权值不为0且最小的边
		min.weight=INF;
		for(int i=0;i<MAXSIZE;i++)
		{
			
			if(lowcost[i].weight!=0&&lowcost[i].weight<min.weight)
			{
				min=lowcost[i];
			}
		}

		tree[j]=min;//获取最小权值,存入最小生成树数组里

		visited[v]=1;//已访问

		v=min.end;//修改起始点

		//修改lowcost数组
		for(int i=0;i<MAXSIZE;i++)
	    {
			//若新的权值小于之前的权值,则更改
			if(map[v][i]<lowcost[i].weight)
			{
				lowcost[i].weight=map[v][i];
				lowcost[i].start=v;
				lowcost[i].end=i;
			}

			//已经访问的结点为0
			if(visited[i]==1)
               lowcost[i].weight=0;

	    }

	}

	//输出生成的最小二叉树的结果
	for(int i=0;i<MAXSIZE-1;i++)
	{
		cout<<tree[i].start<<"->"<<tree[i].end<<"  "<<tree[i].weight<<"  "<<endl;
	}

}

 

至此,我们就完成了Prim()算法的学习。

 

得到的最小生成树为:



 附上源码地址:https://github.com/longpo/algorithm/tree/master/MakeTree

2
2
分享到:
评论

相关推荐

    数据结构 最小生成树C代码

    数据结构最小生成树C代码详解 在计算机科学中,数据结构是指计算机中组织和存储数据的方式,包括数组、链表、栈、队列、树、图等。图是一种非线性数据结构, 由节点和边组成,节点之间通过边相连。最小生成树是图论...

    Prim算法构造最小生成树

    《Prim算法构造最小生成树详解》 在计算机科学和图论中,Prim算法是一种用于寻找加权无向图的最小生成树的经典算法。最小生成树是图中一个权重之和尽可能小的树形子图,它连接了图中的所有顶点。Prim算法是一种贪心...

    最小生成树kruskal算法

    ### 最小生成树Kruskal算法详解 #### 算法背景与定义 最小生成树(Minimum Spanning Tree,简称MST)是图论中的一个经典问题,涉及到在一个加权图中寻找一棵包含所有顶点的子图,使得这棵子图的总权重最小。在实际...

    构造可以使n个城市连接的最小生成树

    ### 构造可以使n个城市连接的最小生成树 #### 综合训练目的与要求 本次实习旨在通过实际项目加深学生对数据结构与C程序设计的理解与应用能力。具体目标包括: 1. **理论联系实际**:让学生通过具体的编程任务,如...

    最小生成树C++代码实现

    ### 最小生成树C++代码实现解析 #### 一、最小生成树概念 最小生成树(Minimum Spanning Tree,简称MST)是指在一个加权无向图中找到一棵包含所有顶点的生成树,使得其边的权重之和最小。在实际应用中,最小生成树...

    数据结构实验报告9-图-Prim算法求最小生成树-实验内容与要求.docx

    根据给定的文件信息,本篇内容将围绕“数据结构实验报告9-图-Prim算法求最小生成树”展开,具体涉及的知识点包括Prim算法的基本原理及其应用、图的邻接矩阵存储结构的设计与实现、最小生成树的概念及求解过程、以及...

    算法分析与设计-实验一 最小生成树实验报告.docx

    《算法分析与设计-实验一 最小生成树实验报告》 最小生成树是图论中的一个重要概念,它在计算机科学中有着广泛的应用,特别是在网络设计、最优化问题和数据结构中。本次实验主要关注的是如何使用Kruskal算法来找到...

    zuixiaoshengchengshu.rar_C++最小生成树_site:www.pudn.com_visual c

    《C++实现最小生成树详解》 在计算机科学中,数据结构与算法是核心部分,而最小生成树问题则是图论中的一个重要概念。本资源针对的是C++编程环境下,通过Visual C++工具来实现最小生成树算法。...

    stp生成树详解

    STP(生成树协议)是局域网中用于防止循环路径和由此引发的广播风暴的一种重要技术。在具有多条物理连接的交换网络中,如果不进行管理,可能会形成环路,导致数据包在网络中无休止地循环,破坏网络稳定性。STP通过...

    prim(suanfa).rar_prim_最小生成树

    《Prim算法实现最小生成树详解》 在图论中,最小生成树(Minimum Spanning Tree, MST)是一个网络图的概念,用于寻找连接所有顶点的边的集合,使得这些边的总权重最小。Prim算法是一种经典的求解最小生成树的方法,...

    数据结构实现最小生成树算法

    ### 数据结构实现最小生成树算法 #### 最小生成树概念及应用场景 最小生成树(Minimum Spanning Tree, MST)是图论中一个重要的概念,在多种实际场景中有着广泛的应用,如网络设计、通信系统构建等。在一个加权无...

    最小生成树

    ### 最小生成树知识点 #### 一、最小生成树概念 最小生成树(Minimum Spanning Tree,MST)是图论中的一个经典问题。对于一个无向连通图,其最小生成树是一棵包含该图所有顶点的树,且所有边的权重之和最小。在...

    最小生成树算法详解

    详细的最小生成树全解,讲述金典的最小生成树算法,全面掌握最小生成树算法

    贪心算法实现最小生成树

    ### 贪心算法实现最小生成树——Prim算法详解及C语言实现 #### Prim算法概述 **Prim算法**是一种在连通带权图中寻找最小生成树(Minimum Spanning Tree, MST)的有效方法。该算法属于贪心算法的一种,通过一系列...

    图的最小生成树prim算法

    ### 图的最小生成树Prim算法详解 在计算机科学与图论中,图的最小生成树(Minimum Spanning Tree,MST)是一个加权无向图的子图,它包含图中的所有顶点,并且所有边的权重之和最小。Prim算法是一种贪心算法,用于...

    最小生成树(MST)问题——北京大学暑期课《ACM/ICPC竞赛训练》

    ### 最小生成树(MST)问题详解 #### 一、最小生成树概念 最小生成树(Minimum Spanning Tree, MST)问题是计算机科学与图论领域中的一个重要问题,尤其是在网络设计、电路板布线等领域有着广泛的应用。对于一个连通的...

    算法最小生成树

    根据给定文件的信息,我们可以提炼出与“算法最小生成树”相关的知识点,主要围绕普利姆算法进行深入探讨。 ### 最小生成树简介 在图论中,最小生成树(Minimum Spanning Tree, MST)是无向连通图的一个子集,它...

    prim算法求最小生成树 源程序

    ### Prim算法求最小生成树详解 #### 一、引言 Prim算法是一种用于寻找图的最小生成树(Minimum Spanning Tree, MST)的有效方法。它适用于带权无向图,并且能够确保找到一棵连接所有顶点且总权重最小的树。在实际...

    最小生成树的C程序实现

    ### 最小生成树的C程序实现:Prim算法详解 #### 引言 在计算机科学与图论领域,最小生成树(Minimum Spanning Tree, MST)是无向加权图的一个重要概念,它指的是一个无环且连接所有顶点的子图,其中边的权重之和...

Global site tag (gtag.js) - Google Analytics