文件名称:prim
介绍说明－－下载内容均来自于网络，请自行研究使用
算法简介: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