无向图与有向图的全部生成树的算法 源代码

以下是Prim算法和Kruskal算法生成无向图的最小生成树的代码：

Prim算法：

import heapq

def prim(graph):
    n = len(graph)
    visited = [False] * n
    min_heap = [(0, 0)] # (cost, vertex)
    mst_cost = 0
    mst_edges = []

    while min_heap:
        cost, u = heapq.heappop(min_heap)
        if visited[u]:
            continue
        visited[u] = True
        mst_cost += cost
        if u != 0:
            mst_edges.append((u, parent))
        for v, w in graph[u]:
            if not visited[v]:
                heapq.heappush(min_heap, (w, v))
    return mst_cost, mst_edges

Kruskal算法：

def kruskal(graph):
    n = len(graph)
    parent = list(range(n))
    rank = [0] * n
    mst_cost = 0
    mst_edges = []

    def find(u):
        if parent[u] != u:
            parent[u] = find(parent[u])
        return parent[u]

    def union(u, v):
        pu, pv = find(u), find(v)
        if pu == pv:
            return False
        if rank[pu] < rank[pv]:
            parent[pu] = pv
        elif rank[pu] > rank[pv]:
            parent[pv] = pu
        else:
            parent[pv] = pu
            rank[pu] += 1
        return True

    edges = []
    for u in range(n):
        for v, w in graph[u]:
            edges.append((w, u, v))
    edges.sort()

    for w, u, v in edges:
        if union(u, v):
            mst_cost += w
            mst_edges.append((u, v))
    return mst_cost, mst_edges

下面是Prim算法和Kruskal算法生成有向图的最小生成树的代码：

Prim算法：

import heapq

def prim(graph):
    n = len(graph)
    visited = [False] * n
    min_heap = [(0, 0, -1)] # (cost, vertex, parent)
    mst_cost = 0
    mst_edges = []

    while min_heap:
        cost, u, parent = heapq.heappop(min_heap)
        if visited[u]:
            continue
        visited[u] = True
        mst_cost += cost
        if parent != -1:
            mst_edges.append((parent, u))
        for v, w in graph[u]:
            if not visited[v]:
                heapq.heappush(min_heap, (w, v, u))
    return mst_cost, mst_edges

Kruskal算法：

def kruskal(graph):
    n = len(graph)
    parent = list(range(n))
    rank = [0] * n
    mst_cost = 0
    mst_edges = []

    def find(u):
        if parent[u] != u:
            parent[u] = find(parent[u])
        return parent[u]

    def union(u, v):
        pu, pv = find(u), find(v)
        if pu == pv:
            return False
        if rank[pu] < rank[pv]:
            parent[pu] = pv
        elif rank[pu] > rank[pv]:
            parent[pv] = pu
        else:
            parent[pv] = pu
            rank[pu] += 1
        return True

    edges = []
    for u in range(n):
        for v, w in graph[u]:
            edges.append((w, u, v))
    edges.sort()

    for w, u, v in edges:
        if union(u, v):
            mst_cost += w
            mst_edges.append((u, v))
    return mst_cost, mst_edges

以上是Prim算法和Kruskal算法生成无向图和有向图的最小生成树的代码，希望对你有帮助！