6.6 最小生成树

[utterances-bot]

6.6 最小生成树

图的生成树知识 #1. 最小生成树的定义 生成树（Spanning Tree）：如果无向连通图 G 的一个子图是一棵包含图 G 所有顶点的树，则称该子图为 G 的生成树。生成树是连通图的包含图中的所有顶点的极小连通子图。图的生成树不惟一。从不同的顶点出发进行遍历，可以得到不同的生成树。

https://algo.itcharge.cn/06_graph/06_06_graph_minimum_spanning_tree/

[axax1134]

还有这里 会更新吗害

[SuPerMinOz]

还在等你

[KehaoC]

蹲

[HalfCheesee]

加油加油，没有几章的内容了呢！

[surpoloyang]

蹲蹲蹲，博主的内容对一个算法小白来说绝对精彩！

[Dolijun]

蹲代码实现

[Gregory616]

#这是AI生成的Prim算法

import heapq

def prim_mst(graph):
    """
    Implementation of Prim's algorithm to find the Minimum Spanning Tree (MST) of a graph.
    
    Args:
    - graph: adjacency list representation of the graph using dictionary
             Format: {vertex: [(neighbor, weight), ...]}
             
    Returns:
    - mst: adjacency list representation of the Minimum Spanning Tree using dictionary
           Format: {vertex: [(neighbor, weight), ...]}
    """
    mst = {}
    start_vertex = next(iter(graph))  # Start from any vertex
    
    visited = set([start_vertex])
    priority_queue = [(weight, start_vertex, neighbor) for neighbor, weight in graph[start_vertex]]
    heapq.heapify(priority_queue)
    
    while priority_queue:
        weight, u, v = heapq.heappop(priority_queue)
        
        if v not in visited:
            visited.add(v)
            if u in mst:
                mst[u].append((v, weight))
            else:
                mst[u] = [(v, weight)]
            
            if v in mst:
                mst[v].append((u, weight))
            else:
                mst[v] = [(u, weight)]
            
            for neighbor, weight in graph[v]:
                if neighbor not in visited:
                    heapq.heappush(priority_queue, (weight, v, neighbor))
    
    return mst

[qwangry]

chatgpt生成的Kruskal代码

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices  # 顶点数
        self.edges = []  # 边的集合

    def add_edge(self, u, v, weight):
        # 添加边，(u, v, weight) 表示顶点 u 和 v 之间的边以及权重
        self.edges.append((u, v, weight))

    def find(self, parent, node):
        # 查找集合的根节点，带路径压缩
        if parent[node] != node:
            parent[node] = self.find(parent, parent[node])
        return parent[node]

    def union(self, parent, rank, u, v):
        # 合并两个集合，使用按秩合并优化
        root_u = self.find(parent, u)
        root_v = self.find(parent, v)
        if rank[root_u] > rank[root_v]:
            parent[root_v] = root_u
        elif rank[root_u] < rank[root_v]:
            parent[root_u] = root_v
        else:
            parent[root_v] = root_u
            rank[root_u] += 1

    def kruskal(self):
        # Kruskal 算法主逻辑
        mst = []  # 存储最小生成树的边
        self.edges.sort(key=lambda edge: edge[2])  # 按边的权重从小到大排序

        parent = {}  # 记录每个顶点的父节点
        rank = {}  # 记录每个顶点的秩（用于按秩合并）

        # 初始化每个顶点为单独集合
        for vertex in range(self.vertices):
            parent[vertex] = vertex
            rank[vertex] = 0

        # 遍历排序后的边
        for edge in self.edges:
            u, v, weight = edge

            # 检查两个顶点是否属于不同的集合
            root_u = self.find(parent, u)
            root_v = self.find(parent, v)
            if root_u != root_v:
                # 不属于同一集合，将边加入最小生成树
                mst.append(edge)
                self.union(parent, rank, root_u, root_v)

            # 如果最小生成树的边数等于顶点数 - 1，停止
            if len(mst) == self.vertices - 1:
                break

        return mst


# 示例用法
if __name__ == "__main__":
    g = Graph(4)  # 创建一个图，4 个顶点
    g.add_edge(0, 1, 10)
    g.add_edge(0, 2, 6)
    g.add_edge(0, 3, 5)
    g.add_edge(1, 3, 15)
    g.add_edge(2, 3, 4)

    mst = g.kruskal()
    print("最小生成树的边及其权重：")
    for u, v, weight in mst:
        print(f"{u} -- {v} == {weight}")

[cabbagewyh]

还会更新吗 作者大大

[itcharge]

已经更新啦