TreeNode類通常用于表示樹結構中的節點,而最小生成樹算法通常使用其他數據結構來實現,例如Prim算法和Kruskal算法。
下面是一個簡單的示例代碼,用于實現Prim算法來生成最小生成樹:
import heapq
class TreeNode:
def __init__(self, val):
self.val = val
self.children = []
def prim(graph):
n = len(graph)
visited = [False] * n
min_heap = [(0, 0, None)] # (cost, node, parent)
mst = [None] * n
while min_heap:
cost, node, parent = heapq.heappop(min_heap)
if visited[node]:
continue
visited[node] = True
if parent is not None:
mst[node] = parent.children.append(TreeNode(node))
for neighbor, weight in graph[node]:
if not visited[neighbor]:
heapq.heappush(min_heap, (weight, neighbor, node))
return mst
在這個示例中,我們使用TreeNode類來表示最小生成樹的節點,使用prim函數來實現Prim算法。通過傳入一個鄰接表形式的圖數據結構,我們可以生成最小生成樹的節點。