【贪心】最小生成树Prim算法Python实现

发布时间:2023年12月24日

因上努力

个人主页:丷从心

系列专栏:贪心算法

果上随缘


问题描述

  • G = ( V , E ) G = (V , E) G=(V,E)是无向连通带权图, E E E中每条边 ( v , w ) (v , w) (v,w)的权为 c [ v ] [ w ] c[v][w] c[v][w]
  • 如果 G G G的一个子图 G ′ G^{'} G是一棵包含 G G G的所有顶点的树,则称 G ′ G^{'} G G G G的生成树
  • 生成树上各边权的总和称为该生成树的耗费,在 G G G的所有生成树中,耗费最小的生成树称为 G G G的最小生成树

最小生成树的性质

  • G = ( V , E ) G = (V , E) G=(V,E)是连通带权图, U U U V V V的真子集,如果 ( u , v ) ∈ E (u , v) \in E (u,v)E,且 u ∈ U u \in U uU v ∈ V ? U v \in V - U vV?U,且在所有这样的边中, ( u , v ) (u , v) (u,v)的权 c [ u ] [ v ] c[u][v] c[u][v]最小,那么一定存在 G G G的一棵最小生成树,它以 ( u , v ) (u , v) (u,v)为其中一条边
  • 这个性质有时也称为 M S T MST MST性质
证明
  • 假设 G G G的任何一棵最小生成树都不包含边 ( u , v ) (u , v) (u,v),将边 ( u , v ) (u , v) (u,v)添加到 G G G的一棵最小生成树 T T T上,将产生含有边 ( u , v ) (u , v) (u,v)的圈,并且在这个圈上有一条不同于 ( u , v ) (u , v) (u,v)的边 ( u ′ , v ′ ) (u^{'} , v^{'}) (u,v),使得 u ′ ∈ U u^{'} \in U uU v ′ ∈ V ? U v^{'} \in V - U vV?U,如下图所示

1

  • 将边 ( u ′ , v ′ ) (u^{'} , v^{'}) (u,v)删去,得到 G G G的另一棵生成树 T ′ T^{'} T,由于 c [ u ] [ v ] ≤ c [ u ′ ] [ v ′ ] c[u][v] \leq c[u^{'}][v^{'}] c[u][v]c[u][v],所以 T ′ T^{'} T的耗费 ≤ T \leq T T的耗费,于是 T ′ T^{'} T是一棵含有边 ( u , v ) (u , v) (u,v)的最小生成树,与假设矛盾

Prim算法

  • G = ( V , E ) G = (V , E) G=(V,E)是连通带权图, V = { ? 1 , 2 , ? ? , n ? } V = \set{1 , 2 , \cdots , n} V={1,2,?,n}
  • 首先置 S = { ? 1 ? } S = \set{1} S={1},然后,只要 S S S V V V的真子集,就做如下贪心选择
  • 选取满足条件 i ∈ S i \in S iS j ∈ V ? S j \in V - S jV?S,且 c [ i ] [ j ] c[i][j] c[i][j]最小的边,将边 ( i , j ) (i , j) (i,j)添加到边集 T T T中,并将顶点 j j j添加到 S S S
  • 这个过程一直进行到 S = V S = V S=V时为止,选取到的所有边恰好构成 G G G的一棵最小生成树

Prim算法的正确性

  • 算法结束时,边集 T T T中包含 G G G n ? 1 n - 1 n?1条边,利用最小生成树性质和数学归纳法容易证明,边集 T T T始终包含 G G G的某棵最小生成树中的边,因此,算法结束时, T T T中的所有边构成 G G G的一棵最小生成树

时间复杂性

  • 对于一个具有 n n n个顶点的带权无向图,Prim算法进行二重循环,需要 O ( n 2 ) O(n^{2}) O(n2)时间

Python实现

import sys


class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)]

    def printMST(self, parent):
        print('边\t\t权')

        for i in range(1, self.V):
            print(f'{parent[i]} - {i}\t{self.graph[i][parent[i]]}')

    def minKey(self, key, mstSet):
        min_val = sys.maxsize
        min_index = None

        for v in range(self.V):
            if key[v] < min_val and not mstSet[v]:
                min_val = key[v]
                min_index = v

        return min_index

    def primMST(self):
        key = [sys.maxsize] * self.V
        parent = [None] * self.V
        mstSet = [False] * self.V

        key[0] = 0
        parent[0] = -1

        for _ in range(self.V):
            u = self.minKey(key, mstSet)

            mstSet[u] = True

            for v in range(self.V):
                if self.graph[u][v] > 0 and not mstSet[v] and self.graph[u][v] < key[v]:
                    key[v] = self.graph[u][v]
                    parent[v] = u

        self.printMST(parent)


g = Graph(5)

g.graph = [
    [0, 2, 0, 6, 0],
    [2, 0, 3, 8, 5],
    [0, 3, 0, 0, 7],
    [6, 8, 0, 0, 9],
    [0, 5, 7, 9, 0],
]

g.primMST()
边		权
0 - 1	2
1 - 2	3
0 - 3	6
1 - 4	5

文章来源:https://blog.csdn.net/from__2023_11_28/article/details/135180386
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。