最小生成树算法prime的具体算法这里不再赘述,很多地方都有介绍,下面着重介绍采用最小堆实现的基本原理。
使用最小堆时需要几个数据结构:
1> Index表,用来查找每个节点在堆中的具体位置
2> Node{int pos , int val}; 堆中的节点
pos,用来记录该节点在index表中的位置
val , 表示该节点与已经拓展的节点的最小距离,该结点需要时时改变。
3> del表,记录该元素是否已经拓展
需要用的几个方法:
keepHeap(int pos):
用来保持堆的性质,当删除堆顶时,需要交换最后一个元素到堆顶,然后从上向下保持堆。
adjustHeap(int pos , int val):
将堆中pos处的节点val变为为val,在本例中,val是比堆中已经存在元素小,因此只需要向上拓展堆。
算法流程如下:
1》 初始化堆:
void initHeap()
{
Heap[0].pos = 0;
Heap[0].val = 0;
Index[0] = 0;
HeapSize = N;
for (int i = 1; i < N; ++i)
{
Heap[i].val = INITMAX;
Heap[i].pos = i;
Index[i] = i;
}
memset(del , 0 , sizeof(del));
}
2>当heapsize != 0时, //第一层循环
弹出堆顶元素node. ,设该节点为u , (由于此步将顶部元素给删除了,因此需要keepHeap, 且del[u] = true)
对与node相邻的所有结点v //第二层循环
如果v还没拓展,且节点v在Heap中的val值小于 d(u , v) , 则需要修改堆中节点v的值为d(u,v), 这时需要adjustHeap(vpos , d(u,v));
将heapsize --; 继续循环。
del[u] = true,说明u已经被拓展。
由2可知,该算法的时间繁杂度为O(E * Log(N)); , 这是因为在第二循环遍历到了每个边,且调用addjustHeap时时间复杂度为log(N)。
下面是一个针对一个问题的实现 :
问题如下:
Description
The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem. They're planning to build some highways so that it will be possible
to drive between any pair of towns without leaving the highway system.
Flatopian towns are numbered from 1 to N. Each highway connects exactly two towns. All highways follow straight lines. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town
that is located at the end of both highways.
The Flatopian government wants to minimize the length of the longest highway to be built. However, they want to guarantee that every town is highway-reachable from every other town.
Input
The first line is an integer N (3 <= N <= 500), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 65536]) between village
i and village j.
Output
You should output a line contains an integer, which is the length of the longest road to be built such that all the villages are connected, and this value is minimum.
This problem contains multiple test cases!
The first line of a multiple input is an integer T, then a blank line followed by T input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.
The output format consists of T output blocks. There is a blank line between output blocks.
Sample Input
Copy sample
input to clipboard
1
3
0 990 692
990 0 179
692 179 0
Sample Output
分享到:
相关推荐
基于邻接矩阵存储的图的最小生成树的Prime算法,对学习C++和数据结构很有帮助
最小生成树的prime算法(MATLAB)
数据结构上最小生成树的prime算法,源代码是用c语言实现的,易于大家的理解。
最小生成树算法,基于Vs2010,可直接运行,代码可修改
输入数据: 7 11 A B 7 A D 5 B C 8 B D 9 B E 7 C E 5 D E 15 D F 6 E F 8 E G 9 F G 11 输出: A - D : 5 D - F : 6 A - B : 7 B - E : 7 E - C : 5 E - G : 9 Total:39
用字符文件提供数据建立连通带权网络邻接矩阵存储¬¬结构。编写程序,用Prim算法求一棵最小生成树。要求输出最小生成树的各条边(用顶点无序偶表示)、各条边上的权值、最小生成树所有边上的权值之和。
//最小生成树的kruskal的算法 #include "stdafx.h" #include #include #include using namespace std; //int maxint=mar_maxint; class BinaryTree; class EdgeNode//边的数据结构 { private: int u,v;//边所在的...
连通网的最小生成树的prime和Kruskal算法,完整的测试代码,包括图的基本操作代码(详见:http://download.csdn.net/detail/u013071074/7445893),包括两组测试数据。 prime和Kruskal算法介绍详见博文:...
最小生成树:利用普鲁姆算法,完成将给定节点和边的权值的图生成最小生成树,用于各项公共事业最少经费的设计方法
最小生成树 (MST),已被广泛用于广泛的科学领域与日常生活中,例如 粒子物理学(区分对撞机碰撞中的事件类别)、天文学(探测星团中的质量分离)、导航路线计算,近几年也不断有新的最小生成树算法被提出,在新的...
Prime 算法写的一个最小生成树的C++程序
随机生成网络,采用prime算法,生成最小生成树Matlab.zip
最小生成树c++实现 算法清晰明了 prime Kruscal两种算法实现
数据结构课程设计,最小生成树,包括Prim算法喝Krusical算法。图形化界面。
(1)分别利用 Kriuskal 算法和 Prime 求网的最小生成树。 (2)实现教科书中定义的抽象数据类型,以此表示构造生成树过程中的连通分量。 (3)以图和文本两种形式输出生成树中各条边以及他们的权值。
最小生成树有Prime和Kruskal,Prime是加点,用优先队列实现;Kruskal是加边,用并查集实现。这里最好用Prime,因为Prime能够从起点出发,获得一个以起点为根的树,并且能够得到每个点对应的父节点 这样生成的迷宫...
①任选一个顶点v1,将其涂红,其余顶点为白点;...③如此,每次将一条边和一个顶点涂成红色,直到所有顶点都成红色为止,最终的红色边和顶点便是最小生成树。上面的描述就是最小生成树的逐步生长过程
因该是prim算法 假设V是图中顶点的集合,E是图中边的集合,TE为最小生成树中的边的集合,则prim算法通过以下步骤可以得到最小生成树: