Python教程

Python教程 Python特性 Python的历史 Python应用程序 Python安装 Python示例 Python变量 Python数据类型 Python的关键词 Python文字 Python运营商 Python的评论 Python If else Python循环 Python For循环 Python While循环 Python打破 Python继续 Python通过 Python字符串 Python列表 Python元组 Python列表Vs元组 Python集 Python字典 Python函数 Python内置函数 Python Lambda函数 Python文件I/O Python模块 Python的例外 Python的日期 Python正则表达式 Python发送邮件读取CSV文件写入CSV文件读取Excel文件写Excel文件 Python断言 Python列表推导 Python Collection模块 Python数学模块 Python OS模块 Python随机模块 Python统计模块 Python Sys模块 Python ide Python数组命令行参数 Python魔法方法 Python Stack & Queue PySpark MLlib Python装饰 Python发电机使用Python进行网页抓取 Python JSON 出现Python Itertools Python多处理如何用地理位置法计算两点之间的距离 Python中的Gmail API 如何在Python中使用folium包绘制谷歌地图 Python中的网格搜索 Python高阶函数 Python中的nsetools Python程序查找第n个斐波那契数 Python OpenCV对象检测 Python SimpleImputer模块 Python中的第二大数字

Python哦

Python oop概念 Python对象类 Python的构造函数 Python继承 Python中的抽象

Python MySQL

环境设置数据库连接创建新数据库创建表插入操作读操作更新操作连接操作执行事务

Python MongoDB

Python SQLite

Python的问题

Python Tkinter (GUI)

Python网页拦截器

介绍构建Python脚本 Linux下的脚本部署 Windows部署脚本

Python MCQ

Python MCQ Python MCQ第2部分

Python程序

下一个→ ←上一页

Kruskal算法在Python中的实现

加权无向图的最小生成树可以用克鲁斯卡方法．在所有可能的生成树中最小生成树是一种张成图上每个顶点并且总权值最低的方法。

该算法的工作原理是对图中所有的边按其权值的递增顺序排序，如果添加的边没有形成一个循环，则逐个将这些边添加到最小生成树中。直到所有的顶点都连接起来。

Kruskal算法的步骤

以下是Kruskal算法的步骤:

排序图中所有边的权重按递增顺序排列。
创建一个新的空集来表示最小生成树。
遍历排序过的边列表中的每条边。
检查向最小生成树添加边是否会生成一个循环。如果不是，就把这条边加入最小生成树。重复直到每个顶点都连接起来。

克鲁斯卡算法时间复杂度是O(E log E),在那里E的数量是多少?边缘在图中。这使得它成为寻找大型图的最小生成树的一个非常有效的算法。

Kruskal算法在python中的实现

逐步实现可以描述如下:

我们定义了一个带有三个实例变量的Graph类:顶点，它是图中所有顶点的列表;边缘，它是图中所有边的列表;和adjacency_list，它是表示图的邻接表的字典。
我们定义一个方法add_edge向图中添加一条边。这个方法有三个参数:u和v，即这条边所连接的顶点;和重量，也就是边的权值。我们将这条边添加到边列表中同时也将它添加到adjacency_list．
我们定义一个方法find_parent找到一个给定顶点的父结点我在不相交集数据结构中。方法跟踪图的连接元素disjoint-set数据结构。每个顶点最初都是它自己的父顶点，我们使用find_parent方法查找属于的已连接组件的根目录我．
我们定义了一个方法union来合并不相交集数据结构中的两个连通的组件。union方法接受四个参数:父，它是一个字典，表示每个顶点的父节点;排名，它是一个表示每个顶点秩的字典;x和y，即我们想要合并其连通分量的顶点。我们使用find_parent方法找到属于x和y的连通分量的根，然后根据它们的秩合并这些分量。
我们定义a克鲁斯卡尔实现Kruskal算法的方法。该方法初始化一个空集minimum_spanning_tree将边存储在最小生成树中。它还为disjoint-set初始化父字典和秩字典。

代码:

            类图:def __init__(self，顶点):self。顶点=顶点self。edge = [] self。adjacency_list= {v: [] for v in vertices} def add_edge(self, u, v, weight): self.edges.append((u, v, weight)) self.adjacency_list[u].append((v, weight)) self.adjacency_list[v].append((u, weight)) def find_parent(self, parent, i): if parent[i] == i: return i return self.find_parent(parent, parent[i]) def union(self, parent, rank, x, y): root_x = self.find_parent(parent, x) root_y = self.find_parent(parent, y) if rank[root_x] < rank[root_y]: parent[root_x] = root_y elif rank[root_x] > rank[root_y]: parent[root_y] = root_x else: parent[root_y] = root_x rank[root_x] += 1 def kruskal(self): minimum_spanning_tree = set() parent = {} rank = {} for v in self.vertices: parent[v] = v rank[v] = 0 sorted_edges = sorted(self.edges, key=lambda x: x[2]) for edge in sorted_edges: u, v, weight = edge root_u = self.find_parent(parent, u) root_v = self.find_parent(parent, v) if root_u != root_v: minimum_spanning_tree.add(edge) self.union(parent, rank, root_u, root_v) return minimum_spanning_tree vertices = [0, 1, 2, 3] g = Graph(vertices) g.add_edge(0, 1, 5) g.add_edge(0, 2, 10) g.add_edge(0, 3, 3) g.add_edge(1, 3, 1) g.add_edge(2, 3, 4) minimum_spanning_tree = g.kruskal() print(minimum_spanning_tree)
           

输出:

{(1,3,1)， (2,3,4)， (0,3,3)}

输入图如下:

Kruskal的算法是贪婪算法求一个连通的加权图的最小生成树。

这个集合表示输入图的最小生成树中的边。我们可以看到最小生成树的总权值是1 + 3 + 5 = 9．

该算法的工作原理是按权值对图中的边进行排序，然后从权值最小的边开始，将这些边依次添加到最小生成树中。
当每条边被添加到最小生成树时，它被检查以确保它不会创建一个循环。如果这条边连接了两个已经在同一连接组件中的顶点，那么添加这条边将创建一个循环，并且这条边将被丢弃。
只要图是连通的，且边权不同，Kruskal的方法总是能识别出图的最小生成树。
的时间复杂度Kruskal的算法是O(E log E)在哪里E的数量是多少?边缘在图中。这是因为该算法需要按权重对边进行排序，这需要O(E log E)时间，然后逐个处理每条边，这需要O (E)
的空间复杂度Kruskal的算法是O(v + e),在那里V的数量是多少?顶点在图中E的数量是多少?边缘．这是因为该算法需要存储图的边和邻接表，以及用于跟踪连接组件的不相交集数据结构。
Kruskal的算法可以使用优先级队列来更有效地按权重对边进行排序。它改进了算法时间复杂度来O(E log V),在那里V是图形的顶点然而,空间复杂度仍然是O(v + e)．
在某些情况下，对于给定的图可能有多个最小生成树。Kruskal的算法会找到其中一棵树，但不一定能找到所有树。

Kruskal算法常用于网络设计问题例如设计通信网络或电网。该算法也可以在python中使用优先级队列来实现:

代码:

            导入队列类图:def __init__(自，顶点):自。顶点=顶点self。edge = [] self。父= {} self.rank = {} for v in self.vertices: self.make_set(v) def add_edge(self, u, v, w): self.edges.append((w, u, v)) def make_set(self, v): self.parent[v] = v self.rank[v] = 0 def find(self, v): if self.parent[v] != v: self.parent[v] = self.find(self.parent[v]) return self.parent[v] def union(self, u, v): root1 = self.find(u) root2 = self.find(v) if root1 != root2: if self.rank[root1] > self.rank[root2]: self.parent[root2] = root1 else: self.parent[root1] = root2 if self.rank[root1] == self.rank[root2]: self.rank[root2] += 1 def kruskal(self): minimum_spanning_tree = set() # Sort edges by weight using priority queue edge_queue = queue.PriorityQueue() for edge in self.edges: edge_queue.put(edge) # Iterate through edges in priority queue and add to MST while not edge_queue.empty(): weight, u, v = edge_queue.get() if self.find(u) != self.find(v): self.union(u, v) minimum_spanning_tree.add((u, v, weight)) return minimum_spanning_tree # Create a graph with 5 vertices g = Graph([0, 1, 2, 3, 4]) # Add edges to the graph g.add_edge(0, 1, 2) g.add_edge(0, 2, 3) g.add_edge(0, 3, 6) g.add_edge(1, 2, 5) g.add_edge(1, 4, 3) g.add_edge(2, 3, 1) g.add_edge(2, 4, 4) g.add_edge(3, 4, 5) # Find the minimum spanning tree mst = g.kruskal() # Print the edges in the minimum spanning tree for edge in mst: print(edge)
           

输出:

(2,3,1) (0,2,3) (0,1,2) (1,4,3)

这些是上面同一个图的最小生成树中的边。

在这个实现中，我们使用优先队列来排序边的权重。我们将每条边添加到优先级队列中重量作为优先级，这样当我们从队列中检索边时，我们总是首先获得权值最小的边。之后，我们遍历优先级队列中的边，并将它们逐个添加到最小生成树中，只要它们不产生循环。我们用。来跟踪图的连通分量找到和联盟的方法的disjoint-set数据结构，就像前面的实现一样。

要使用此实现，您需要创建一个图形对象，添加边使用add_edge方法，然后调用克鲁斯卡尔找到最小生成树的方法。

下一个话题在Python中模拟外部API

←上一页下一个→