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
|
5天前
|
存储 数据挖掘 开发者
Python编程入门:从零到英雄
在这篇文章中,我们将一起踏上Python编程的奇幻之旅。无论你是编程新手,还是希望拓展技能的开发者,本教程都将为你提供一条清晰的道路,引导你从基础语法走向实际应用。通过精心设计的代码示例和练习,你将学会如何用Python解决实际问题,并准备好迎接更复杂的编程挑战。让我们一起探索这个强大的语言,开启你的编程生涯吧!
|
11天前
|
机器学习/深度学习 人工智能 TensorFlow
人工智能浪潮下的自我修养:从Python编程入门到深度学习实践
【10月更文挑战第39天】本文旨在为初学者提供一条清晰的道路,从Python基础语法的掌握到深度学习领域的探索。我们将通过简明扼要的语言和实际代码示例,引导读者逐步构建起对人工智能技术的理解和应用能力。文章不仅涵盖Python编程的基础,还将深入探讨深度学习的核心概念、工具和实战技巧,帮助读者在AI的浪潮中找到自己的位置。
|
11天前
|
机器学习/深度学习 数据挖掘 Python
Python编程入门——从零开始构建你的第一个程序
【10月更文挑战第39天】本文将带你走进Python的世界,通过简单易懂的语言和实际的代码示例,让你快速掌握Python的基础语法。无论你是编程新手还是想学习新语言的老手,这篇文章都能为你提供有价值的信息。我们将从变量、数据类型、控制结构等基本概念入手,逐步过渡到函数、模块等高级特性,最后通过一个综合示例来巩固所学知识。让我们一起开启Python编程之旅吧!
|
11天前
|
存储 Python
Python编程入门:打造你的第一个程序
【10月更文挑战第39天】在数字时代的浪潮中,掌握编程技能如同掌握了一门新时代的语言。本文将引导你步入Python编程的奇妙世界,从零基础出发,一步步构建你的第一个程序。我们将探索编程的基本概念,通过简单示例理解变量、数据类型和控制结构,最终实现一个简单的猜数字游戏。这不仅是一段代码的旅程,更是逻辑思维和问题解决能力的锻炼之旅。准备好了吗?让我们开始吧!
|
2天前
|
数据采集 存储 数据处理
Python中的多线程编程及其在数据处理中的应用
本文深入探讨了Python中多线程编程的概念、原理和实现方法,并详细介绍了其在数据处理领域的应用。通过对比单线程与多线程的性能差异,展示了多线程编程在提升程序运行效率方面的显著优势。文章还提供了实际案例,帮助读者更好地理解和掌握多线程编程技术。
|
5天前
|
存储 人工智能 数据挖掘
Python编程入门:打造你的第一个程序
本文旨在为初学者提供Python编程的初步指导,通过介绍Python语言的基础概念、开发环境的搭建以及一个简单的代码示例,帮助读者快速入门。文章将引导你理解编程思维,学会如何编写、运行和调试Python代码,从而开启编程之旅。
27 2
|
6天前
|
存储 Python
Python编程入门:理解基础语法与编写简单程序
本文旨在为初学者提供一个关于如何开始使用Python编程语言的指南。我们将从安装Python环境开始,逐步介绍变量、数据类型、控制结构、函数和模块等基本概念。通过实例演示和练习,读者将学会如何编写简单的Python程序,并了解如何解决常见的编程问题。文章最后将提供一些资源,以供进一步学习和实践。
17 1
下一篇
无影云桌面