JAVA—咖啡馆

——欢迎访问rogerfan的博客,常来《JAVA——咖啡馆》坐坐,喝杯浓香的咖啡,彼此探讨一下JAVA技术,交流工作经验,分享JAVA带来的快乐!本网站部分转载文章,如果有版权问题请与我联系。

BlogJava 首页 新随笔 联系 聚合 管理
  447 Posts :: 145 Stories :: 368 Comments :: 0 Trackbacks

图中代权的最小树的问题如下:


如果N个城市之间(图中的顶点)要修公路(图中的边)以使所有的城市联通,求怎样修可以使得公路的总长最小?
以上问题中的N个城市之间可以用图中的顶点表示,公路可以图中的边表示,公路的长度用边长表示,公路是双向的。问题就转换为在有N个顶点中的双向代权图中求得一个最小树。这里的代权指的边的长度,这与以前的不代权的最小树生成算法有很大的区别。


算法描述如下:


    任选一个节点开始,将该节点标志为已访问过的节点。也就是最小树中的节点。并设置为当前节点。
    1 寻找此访问节点的所有的邻接顶点,将边置入优先队列。邻接顶点不考虑已标志为访问的节点,因为它已在结果中。
    2 重复 步骤1 直到没有新的边被发现。此时在所有发现的边中找到最小的边,将其终点顶点标志为已访问,放入最小树中。并设置为当前节点
    3 重复 步骤 1,2,直到边的队列中没有多余的边,算法结束。

    注意:这里的优先级队列是个修正过的优先级队列,每次向该队列中加入一条新边时后,会检查是否有与新边终点相同的第二条边的存在,如果有,则删除边长较大的边。因为如果存在这样的边说明,有两条从已访问过节点到相同目标节点的路径存在,如果这样的话只用保留最小的那条边即可。

这里的图采用Graph 图-邻接矩阵法 表示。



算法实际上是作如下操作:


    先准备好一个优先级队列,里面以边长为关键值存放边,边的起点表示已被访问过的节点,而边的终点表示未访问的节点。将某节点标志为访问过节点。开始算法。
    寻找该访问过节点的所有边,并记录边长,放入边优先级队列中;
    找到所有从已访问过的节点到未访问节点的边中的最小边;
    将最小边连接的顶点设置为访问过,重复以上过程,直到所有节点都变成已访问。

主要的类如下:

    Edge:记载边

    PriorityQ:修正后的优先级队列

    Vertex:顶点

    Gragh:图

        Gragh.mstw():最小树生成算法

        Gragh.main():提供简单测试

代码如下:

 

JAVA代码

 

posted on 2008-05-28 15:45 rogerfan 阅读(348) 评论(0)  编辑  收藏 所属分类: 【JAVA算法】

只有注册用户登录后才能发表评论。


网站导航: