文件名称:prim
-
所属分类:
- 标签属性:
- 上传时间:2012-11-16
-
文件大小:628byte
-
已下载:0次
-
提 供 者:
-
相关连接:无下载说明:别用迅雷下载,失败请重下,重下不扣分!
介绍说明--下载内容来自于网络,使用问题请自行百度
算法简介:Prim算法用于求无向图的最小生成树 设图G =(V,E),其生成树的顶点集合为U。
①、把v0放入U。
②、在所有u∈U,v∈V-U的边(u,v)∈E中找一条最小权值的边,加入生成树。
③、把②找到的边的v加入U集合。如果U集合已有n个元素,则结束,否则继续执行②。
其算法的时间复杂度为O(|E|log|V|)-Introduction to Algorithms: Prim algorithm used to find the undirected minimum spanning tree based graph G = (V, E), the spanning tree of the vertex set of U. ①, the v0 into the U. ②, all u ∈ U, v ∈ VU edge (u, v) ∈ E to find a minimum weight of the edge, adding spanning tree. ③, ② to find the edges of v to join U collection. If U have a collection of n elements, then the end, otherwise continue ②. The algorithm' s time complexity is O (| E | log | V |)
①、把v0放入U。
②、在所有u∈U,v∈V-U的边(u,v)∈E中找一条最小权值的边,加入生成树。
③、把②找到的边的v加入U集合。如果U集合已有n个元素,则结束,否则继续执行②。
其算法的时间复杂度为O(|E|log|V|)-Introduction to Algorithms: Prim algorithm used to find the undirected minimum spanning tree based graph G = (V, E), the spanning tree of the vertex set of U. ①, the v0 into the U. ②, all u ∈ U, v ∈ VU edge (u, v) ∈ E to find a minimum weight of the edge, adding spanning tree. ③, ② to find the edges of v to join U collection. If U have a collection of n elements, then the end, otherwise continue ②. The algorithm' s time complexity is O (| E | log | V |)
(系统自动生成,下载前可以参看下载内容)
下载文件列表
prim.c
本网站为编程资源及源代码搜集、介绍的搜索网站,版权归原作者所有! 粤ICP备11031372号
1999-2046 搜珍网 All Rights Reserved.