嘿,你忘记写博客了~

盛年不重来,一日难再晨,及时宜自勉,岁月不待人....

最小生成树算法

发布时间:2020-10-18编辑:windydeng浏览(832)评论览(0)

    文字表述:

    1. 新建图GG中拥有原图中相同的节点,但没有边

    2. 将原图中所有的边按权值从小到大排序

    3. 从权值最小的边开始,如果这条边连接的两个节点于图G中不在同一个连通分量中,则添加这条边到图G中

    4. 重复3,直至图G中所有的节点都在同一个连通分量中

    Input: A connected undirected graph G = (V;E) with edge weights we

    Output: A minimum spanning tree defined by the edges X

    for all u ∈ V:

    make set(u)

    X = {}

    Sort the edges E byweight

    //每次选取权重最小的边作为操作对象

    for all edges {u,v}∈ E, in increasing order of weight:

      //如果边的两个端点在不同的集合中,那么我们可以将该边加进来,

      //使集合两个连通组件相互连通

      if find(u) ≠find(v):

      add edge {u,v} toX

      union(u,v)

      //如果两个端点已经在同一个连通图中,那么加进该边就会形成环

      //因此舍弃该边

      if find(u) =find(v): do nothing

     

     

    辅助函数:

    makeset(x):构建一个只包含节点x的集合

    find(x):找出节点所属的集合

    union(x;y): 合并分别包含元素xy的两个集合

     

    通过辅助函数,我们就可以确定各个节点是否已经组合在了一个连通图,当所有的节点都在一个连通图中时,我们就得到了最小生成树。

    DPV一书中,给出了这些辅助函数的一种实现方式,同时还对union函数进行了优化,不过这一部分不是最小生成树算法的主体了,更多的是在研究数据结构方面对算法的贡献。

    该算法的思想是从已经形成树的部分出发,一步步向外扩张,找到离已形成连通图的部分“最近”的点将其加进来。

    文字表述

    从单一顶点开始,prime算法按照以下步骤逐步扩大树中所含顶点的数目,直到遍及连通图的所有顶点。

    1. 输入:一个加权连通图,其中顶点集合为V,边集合为E;

    2. 初始化:Vnew= {x},其中x为集合V中的任一节点(起始点),Enew= {};

    3. 重复下列操作,直到Vnew= V:

      1. 在集合E中选取权值最小的边(u,v),其中u为集合Vnew中的元素,而v则不是(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一);

      2. 将v加入集合Vnew中,将(u,v)加入集合Enew中;

    4. 输出:使用集合Vnew和Enew来描述所得到的最小生成树。

     

    procedure prim(G,w)

    Input: A connected undirected graph G = (V;E) with edge weights we

    Output: A minimum spanning tree defined by the array prev

    for all u ∈ V :

      cost(u)= ∞

      prev(u)= nil

    Pickany initial node u0

      cost(u0)= 0

    H = makequeue(V) (priority queue, using cost-values as keys)

    while H is not empty:

      v = deletemin(H)

      foreach (v; z) ∈ E:

        if cost(z) > w(v; z):

          cost(z)= w(v; z) //<*>

          prev(z)= v

          decreasekey(H;z)

     

    对比求最短路径的Dijkstra算法,我们会发现他们有极高的相似度

     

    procedure dijkstra(G;l; s)

    Input: Graph G = (V;E), directed or undirected; positive edge lengths {le : e∈E};vertex s ∈ V

    Output:For all vertices u reachable from s, dist(u) is set to the distance from s to u.

    for all u∈V :

      dist(u)= 1

      prev(u)= nil

    dist(s)= 0

    H = makequeue(V) (using dist-values as keys)

    while|H|>0 :

      u = deletemin(H)

      for all edges (u; v) ∈ E:

      if dist(v) > dist(u) + l(u; v):

        dist(v)= dist(u) + l(u; v) //<*>

        prev(v)= u

        decreasekey(H;v)

     

    除了<*>的部分,Prim是直接将边的权重赋上,Dijkstra则是加上前序的累积权重。所以理解和算法记忆上(其实理解了也不用可以去记忆算法的具体实现了,不过对于初学的我还是需要对这些主要的算法做强化记忆),在懂了Dijkstra之后看Prim就不会有很大的难度。


关键字词:最小生成树算法