Python之最小生成树 kruskal

简介: Python之最小生成树 kruskal

蓝桥杯填空压轴考察了最小生成树 因此本文围绕算法kruskal解决最小生成树问题


适合小白阅读(会比较枯燥)


试题E:


f53e07ca45ca48f6b4a03acc45017127.png


抛开最小生成树,阅读完题目,我们知道,每两座城堡都有一座桥连接。


因此一共有C(2021,2)座桥来连接。(组合数)


下面来掌握一个定义:(下面表述以顶点代替城堡,边代替桥)


连通图:在无向图中,若任意两个顶点vi与vj都有路径相通,则称该无向图为连通图。

对边加入了权值的连通图,叫连通网

那么对于2021个顶点,要保证所有顶点连通(比如有顶点A,B,如果A可以从C再到B,从D到E再到B等等,只要能通过一种路径到B,就称A和B有路径连通,并不是只有A直接到B这样),至少需要多少个边?答案是n-1条


数学归纳法证明:n=1 成立 假设n=k时,命题成立,即有k个顶点的连通图至少具有k-1条边,下面只需证k+1个顶点的连通图至少有k条边:


对于k个顶点和那一个孤立的第k+1个点,k个顶点之中任取一点,必然可以和那个孤立的点连接,此时有k+1条边,下面只需证明现在这个加入这条边后的图是连通图:由于k个顶点组成的图是连通图,说明k中任意两点都有路径相同,因此只需证明那个孤立的点与k个顶点都有路径相通,由于那个孤立的点与之前取的顶点直接相连,孤立的点必定可以访问余下的k-1个顶点。所以证明成立


所以题目说对于2021个顶点,取(所谓的装饰)2020条边就可以保证连通,是合理的。


现在在谈最小生成树,那要先知道生成树定义:对于有n个顶点的连通图,只有n-1条边的连通子图就是它的生成树。(既然是树就不可能存在环)


所以简言之,生成树就是以最少的边(n-1)条边来连接所有顶点的图。但是:


fffaa29dca6a4078b058627078277ccc.png


生成树不唯一(取的边的组合不唯一),当我们赋予了边的权值时,所有边的权值的和也就必然有一个最小值。即最小生成树


前面提到,一共有C(2021,2)条边,我们要做的就是取2020条边,保证顶点连通的同时确保边权值和最小。而kruskal算法就保证了以上两点要求:连通性,最小权值和。


https://www.bilibili.com/video/BV1PW411877b

https://www.bilibili.com/video/BV1PW411877b

建议去看一下这个视频,有助于理解。


kruskal的主要内容是并查集和贪心,对此不熟悉的同学可以先去洛谷做一下亲戚那道题

传送门

https://www.luogu.com.cn/problem/P1551


配套相应的视频花一个下午的时间即可掌握并查集。


下面阐述kruskal的基本算法思想,创建边的数组(i,j,weihgt),按照边的权值排序(贪心),然后,初始化各个顶点作为一个独立的集合(并查集思想),遍历边(贪心),如果i和j不在同一集合,意味着i,j不连通(并查集),对应的边应当取过来,权值和累加一次,否则如果i和j在同一集合(已经连通),意味着这条边不应取过来...直至取完n-1条边,只剩下一个集合,这个集合包含所有点(连通性)那么最终的权值和一定是最小的(最小权值和)。

如果想知道数学证明的可以点这里,也可以和小郑一样暂时把这个记下来~

https://zhuanlan.zhihu.com/p/340628568

#连通网:最小生成树
#定义获取两城邦权值函数
parent=[i for i in range(0,2022)]#初始化祖先
def find_root(x):#查找集合[路径压缩]
    if x!=parent[x]:
        parent[x]=find_root(parent[x])
    return parent[x]
def union(x,y):#合并集合
    x_root,y_root=find_root(x),find_root(y)
    if x_root!=y_root:
        parent[x_root]=y_root
def get_weight(x,y):#获取权值
    a='0'*(4-len(str(x)))+str(x)
    b='0'*(4-len(str(y)))+str(y)
    s=0
    for i in range(4):
        if a[i]!=b[i]:
            s+=int(a[i])+int(b[i])
    return s
edge=[]#创建边集(i,j,weight)
for i in range(1,2022):
    for j in range(1,2022):
        edge.append((i,j,get_weight(i,j)))
edge.sort(key=lambda x:x[2])#关键字排序
count=0
j=1
for i in edge:
    try:
        if find_root(i[0])!=find_root(i[1]) and j<=2020:#不处在同一连通分量(集合)且点数未达到2021-1
            count+=i[2]#累加
            union(i[0],i[1])#合并
            j+=1
    except:#检查报错点
        print(i[0],i[1])
        break
print(count)#答案是4046

我是小郑 正在奔赴热爱奔赴山海

相关文章
|
算法 Go Python
CSP 201703-4 地铁修建 python 最小生成树,并查集
CSP 201703-4 地铁修建 python 最小生成树,并查集
CSP 201703-4 地铁修建 python 最小生成树,并查集
|
算法 Python 内存技术
【python算法】图论之Kruskal求最小生成树模板
【python算法】图论之Kruskal求最小生成树模板
【python算法】图论之Kruskal求最小生成树模板
|
算法 Python
Python之最小生成树 kruskal
Python之最小生成树 kruskal
128 0
Python之最小生成树 kruskal
|
15天前
|
安全 数据处理 开发者
Python中的多线程编程:从入门到精通
本文将深入探讨Python中的多线程编程,包括其基本原理、应用场景、实现方法以及常见问题和解决方案。通过本文的学习,读者将对Python多线程编程有一个全面的认识,能够在实际项目中灵活运用。
|
9天前
|
设计模式 开发者 Python
Python编程中的设计模式:工厂方法模式###
本文深入浅出地探讨了Python编程中的一种重要设计模式——工厂方法模式。通过具体案例和代码示例,我们将了解工厂方法模式的定义、应用场景、实现步骤以及其优势与潜在缺点。无论你是Python新手还是有经验的开发者,都能从本文中获得关于如何在实际项目中有效应用工厂方法模式的启发。 ###
|
2天前
|
存储 人工智能 数据挖掘
从零起步,揭秘Python编程如何带你从新手村迈向高手殿堂
【10月更文挑战第32天】Python,诞生于1991年的高级编程语言,以其简洁明了的语法成为众多程序员的入门首选。从基础的变量类型、控制流到列表、字典等数据结构,再到函数定义与调用及面向对象编程,Python提供了丰富的功能和强大的库支持,适用于Web开发、数据分析、人工智能等多个领域。学习Python不仅是掌握一门语言,更是加入一个充满活力的技术社区,开启探索未知世界的旅程。
12 5
|
2天前
|
人工智能 数据挖掘 开发者
探索Python编程:从基础到进阶
【10月更文挑战第32天】本文旨在通过浅显易懂的语言,带领读者从零开始学习Python编程。我们将一起探索Python的基础语法,了解如何编写简单的程序,并逐步深入到更复杂的编程概念。文章将通过实际的代码示例,帮助读者加深理解,并在结尾处提供练习题以巩固所学知识。无论你是编程新手还是希望提升编程技能的开发者,这篇文章都将为你的学习之旅提供宝贵的指导和启发。
|
14天前
|
弹性计算 安全 小程序
编程之美:Python让你领略浪漫星空下的流星雨奇观
这段代码使用 Python 的 `turtle` 库实现了一个流星雨动画。程序通过创建 `Meteor` 类来生成具有随机属性的流星,包括大小、颜色、位置和速度。在无限循环中,流星不断移动并重新绘制,营造出流星雨的效果。环境需求为 Python 3.11.4 和 PyCharm 2023.2.5。
|
7天前
|
数据处理 Python
从零到英雄:Python编程的奇幻旅程###
想象你正站在数字世界的门槛上,手中握着一把名为“Python”的魔法钥匙。别小看这把钥匙,它能开启无限可能的大门,引领你穿梭于现实与虚拟之间,创造属于自己的奇迹。本文将带你踏上一场从零基础到编程英雄的奇妙之旅,通过生动有趣的比喻和实际案例,让你领略Python编程的魅力,激发内心深处对技术的渴望与热爱。 ###
|
10天前
|
数据采集 机器学习/深度学习 人工智能
Python编程入门:从基础到实战
【10月更文挑战第24天】本文将带你进入Python的世界,从最基础的语法开始,逐步深入到实际的项目应用。我们将一起探索Python的强大功能和灵活性,无论你是编程新手还是有经验的开发者,都能在这篇文章中找到有价值的内容。让我们一起开启Python的奇妙之旅吧!