您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

最小生成树

文章目录

  • 1.最小生成树
  • 2.信息广播问题
    • 单播解法
    • 洪水解法
  • 最小生成树算法
    • Prim算法
      • Prim算法示例
      • Prim算法:最小生成树
      • 视频地址
        • 推荐阅读

1.最小生成树

  • 本算法涉及到在互联网中网游设计者和网络收音机所面临的问题:信息广播问题
    • 网游需要让玩家获知其他玩家所在的位置
    • 收音机则需要让所有听众获取直播的音频数据
      在这里插入图片描述

2.信息广播问题

单播解法

  • 信息广播问题最简单的解法是由广播源维护一个收听者的列表。将每条信息向每个收听者发送一次
    • 如下图所示,每条信息会被发送4次,每个消息都采用最短路径算法到达收听者
  • 问题: 路由器A会处理4次相同消息,C仅会处理一次;而B/D位于其他三个收听者的最短路径上,则会处理转发3次相同消息
    • 会产生许多额外流量
      在这里插入图片描述

洪水解法

  • 特点
    • 信息广播问题的暴力解法,将每条信息息在路由器间散播出去
    • 所有路由器都将收到的信息转发到自己相邻的路由器和接收者
    • 如果没有限制,将造成洪水灾难
    • 很多路由器和收听者会不断重复收到相同的信息,永不停止!
  • 解决方法
    • 给每条信息附加一个生命值(TTL,Time To Live),初始设置为从信息源到最远的收听者的距离
    • 每个路由器收到一条消息,如果其TTL减少1,在转发出去
      • 如果TTL等于0了,则就直接抛弃这个信息
    • 这种洪水解法比前面的单播方法所产生的流量

最小生成树算法

  • 信息广播问题的最优解法,依赖于路由器关系图上选取具有最小权重的生成树(minimum weight spanning tree)
    • 生成树:拥有图中所有的顶点和最少数量的边,以保持连通的子图
  • 图G(V,E)的最小生成树T,定义为
    • 包含所有顶点V,以及E的无圈子集,并且边权重之和最小
    • 信息广播只需要从A开始,沿着树的路径层次向下传播
      • 每个路由器只需要处理一次消息,费用最小
        最小生成树

Prim算法

  • 解决最小生成树问题的算法,属于"贪心算法",每步都沿着最小权重的边向前搜索
  • 构造最小生成树的思路很简单,如果T还不是生成树,则反复做:
    • 找到一条最小权重的可以安全添加的边,将边添加到树T
    • "可以安全添加"的边,定义为以端顶点在树中,另一端不在树中的边,以便保持树的无圈特性

Prim算法示例

1
2
3
4
5
6
7

Prim算法:最小生成树

  • 代码实现
from pythonds.graphs import PriorityQueue, Graph, Vertex
import sys

def prim(G, start):
    pq = PriorityQueue()              #优先队列
    for v in G:
        v.setDistance(sys.maxsize)
        v.pred(None)                   #设置预测
    start.setDistance(0)
    pq.buildHeap([(v.getDistance(), v) for v in G])       #建堆,根据距离进堆
    while not pq.isEmpty():          #堆是否为空
        currentVert = pq.deMin()    #优先队列出队
        for nextVert in currentVert.getConnections():
            newCost = currentVert.getWeight(nextVert)
            if nextVert in pq and newCost < nextVert.getDistance():
                nextVert.setPred(cueerntVert)
                nextVert.setDistance(newCost)
                pq.decreaseKey(nextVert, newCost)

视频地址

中国大学

推荐阅读

图的应用:最短路径问题
图的应用:强连通分支


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进