普利姆算法和克鲁斯卡尔算法

### 普里姆算法与克鲁斯卡尔算法对比

#### 算法原理差异
普里姆算法的核心在于每一步都形成一棵树。这意味着在整个执行过程中，所选边总是会将新的顶点加入到现有的单棵树结构中[^1]。与此不同的是，克鲁斯卡尔算法在处理图的过程中可能会暂时创建多棵独立的小树（即森林），直到最终这些小树通过合适的边相互连接成为完整的最小生成树。

#### 数据结构需求
对于普里姆算法而言，通常采用优先队列来高效选取下一个要添加至当前树中的节点；而对于克鲁斯卡尔算法，则更倾向于利用并查集数据结构来进行高效的连通性检测以及循环预防操作。

#### 时间复杂度分析
两种算法的时间性能取决于具体实现方式及其适用条件。当面对稠密图时，由于每次迭代都需要更新大量候选边的信息，因此基于斐波那契堆优化后的普里姆算法能够展现出较好的效率表现。然而，在稀疏图场景下，如果可以预先对所有边按权重排序的话，那么克鲁斯卡尔算法则能凭借其简单的贪心策略获得更快的速度优势。

#### 应用场景举例
- **网络设计问题**：假设某公司计划铺设光纤通信线路覆盖全国主要城市，并希望总成本最低。此时可考虑使用普里姆算法从任一选定起点出发逐步扩展最优路径直至遍历全部目标地点。

- **电路板布线规划**：电子设备内部PCB布局往往涉及众多元件间的电气连接关系。为了确保信号传输质量同时减少材料消耗，工程师们可以选择应用克鲁斯卡尔算法寻找全局范围内代价最少的一组导线配置方案。

def prim_mst(graph):
    import heapq
    
    mst = []
    visited = set()
    
    start_vertex = list(graph.keys())[0]
    edges = [(weight, start_vertex, neighbor) for neighbor, weight in graph[start_vertex].items()]
    heapq.heapify(edges)

    while edges:
        weight, u, v = heapq.heappop(edges)
        
        if v not in visited:
            visited.add(v)
            mst.append((u, v, weight))
            
            for next_node, w in graph[v].items():
                if next_node not in visited:
                    heapq.heappush(edges, (w, v, next_node))

    return mst


def kruskal_mst(edges, num_vertices):
    parent = {i: i for i in range(num_vertices)}
    rank = dict.fromkeys(range(num_vertices), 0)
    result = []

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

    def union(x, y):
        rootX = find(x)
        rootY = find(y)
        if rootX != rootY:
            if rank[rootX] > rank[rootY]:
                parent[rootY] = rootX
            elif rank[rootX] < rank[rootY]:
                parent[rootX] = rootY
            else:
                parent[rootY] = rootX
                rank[rootX] += 1
                
    sorted_edges = sorted(edges, key=lambda item:item[2])

    for edge in sorted_edges:
        u, v, weight = edge
        
        if find(u) != find(v):
            result.append(edge)
            union(u,v)

    return result