首页 > 其他分享 >最小生成树

最小生成树

时间：2022-10-29 13:23:08浏览次数：71  
标签：matrix self 最小 生成 range edges 顶点 65535

如下图是个带权值的网结构图。要用最小的成本将所有元素连接起来，即n个顶点，用n-1条边把连通图连接起来，并且使得权值的和最小。定义：把构造连通网的最小代价生成树称为最小生成树。这里介绍两种经典算法。

img

1. 普里姆（Prim）算法

假设N=(V,E)是连通图，TE是N上的最小生成树中边的集合。

  1. U={u0}(u0∈V)， TE={ }。

  2. 在所有u∈U，v∈V-U的边(u，v)∈E 中找一条代价(权值)最小的边(u0，v0) 并入集合TE，同时v0并入U。

  3. 重复2，直至U=V为止。
    此时TE中必有n-1条边，则T= (V,{TE}) 为N的最小生成树。

    img

python代码实现：

class MGraph():
    def __init__(self):
        self.vertex = []
        self.matrix = []
        self.numNodes = 0
        self.numEdges = 0

    def createMGraph(self):
        """创建无向网图的邻接矩阵表示"""
        INFINITY = 65535
        self.numNodes = int(input("请输入顶点数："))
        self.numEdges = int(input("请输入边数："))
        for i in range(self.numNodes):
            self.vertex.append(input("请输入一个顶点："))

        for i in range(self.numNodes):
            self.matrix.append([])
            for j in range(self.numNodes):
                if i == j:
                    self.matrix[i].append(0)  # 初始化邻接矩阵
                else:
                    self.matrix[i].append(INFINITY)  # 初始化邻接矩阵

        for k in range(self.numEdges):  # 读入numEdges条边，建立邻接矩阵
            i = int(input("请输入边(vi,vj)上的下标i:"))
            j = int(input("请输入边(vi,vj)上的下标j:"))
            w = int(input("请输入边(vi,vj)上的权w:"))
            self.matrix[i][j] = w
            self.matrix[j][i] = self.matrix[i][j]  # 因为是无向网图，矩阵对称

    def viewMGraphStruct(self):
        print(self.matrix)


def MiniSpanTree_Prim(G):
    INFINITY = 65535  # 用一个极大值代替∞
    adjvex = []  # 保存相关顶点间边的权值点下标
    lowcost = []  # 保存相关顶点间边的权值
    adjvex.append(0)  # 初始化第一个权值为0，即v0加入生成树
    lowcost.append(0)  # 初始化第一个顶点下标为0，表示从v0开始
    for i in range(1, G.numNodes):  # 循环除下标为0外的所有顶点
        lowcost.append(G.matrix[0][i])  # 将v0顶点与之有边的权值存入列表
        adjvex.append(0)  # 初始化都为v0的下标
    for i in range(1, G.numNodes):
        min_w = INFINITY  # 初始化最小权值为∞
        j, k = 1, 0
        while j < G.numNodes:  # 循环全部顶点
            if lowcost[j] != 0 and lowcost[j] < min_w:  # 如果权值不为0且权值小于min_w
                min_w = lowcost[j]  # 让当前值成为最小值
                k = j  # 记录最小值的下表，存入k
            j += 1
        print("({},{})".format(adjvex[k], k))  # 打印当前顶点边中权值最小的边
        lowcost[k] = 0  # 将当前顶点权值设为0，此顶点已完成任务
        for j in range(1,G.numNodes):  # 循环所有顶点
            if lowcost[j] != 0 and G.matrix[k][j] < lowcost[j]:  # 如果下标为k的顶点的各边权值小于此前这些顶点未被加入生成树的权值
                lowcost[j] = G.matrix[k][j]  # 将较小的权值存入lowcost相应位置
                adjvex[j] = k  # 将下标为k的顶点存入adjvex


if __name__ == '__main__':
    G = MGraph()
    G.createMGraph()
    G.viewMGraphStruct()
    MiniSpanTree_Prim(G)

以下图网图为例：

img

输入图的信息后生成的邻接矩阵和最小生成树如下所示：

[[0, 10, 65535, 65535, 65535, 11, 65535, 65535, 65535],
[10, 0, 18, 65535, 65535, 65535, 16, 65535, 12],
[65535, 18, 0, 22, 65535, 65535, 65535, 65535, 8], 
[65535, 65535, 22, 0, 20, 65535, 24, 16, 21],
[65535, 65535, 65535, 20, 0, 26, 65535, 7, 65535], 
[11, 65535, 65535, 65535, 26, 0, 17, 65535, 65535],
[65535, 16, 65535, 24, 65535, 17, 0, 19, 65535], 
[65535, 65535, 65535, 16, 7, 65535, 19, 0, 65535], 
[65535, 12, 8, 21, 65535, 65535, 65535, 65535, 0]]

(0,1)
(0,5)
(1,8)
(8,2)
(1,6)
(6,7)
(7,4)
(7,3)

2. 克鲁斯卡尔(Kruskal)算法

假设连通网N=(V,E),将N中的边按权值从小到大的顺序排列。

  1. 初始状态为只有n个顶点而无边的非连通图T={V，{ }}，图中每个顶点自成一个连通分量。

  2. 在E 中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中(即不形成回路)，否则舍去此边而选择下一条代价最小的边。

  3. 重复2，直至T中所有顶点都在同一个连通分量上为止。

    img

    算法的实现要先将邻接矩阵的存储方式转换为边集数组的存储方式。

算法步骤：

  1. 将邻接矩阵的存储方式转换为边集数组的存储方式。
  2. 将边集数组Edge中的元素按权值从小到大排序。
  3. 依次查看数组Edge中的边，循环执行以下操作：
  • 依次从排序好的数组Edge中选出一条边（U1,U2）
  • 在Vexset中分别查找v1和v2 所在的连通分量vs1 和vs2，并进行判断：

*如果vs1 和vs2不等，表明所选的两个顶点分属不同的连通分量，输出此边，并合并vs1 和vs2两个连通分量。
*如果vs1 和vs2相等，表明所选的两个顶点属于同一个连通分量，舍去此边而选择下一条权值最小的边。

python实现：

 class MGraph():
    def __init__(self):
        self.vertex = []
        self.matrix = []
        self.numNodes = 0
        self.numEdges = 0

    def createMGraph(self):
        """创建无向网图的邻接矩阵表示"""
        INFINITY = 65535
        self.numNodes = int(input("请输入顶点数："))
        self.numEdges = int(input("请输入边数："))
        for i in range(self.numNodes):
            self.vertex.append(input("请输入一个顶点："))

        for i in range(self.numNodes):
            self.matrix.append([])
            for j in range(self.numNodes):
                if i == j:
                    self.matrix[i].append(0)  # 初始化邻接矩阵
                else:
                    self.matrix[i].append(INFINITY)  # 初始化邻接矩阵

        for k in range(self.numEdges):  # 读入numEdges条边，建立邻接矩阵
            i = int(input("请输入边(vi,vj)上的下标i:"))
            j = int(input("请输入边(vi,vj)上的下标j:"))
            w = int(input("请输入边(vi,vj)上的权w:"))
            self.matrix[i][j] = w
            self.matrix[j][i] = self.matrix[i][j]  # 因为是无向网图，矩阵对称

    def viewMGraphStruct(self):
        print(self.matrix)


class EdgeNode():
    """边节点"""
    def __init__(self):
        self.begin = None
        self.end = None
        self.weight = None


def TransEdge(G):
    """将邻接矩阵转换为边集数组"""
    INFINITY = 65535  # 极大值
    k = 0
    edges = []  # 边集数组
    for i in range(G.numEdges):  # 注意这里千万不要用列表推导式，初始化边集数组，不然会出现列表越界错误
        e = EdgeNode()  # 实例化边节点
        edges.append(e)
    for i in range(G.numNodes - 1):
        for j in range(i + 1, G.numNodes):
            if 0 < G.matrix[i][j] < INFINITY:
                edges[k].begin = i
                edges[k].end = j
                edges[k].weight = G.matrix[i][j]
                k += 1
    # 按权由小到大排序(冒泡排序)
    for i in range(G.numEdges):
        for j in range(i + 1, G.numEdges):
            if edges[i].weight > edges[j].weight:
                edges[i], edges[j] = edges[j], edges[i]

    print("权排序后的为：")
    for i in range(G.numEdges):
        print("({},{}) {}".format(edges[i].begin, edges[i].end, edges[i].weight))

    return edges


def Find(parent, f):
    """查找连线顶点的尾部下标"""
    while parent[f] > 0:
        f = parent[f]
    return f


def MiniSpanTree_Kruskal(G):
    parent = [0 for _ in range(G.numNodes)]  # 定义并初始化一个列表用来判断边与边是否形成环路
    edges = TransEdge(G)  # 由邻接矩阵转换来的边集数组
    print("打印最小生成树：")
    for i in range(G.numEdges):  # 循环每一条边
        n = Find(parent, edges[i].begin)
        m = Find(parent, edges[i].end)
        if n != m:  # 如果n与m不相等，说明此边没有与现有的生成树形成环路
            parent[n] = m  # 将此边的结尾顶点放入下标为起点的的parent中，表示此顶点已经在生成树集合中
            print("({},{}) {}".format(edges[i].begin, edges[i].end, edges[i].weight))


if __name__ == '__main__':
    G = MGraph()
    G.createMGraph()
    G.viewMGraphStruct()
    MiniSpanTree_Kruskal(G)

以下图网图为例：

img

输入图的信息后生成的邻接矩阵和最小生成树如下所示：

[[0, 10, 65535, 65535, 65535, 11, 65535, 65535, 65535], 
[10, 0, 18, 65535, 65535, 65535, 16, 65535, 12], 
[65535, 18, 0, 22, 65535, 65535, 65535, 65535, 8],
[65535, 65535, 22, 0, 20, 65535, 24, 16, 21], 
[65535, 65535, 65535, 20, 0, 26, 65535, 7, 65535], 
[11, 65535, 65535, 65535, 26, 0, 17, 65535, 65535],
[65535, 16, 65535, 24, 65535, 17, 0, 19, 65535], 
[65535, 65535, 65535, 16, 7, 65535, 19, 0, 65535],
[65535, 12, 8, 21, 65535, 65535, 65535, 65535, 0]]

打印最小生成树：
(4,7) 7
(2,8) 8
(0,1) 10
(0,5) 11
(1,8) 12
(3,7) 16
(1,6) 16
(6,7) 19

本文部分概念和图片来自：https://www.jianshu.com/p/d9ca383e2bd8

标签：matrix,self,最小,生成,range,edges,顶点,65535
From： https://www.cnblogs.com/minqiliang/p/16838541.html

相关文章

  • 【PE806】Nim on Towers of Hanoi（汉诺塔游戏，生成函数）
    PE：ProjectEuler题意：汉诺塔游戏是如下的问题：有三根柱子，第一根柱子套有\(n\)个圆盘，圆盘从上往下半径递增。每次操作可以把套在某根柱子上的最上面的那个圆盘移到另一个......
  • 动态规划-746. 使用最小花费爬楼梯
    题目描述给你一个整数数组cost，其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。你可以选择从下标为0或下......
  • 生成9宫图
    #比如，美术直接给了一张原大小的弹框背景图，但实际该图可以做成九宫可拉伸格形式，但是美术又不愿意再重切一次，那我们就自己来吧，先用Unity的9宫工具，框出要保留的四个角#然......
  • K3CloudDevTools【强类型DynamicObject代码生成器】
    强类型DynamicObject代码生成器DynamicObject是一个类似Dictionary的结构。实际使用过程中，需牢记Key，同时还需频繁进行类型转换，十分麻烦。通过本工具，可以为表单创建一个强......
  • 1879. 两个数组最小的异或值之和
    题目描述给了两个数组nums1和nums2，长度都是n，问怎么排列可以让数组对应元素的异或值之和最小？f1-二进制枚举+状态压缩基本分析1.有没有是啥贪心做法，因为看到相同元素异或......
  • 【EA的练习赛2】【洛谷P7274】草地（单调栈，LCT维护最小生成树）
    学到了很多。我们分步走。首先在做这道题前先观察到几个小性质：操作顺序不同不影响结果发现对于每一个黑点，一通操作过后它扩展出的区域是一个矩形，而操作顺序是不影响......
  • 【CFgym102482D】Gem Island（生成函数）
    题意：有一个序列\(a_1,\cdots,a_n\)，初始时它们全为\(1\)。进行\(d\)轮操作：每轮操作以正比于\(a\)的概率选择一个\(a_i\)加\(1\)。求最后\(a_1,\cdots,a_n\)中前......
  • 【CF1253F】Cheap Robot（最小生成树，最短路）
    首先发现所有询问点都是充电桩这个条件很有用。它能滋生出一种暴力到极端的想法：用Floyd对全局跑一遍最短路。然后新建一个图，图中两两充电桩连一条边，边权为它们之间的最......
  • 【CF1120D】Power Tree（建图，差分，最小生成树）
    题面题意有点难懂。主要是洛谷给的翻译太zz了。大概的意思是：给定一棵\(n\)个点的有根树，\(1\)为根，每一个点有一个代价\(c_i\)。然后有两个人Alice和Bob在玩游......
  • 【CF888G】Xor-MST（01Trie，最小生成树）
    看到异或最值要么是线性基要么是01Trie。线性基显然可以排除。那么先把所有的\(a_i\)插入01Trie内。然后发现对于任意两个数\(a_i\)和\(a_j\)：你发现它们在\(......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99