Kruskal算法

一种贪心算法，从最小的边开始遍历，并用并查集判断是否为同一个路径内

代码

# 并查集
def find(parent, node):
    if parent[node] != node:
        parent[node] = find(parent, parent[node])
    return parent[node]

def union(parent, rank, node1, node2):
    root1 = find(parent, node1)
    root2 = find(parent, node2)

    if root1 != root2:
        if rank[root1] > rank[root2]:
            parent[root2] = root1
        elif rank[root1] < rank[root2]:
            parent[root1] = root2
        else:
            parent[root2] = root1
            rank[root1] += 1

def kruskal(graph):
    min_spanning_tree = []
    edges = []

    for node, neighbors in graph.items():
        for neighbor, weight in neighbors.items():
            edges.append((weight, node, neighbor))

    edges.sort()

    parent = {node: node for node in graph}
    rank = {node: 0 for node in graph}

    for edge in edges:
        weight, node1, node2 = edge
        if find(parent, node1) != find(parent, node2):
            union(parent, rank, node1, node2)
            min_spanning_tree.append((weight, node1, node2))

    return min_spanning_tree

Prim算法

代码

#G是路径图，s是开始点
def prim(G, s):
    P, Q = {}, [(0, None, s)]
    while Q:
        w, p, u = heappop(Q)
        if u in P: continue # 如果目标点在生成树中，跳过
        P[u] = p # 记录目标点不在生成树中
        for v, w in G[u].items():
            heappush(Q, (w, u, v)) # 将u点的出边入堆
    return P
# T = prim(G, 1)
# sum_count = 0
# for k, v in T.items():
# if v !=None:
# sum_count += G[k][v]
#
# print(sum_count)
# print(T)
# 结果为19
# {1: None, 2: 1, 3: 1, 4: 3, 5: 6, 6: 4}