python随机给定一个无向加权图，包含 n 个顶点和 m 条边，设计一个算法来找出一棵最小生成树，也就是将所有的顶点连接在一起，并使得所有的边的权重总和最小。

这是一个经典的最小生成树问题，可以使用 Kruskal 或 Prim 算法来解决。

1. Kruskal 算法

Kruskal 算法是一种基于贪心策略的最小生成树算法，其基本思想是按照边权值从小到大选择边，并且在选择过程中保证不会形成环。具体步骤如下：

（1）将所有边按照权重从小到大排序。

（2）依次将每条边加入生成树中，如果加入该边后会形成环，则不加入。直到生成树中包含 n-1 条边为止。

Python 代码如下：

def kruskal(n, edges):
    # 初始化并查集
    parent = [i for i in range(n)]
    rank = [0] * n

    # 定义查找祖先节点的函数
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    # 定义合并集合的函数
    def union(x, y):
        x_root, y_root = find(x), find(y)
        if x_root == y_root:
            return False
        elif rank[x_root] < rank[y_root]:
            parent[x_root] = y_root
        elif rank[x_root] > rank[y_root]:
            parent[y_root] = x_root
        else:
            parent[y_root] = x_root
            rank[x_root] += 1
        return True

    # 将边按照权重从小到大排序
    edges.sort(key=lambda edge: edge[2])

    # 初始化生成树和边权值总和
    mst, weight = [], 0

    # 依次加入每条边
    for edge in edges:
        if union(edge[0], edge[1]):
            mst.append(edge)
            weight += edge[2]
            if len(mst) == n - 1:
                break

    return mst, weight

2. Prim 算法

Prim 算法也是一种基于贪心策略的最小生成树算法，其基本思想是从一个起始点开始，每次选择与当前生成树相邻且权重最小的边，并将该点加入生成树中。具体步骤如下：

（1）选择一个起始点，将该点加入生成树中。

（2）将该点的所有出边加入优先队列中。

（3）从队列中取出权重最小的边，如果该边的终点不在生成树中，则将该点加入生成树中，并将该点的所有出边加入队列中。

（4）重复步骤（3），直到生成树中包含 n 个点为止。

Python 代码如下：

import heapq

def prim(n, edges):
    # 构建邻接表
    graph = [[] for _ in range(n)]
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))

    # 初始化起始点和优先队列
    start = 0
    visited = set([start])
    pq = [(w, start, v) for v, w in graph[start]]

    # 初始化生成树和边权值总和
    mst, weight = [], 0

    # 依次加入每个点
    while len(mst) < n - 1:
        # 取出权重最小的边
        w, u, v = heapq.heappop(pq)
        if v not in visited:
            # 将该点加入生成树中
            visited.add(v)
            mst.append((u, v, w))
            weight += w
            # 将该点的所有出边加入队列中
            for next_v, next_w in graph[v]:
                if next_v not in visited:
                    heapq.heappush(pq, (next_w, v, next_v))

    return mst, weight

注意，以上两种算法都需要用到并查集或优先队列来管理边或点，时间复杂度为 O(mlogm) 或 O(mlogn)，其中 m 是边数，n 是点数。