最小生成樹(Minimum Spanning Tree,簡稱 MST)問題是圖論中的一個經典問題,它在各種實際應用中都有廣泛的用途。在這里,我將圍繞著最小生成樹問題的背景、兩種主要的算法(Prim算法和Kruskal算法),以及如何實現它們來解決最小生成樹問題進行詳細講解。
背景: 最小生成樹問題是指在一個帶權重的無向連通圖中找到一個生成樹,使得這棵樹的所有邊的權重之和最小。
應用:
Prim算法的貪心性質: Prim算法是一種基于貪心策略的算法,它從一個初始節點開始,逐步向外擴展樹的規模,每次選擇連接樹和未連接部分的最小權重邊,直到覆蓋所有節點為止。
算法思路:
Kruskal算法的貪心性質: Kruskal算法也是基于貪心思想的算法,它按照邊的權重從小到大的順序逐步選擇邊,如果加入這條邊不構成環,則將其加入最小生成樹中。
算法思路:
import heapqdef prim(graph): min_span_tree = [] visited = set() start_node = list(graph.keys())[0] # 選擇任意一個節點作為起始節點 visited.add(start_node) candidate_edges = [(cost, start_node, to) for to, cost in graph[start_node]] heapq.heapify(candidate_edges) while candidate_edges: cost, frm, to = heapq.heappop(candidate_edges) if to not in visited: visited.add(to) min_span_tree.append((frm, to, cost)) for next_to, c in graph[to]: if next_to not in visited: heapq.heappush(candidate_edges, (c, to, next_to)) return min_span_tree# 示例圖的鄰接表表示graph = { 'A': [('B', 3), ('C', 1)], 'B': [('A', 3), ('C', 3), ('D', 6)], 'C': [('A', 1), ('B', 3), ('D', 4)], 'D': [('B', 6), ('C', 4)]}result_prim = prim(graph)print("Prim算法得到的最小生成樹邊集合:", result_prim)
class DisjointSet: def __init__(self, vertices): self.parent = {v: v for v in vertices} def find(self, vertex): if self.parent[vertex] != vertex: self.parent[vertex] = self.find(self.parent[vertex]) return self.parent[vertex] def union(self, u, v): self.parent[self.find(u)] = self.find(v)def kruskal(graph): edges = [] for frm in graph: for to, cost in graph[frm]: edges.append((cost, frm, to)) edges.sort() vertices = set() for frm, to, _ in edges: vertices.add(frm) vertices.add(to) min_span_tree = [] disjoint_set = DisjointSet(vertices) for cost, frm, to in edges: if disjoint_set.find(frm) != disjoint_set.find(to): min_span_tree.append((frm, to, cost)) disjoint_set.union(frm, to) return min_span_tree# 使用與Prim算法相同的示例圖的鄰接表表示graph = { 'A': [('B', 3), ('C', 1)], 'B': [('A', 3), ('C', 3), ('D', 6)], 'C': [('A', 1), ('B', 3), ('D', 4)], 'D': [('B', 6), ('C', 4)]}result_kruskal = kruskal(graph)print("Kruskal算法得到的最小生成樹邊集合:", result_kruskal)
以上是兩種算法的簡單實現示例,它們可以用來解決最小生成樹問題。通過閱讀代碼和理解算法思想,你可以深入學習和掌握最小生成樹問題及其解決方法。
本文鏈接:http://www.www897cc.com/showinfo-26-34627-0.html最小生成樹問題
聲明:本網頁內容旨在傳播知識,若有侵權等問題請及時與本網聯系,我們將在第一時間刪除處理。郵件:2376512515@qq.com
下一篇: 五分鐘 K8s 實戰-應用探針