利用kruskal算法求一个图的最小生成树,设计Kruskal算法求解邻接矩阵存储结构下图的最小生成树的函数,并以下图为例设计一个主函数进行测试,要求输出最小生成树的各顶点及各边的权值。

Kruskal算法是一种用于寻找无向加权图中最小生成树的贪心算法。它按照边的权重从小到大排序，然后依次加入这些边，直到形成一个连通的子图，并保证这个子图中每对顶点之间恰好有一条且仅有一条路径。

以下是用Python编写的一个基本的Kruskal算法实现，假设我们有一个二维列表表示邻接矩阵：

def kruskal(graph):
    # 初始化最小生成树结果
    mst = []
    # 边的集合，记录边已经被添加的情况
    edges_set = set()
    
    # 对所有边按权重升序排列
    edges = sorted((graph[u][v], u, v) for u in range(len(graph)) for v in range(u, len(graph)))
    
    for weight, u, v in edges:
        # 如果这条边还没被加入过最小生成树，就添加
        if (u, v) not in edges_set and (v, u) not in edges_set:
            mst.append((u, v, weight))
            edges_set.add((u, v))

    return mst

# 示例邻接矩阵
adj_matrix = [
    [0, 4, 0, 0],
    [4, 0, 8, 0],
    [0, 8, 0, 7],
    [0, 0, 7, 0]
]

# 将邻接矩阵转换为邻接列表形式，方便查找
graph = {i: [j for j, w in enumerate(adj_matrix[i]) if w > 0] for i in range(len(adj_matrix))}
mst = kruskal(graph)

def print_mst(mst):
    print("最小生成树的顶点和边及其权值:")
    for node_pair, weight in mst:
        print(f"节点({node_pair[0]}, {node_pair[1]}): 权重={weight}")

if __name__ == "__main__":
    print_mst(mst)

在这个例子中，`print_mst` 函数会打印出找到的最小生成树中的各个顶点以及对应的边和权值。运行这个主函数，你会得到对应给定邻接矩阵的最小生成树信息。