最小生成树问题，python解法

梦里梦外; 2022-05-19 04:21 158阅读 0赞

思路很简单：

主要是创建两个集合，一个表示已经遍历过的节点集合S，另一个表示还没有遍历过的节点W，算法的主要思想借鉴了prim算法，但是我没有尽行归并操作，直接遍历S和W中的点，寻找最短的边，从W中删除，并加入S中，本文参考：[https://blog.csdn.net/qq\_35644234/article/details/59106779][https_blog.csdn.net_qq_35644234_article_details_59106779]，主要Python算法代码如下：

# 最小生成树，动态规划解法
    class Solution:
        def __init__(self,X,start_node):
            self.X = X
            self.start_node = start_node
            
        def prim(self):
            num = len(self.X)
            first_node = self.start_node
            last_node = self.start_node
            sets = range(num)
            sets.pop(first_node)
            first_set = [self.start_node]
            self.dtgh(first_set,sets)
            return first_set
        def dtgh(self,past_sets,sets):
            if len(sets) == 0:
                return
            d_i = [] 
            d_min = 10000
            # 遍历还未经过的节点
            for i in range(len(sets)):
                d_ij = [] # 储存已经过集合中所有节点（j）到新集合中i节点的距离
                for j in past_sets:
                    d_ij.append(self.X[j][sets[i]])
                # 寻找最短的i节点到j节点的路径
                if min(d_ij)<d_min:
                    # 最短路径中的（位于老集合中的节点）j节点
                    j_min = d_ij.index(min(d_ij))
                    # 最短路径中的（位于新集合中的节点）i节点
                    i_d = i
                d_i.append(min(d_ij)) #求取所有i（新集合）节点与老集合的最小距离集合
                d_min = min(d_ij) #参与循环
            d_increase = min(d_i) # 当前最短路径（j，i）的最短距离
            print past_sets[j_min], "---->", sets[i_d], "the distance", d_increase
            past_sets.append(sets[i_d])
            sets.pop(i_d)
            self.dtgh(past_sets,sets)
    D = [[0,6,1,5,999,999],[6,0,5,999,3,999],[1,5,0,5,6,4],[5,999,5,0,999,2],[999,3,6,999,0,6],[999,999,4,2,6,0]]
    start_node = 0
    S = Solution(D,start_node)
    S.prim()

[https_blog.csdn.net_qq_35644234_article_details_59106779]: https://blog.csdn.net/qq_35644234/article/details/59106779