【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】
前面我们讨论了图的创建、添加、删除和保存等问题。今天我们将继续讨论图的一些其他问题,比如说如何在图的环境下构建最小生成树。为什么要构建最小生成树呢?其实原理很简单。打个比方,现在某一个乡镇有n个村,那么这n个村肯定是联通的。现在我们打算在各个村之间搭建网线,实现村村通的工程。那么有什么办法可以实现村村互通,同时又使得最后的总距离最小呢?要达到这个目的,就必须在已有的图中构建最小生成树。
生成最小生成树的方法很多,prim方法就是其中的一种。那么生成最小生成树的基本步骤是什么呢?很简单,听我慢慢道来:
1)以某一个点开始,寻找当前该点可以访问的所有的边;
2)在已经寻找的边中发现最小边,这个边必须有一个点还没有访问过,将还没有访问的点加入我们的集合,记录添加的边;
3)寻找当前集合可以访问的所有边,重复2的过程,直到没有新的点可以加入;
4)此时由所有边构成的树即为最小生成树。
那么,代码应该怎么编写呢?朋友们可以自己好好思考一下。
a)首先,我们定义基本的数据结构。
b)DIR_LINE的基本操作
【未完,待续】
分享到:
相关推荐
prim算法 代码 报告prim算法 代码 报告prim算法 代码 报告prim算法 代码 报告prim算法 代码 报告
prim算法(C语言编写) 可以供学习参考使用
C语言实现prim算法
封装DFS、BFS算法、Prim算法、Kruskal算法、Dijstra算法、Floyd算法 上机作业: 定义采用邻接矩阵存储的图结构
Prim算法 1.概览 普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点(英语:Vertex (graph theory)),且其所有...
代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小...
邻接矩阵 Prim 算法,C++完美实现,数据结构作业。
Prim算法的cpp实现
Prim算法的C语言实现,原创,算法课作业
【老生谈算法】Matlab实现无约束条件下普列姆(Prim)算法.docx
图论算法:最小生成树——Prim算法和Kruskal算法C 实现
Prim算法与Kruskal算法 求最小生成树 源代码 实验报告 完整
prim算法的实现,包括图的邻接矩阵, prim算法的实现 prim算法的实现
prim算法Huffman算法Dijkstra算法和实验报告
prim算法prim算法prim算法prim算法prim算法prim算法prim算法prim算法prim算法
prim算法 Kruskal算法分别实现最小生成树
用邻接表为存储结构的prim算法,程序中包括图的建立,图的深度优先遍历,和最小生成树prim算法
PRIM算法`````````````
prim算法
图的深度优先搜索,广度优先搜索,最小生成树算法,包括kruskal、prim算法的代码,以及详细的注释。深度优先应用递归、广度优先搜索利用队列、kruskal利用STL中的关联容器set、prim算法利用二叉堆结构进行优化。