手机版 欢迎访问it开发者社区(www.mfbz.cn)网站

当前位置: > 开发

算法学习-最小生成树

时间:2021/10/28 23:53:16|来源:|点击: 次

文章目录

    • 概念介绍
      • 最小生成树
      • Prim实现步骤
    • 代码实现
      • 最小生成树代码
      • 最短路图的创建
      • 调用示例
    • 趣味应用

概念介绍

本博客在学习北京大学陈斌老师《数据结构与算法》MOOC课程中总结反思形成。

最小生成树

  • 生成树:拥有图中所有的顶点和最小数量的边,以保持连通的子图;
  • 最小生成树:包含所有顶点V,以及E的无圈子集,并且边权重之和最小。

Prim实现步骤

准备阶段

  • “可以安全添加的边”:一端顶点在树中,另一端不在树中的边,以便保持树的无圈特性。
  • 顶点的访问次序由一个优先队列来控制,队列中作为优先级的是顶点的dist属性。

实现阶段

  • 判断是否最小生成树
  • 不是则:反复找到一条最小权重的可以安全添加的边,将边添加到树

可视化
image-20211027231512067

代码实现

最小生成树代码

陈斌老师实现的Prim算法

# 最小生成树
def prim(G, start):
    pq = PriorityQueue()
    for v in G:
        v.setDistance(sys.maxsize)
        v.setPred(None)

    start.setDistance(0)
    pq.buildHeap([(v.getDistance(), v) for v in G])
    while not pq.isEmpty():
        currentVert = pq.delMin()
        for nextVert in currentVert.getConnections():
            newCost = currentVert.getWeight(nextVert)
            # 判断是否是可以安全添加的边
            if nextVert in pq and newCost < nextVert.getDistance():
                nextVert.setPred(currentVert)
                nextVert.setDistance(newCost)
                pq.decreaseKey(nextVert, newCost)

最短路图的创建

这里为了方便以后的调用,考虑到邻接矩阵使用的广泛性,实现了给定邻接矩阵,创建邻接表图

# 实现邻接矩阵转化为邻接图
def Matrix2Graph(LJGraph, LJmatrix):
    for i in range(len(LJmatrix)):
        LJGraph.addVertex(i)

    for i in range(len(LJmatrix)):
        for j in range(len(LJmatrix[0])):
            if i != j:
                LJGraph.addEdge(i, j, LJmatrix[i][j])

调用示例

if __name__ == '__main__':
    TreeGraph = Graph()
    Treematrix = [[0, 2, 3, sys.maxsize, sys.maxsize, sys.maxsize, sys.maxsize],
                  [2, 0, 1, sys.maxsize, 4, sys.maxsize, sys.maxsize],
                  [3, 1, 0, sys.maxsize, sys.maxsize, 5, sys.maxsize],
                  [sys.maxsize, sys.maxsize, sys.maxsize, 0, 1, sys.maxsize, sys.maxsize],
                  [sys.maxsize, 4, sys.maxsize, 1, 0, 1, sys.maxsize],
                  [sys.maxsize, sys.maxsize, 5, sys.maxsize, 1, 0, 1],
                  [sys.maxsize, sys.maxsize, sys.maxsize, sys.maxsize, sys.maxsize, 1, 0]]
    Matrix2Graph(TreeGraph, Treematrix)
    prim(TreeGraph, TreeGraph.getVertex(0))

趣味应用

中心城市地位可视化:参考

由于缺少数据来源,这里贴出原帖给的一张图
image-20211027224157100

Copyright © 2002-2019 某某自媒体运营 版权所有