编辑“︁Prim算法”︁（章节）

= Prim算法 =

'''Prim算法'''是一种用于在加权无向图中寻找'''最小生成树'''（Minimum Spanning Tree, MST）的贪心算法。最小生成树是指一个连通图的子图，它包含原图的所有顶点，且所有边的权重之和最小，同时不包含任何环路。Prim算法由数学家[[罗伯特·普里姆]]（Robert C. Prim）于1957年提出，适用于稠密图（边较多的图）。

== 算法思想 ==
Prim算法的核心思想是从一个初始顶点出发，逐步扩展生成树，每次选择连接生成树和非生成树顶点的最小权重边，直到所有顶点都被包含在生成树中。具体步骤如下：

1. 初始化：选择一个起始顶点，将其加入生成树。
2. 重复以下步骤，直到所有顶点都被包含：
   - 在所有连接生成树和非生成树顶点的边中，选择权重最小的边。
   - 将该边及其连接的顶点加入生成树。

== 算法实现 ==
Prim算法可以通过优先队列（最小堆）高效实现，时间复杂度为<math>O(E \log V)</math>，其中<math>E</math>是边数，<math>V</math>是顶点数。

以下是使用Python实现的Prim算法示例：

<syntaxhighlight lang="python">
import heapq

def prim(graph, start):
    mst = []
    visited = set([start])
    edges = [
        (cost, start, to)
        for to, cost in graph[start].items()
    ]
    heapq.heapify(edges)
    
    while edges:
        cost, frm, to = heapq.heappop(edges)
        if to not in visited:
            visited.add(to)
            mst.append((frm, to, cost))
            for to_next, cost_next in graph[to].items():
                if to_next not in visited:
                    heapq.heappush(edges, (cost_next, to, to_next))
    return mst

# 示例图的邻接表表示
graph = {
    'A': {'B': 2, 'D': 6},
    'B': {'A': 2, 'C': 3, 'D': 8},
    'C': {'B': 3, 'D': 7, 'E': 4},
    'D': {'A': 6, 'B': 8, 'C': 7, 'E': 5},
    'E': {'C': 4, 'D': 5}
}

mst = prim(graph, 'A')
print("最小生成树的边：")
for edge in mst:
    print(f"{edge[0]} -- {edge[1]} (权重: {edge[2]})")
</syntaxhighlight>

'''输入：'''
邻接表表示的图，其中顶点为<code>'A'</code>到<code>'E'</code>，边权重如下：
* <code>'A'</code>与<code>'B'</code>相连，权重为2；<code>'A'</code>与<code>'D'</code>相连，权重为6。
* <code>'B'</code>与<code>'C'</code>相连，权重为3；<code>'B'</code>与<code>'D'</code>相连，权重为8。
* <code>'C'</code>与<code>'D'</code>相连，权重为7；<code>'C'</code>与<code>'E'</code>相连，权重为4。
* <code>'D'</code>与<code>'E'</code>相连，权重为5。

'''输出：'''
<pre>
最小生成树的边：
A -- B (权重: 2)
B -- C (权重: 3)
C -- E (权重: 4)
E -- D (权重: 5)
</pre>

== 算法可视化 ==
以下是用Mermaid绘制的Prim算法执行过程示意图：

<mermaid>
graph TD
    A((A)) --2--> B((B))
    B --3--> C((C))
    C --4--> E((E))
    E --5--> D((D))
</mermaid>

== 实际应用 ==
Prim算法在许多领域有广泛应用，例如：
1. '''网络设计'''：在计算机网络或电信网络中，Prim算法可用于设计成本最低的连接方案。
2. '''电路布线'''：在电子电路设计中，Prim算法帮助优化导线布局以减少材料成本。
3. '''交通规划'''：在城市道路或铁路规划中，Prim算法可用于确定连接所有地点的最短路径。

== 与Kruskal算法的比较 ==
Prim算法和[[Kruskal算法]]都是求解最小生成树的经典算法，但有以下区别：
* '''Prim算法'''基于顶点扩展，适合稠密图（边较多）。
* '''Kruskal算法'''基于边排序，适合稀疏图（边较少）。

== 时间复杂度分析 ==
Prim算法的时间复杂度取决于实现方式：
* 使用邻接矩阵和普通数组：<math>O(V^2)</math>。
* 使用邻接表和二叉堆：<math>O(E \log V)</math>。
* 使用斐波那契堆：<math>O(E + V \log V)</math>。

== 总结 ==
Prim算法是一种高效的贪心算法，用于求解加权无向图的最小生成树。通过逐步选择最小权重边扩展生成树，Prim算法能够快速找到最优解，适用于稠密图。理解Prim算法有助于解决实际中的网络优化问题。

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:图论算法]]