查看“︁普林姆算法”︁的源代码

{{Non-free|time=2020-04-08T23:35:53+00:00}}
{{noteTA
|T=zh-cn:普里姆算法; zh-tw:普林演算法;
|1=zh-cn:普里姆; zh-tw:普林;
|2=zh-cn:算法; zh-tw:演算法;
}}
{{图搜索算法}}
'''普里姆算法'''（{{lang-en|Prim's algorithm}}）是[[图论]]中的一种[[贪心算法|贪心]][[算法]]，可在一个加权连通图中找到其[[最小生成树]]。意即由此算法搜索到的[[邊 (圖論)|边]]子集所构成的[[树 (图论)|树]]中，不但包括了连通图里的所有[[顶点 (图论)|顶点]]，且其所有边的权值之和亦为最小。该算法于1930年由[[捷克]]数学家{{link-en|沃伊捷赫·亚尔尼克|Vojtěch Jarník}}发现；并在1957年由[[美国]]计算机科学家[[羅伯特·C·普里姆]]独立发现；1959年，[[艾兹格·迪科斯彻]]再次发现了该算法。因此，在某些场合，普里姆算法又被称为'''DJP算法'''、'''亚尔尼克算法'''或'''普里姆－亚尔尼克算法'''。

== 描述 ==

从单一[[顶点 (图论)|顶点]]开始，普里姆算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。

# 输入：一个加权连通图，其中[[顶点 (图论)|顶点]]集合为<math>V</math>，边集合为<math>E</math>；
# 初始化：<math>V_{\text{new}}=\{x\}</math>，其中<math>x</math>为集合<math>V</math>中的任一节点（起始点），<math>E_{\text{new}}=\{\}</math>；
# 重复下列操作，直到<math>V_{\text{new}}=V</math>：
## 在集合<math>E</math>中选取权值最小的边<math>(u,v)</math>，其中<math>u</math>为集合<math>V_{\text{new}}</math>中的元素，而<math>v</math>则是<math>V</math>中没有加入<math>V_{\text{new}}</math>的顶点（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
## 将<math>v</math>加入集合<math>V_{\text{new}}</math>中，将<math>(u,v)</math>加入集合<math>E_{\text{new}}</math>中；
# 输出：使用集合<math>V_{\text{new}}</math>和<math>E_{\text{new}}</math>来描述所得到的最小生成树。

== 时间复杂度 ==

{| class="wikitable"
! 最小边、权的数据结构 !! 时间复杂度（总计）
|-
| [[邻接矩阵]]、搜索 || <math>O(|V|^2)</math>
|-
| [[二叉堆]]（后文伪代码中使用的数据结构）、[[邻接表]] || <math>O((|V| + |E|) \log |V|) = O(|E| \log |V|)</math>
|-
| [[斐波那契堆]]、[[邻接表]] || <math>O(|E| + |V| \log |V|)</math>
|}

通过[[邻接矩阵]]图表示的简易实现中，找到所有最小权边共需<math>O(|V|^2)</math>的运行时间。使用简单的[[二叉堆]]与[[邻接表]]来表示的话，普里姆算法的运行时间则可缩减为<math>O(|E| \log |V|)</math>，其中<math>|E|</math>为连通图的边集大小，<math>|V|</math>为点集大小。如果使用较为复杂的[[斐波那契堆]]，则可将运行时间进一步缩短为<math>O(|E| + |V| \log |V|)</math>，这在连通图足够密集时（当<math>|E|</math>满足<math>\Omega(|V|\log |V|)</math>条件时），可较显著地提高运行速度。

== 例示 ==

{| class="wikitable" border=1 cellspacing=2 cellpadding=5 
! 图例 !! 说明 !! 不可选 !! 可选 !! 已选
|-
|[[File:Prim_Algorithm_0.svg|200px]]
|此为原始的加权连通图。每条边一侧的数字代表其权值。
| - 
| -
| -
|-
|[[File:Prim_Algorithm_1.svg|200px]]
|[[顶点 (图论)|顶点]]'''D'''被任意选为起始点。顶点'''A'''、'''B'''、'''E'''和'''F'''通过单条边与'''D'''相连。'''A'''是距离'''D'''最近的顶点，因此将'''A'''及对应边'''AD'''以高亮表示。
| C, G
| A, B, E, F
| D
|-
|[[File:Prim_Algorithm_2.svg|200px]]
|下一个顶点为距离'''D'''或'''A'''最近的顶点。'''B'''距'''D'''为9，距'''A'''为7，'''E'''距'''D'''為15，'''F'''距'''D'''為6。因此，'''F'''距'''D'''或'''A'''最近，因此将顶点'''F'''与相应边'''DF'''以高亮表示。
| C, G
| B, E, F
| A, D
|-
|[[File:Prim Algorithm 3.svg|200px]]
|算法继续重复上面的步骤。距离'''A'''为7的顶点'''B'''被高亮表示。
| C
| B, E, G
| A, D, F
|-
|[[File:Prim Algorithm 4.svg|200px]]
|在当前情况下，可以在'''C'''、'''E'''与'''G'''间进行选择。'''C'''距'''B'''为8，'''E'''距'''B'''为7，'''G'''距'''F'''为11。'''E'''最近，因此将顶点'''E'''与相应边'''BE'''高亮表示。
| 无
| C, E, G
| A, D, F, B
|-
|[[File:Prim Algorithm 5.svg|200px]]
|这里，可供选择的[[顶点 (图论)|顶点]]只有'''C'''和'''G'''。'''C'''距'''E'''为5，'''G'''距'''E'''为9，故选取'''C'''，并与边'''EC'''一同高亮表示。
| 无
| C, G
| A, D, F, B, E
|-
|[[File:Prim Algorithm 6.svg|200px]]
|顶点'''G'''是唯一剩下的顶点，它距'''F'''为11，距'''E'''为9，'''E'''最近，故高亮表示'''G'''及相应边'''EG'''。
| 无
| G
| A, D, F, B, E, C
|-
|[[File:Prim Algorithm 7.svg|200px]]
|现在，所有[[顶点 (图论)|顶点]]均已被选取，图中绿色部分即为连通图的[[最小生成树]]。在此例中，最小生成树的权值之和为39。
| 无
| 无
| A, D, F, B, E, C, G
|}

== 证明 ==

已知图G的边数量为numEdge, [[顶点 (图论)|顶点]]数量为numVert, prim生成的树为T<sub>0</sub>, 最小生成树（MST）为T<sub>min</sub>

则有，cost(T<sub>min</sub>)<=cost(T<sub>0</sub>)

设：
T<sub>0</sub> 的 numVert-1 条边按照权重由小到大排列依次为：e<sub>k<sub>1</sub></sub>, e<sub>k<sub>2</sub></sub>, e<sub>k<sub>3</sub></sub>, ..., e<sub>k<sub>n</sub></sub>

T<sub>min</sub> 的 numVert-1 条边按照权重由小到大排列依次为：e<sub>g<sub>1</sub></sub>, e<sub>g<sub>2</sub></sub>, e<sub>g<sub>3</sub></sub>, ..., e<sub>g<sub>n</sub></sub>

其中n=numVert-1

两棵树的边从小到大权重比较，设第一个属于 T<sub>0</sub> 但不属于 T<sub>min</sub> 的边为 e<sub>d<sub>1</sub></sub>, 连接该边的两个顶点为 (v<sub>s</sub>, v<sub>e<sub>1</sub></sub>)

同时存在第一个属于 T<sub>min</sub> 但不属于 T<sub>0</sub> 且以v<sub>s</sub>为[[顶点 (图论)|顶点]]的边，记为 e<sub>d<sub>2</sub></sub>, 连接该边的两个顶点为 (v<sub>s</sub>, v<sub>e<sub>2</sub></sub>)。

两个边的起点相同。由Prim算法性质可知，w(e<sub>d<sub>2</sub></sub>) >= w(e<sub>d<sub>1</sub></sub>)

此时，在 T<sub>min</sub> 中删除 e<sub>d<sub>2</sub></sub> ，添加 e<sub>d<sub>1</sub></sub>，边的数量和顶点数量均不变，且不存在环，因此得到新的生成树T<sub>new</sub>,且cost(T<sub>min</sub>)>=cost(T<sub>new</sub>)

又因为 T<sub>min</sub> 是MST 所以 cost(T<sub>min</sub>)=cost(T<sub>new</sub>)。

以此类推，cost(T<sub>min</sub>)=cost(T<sub>0</sub>)

T<sub>0</sub>是最小生成树， 得证.

== 各語言程序代码 ==
=== Pascal語言程序 ===
部分主程序段：
<syntaxhighlight lang="pascal" line="1">
procedure prim(v0:integer);
var
   lowcost,closest:array[1..maxn] of integer;
   i,j,k,min,ans:integer;

   for i:=1 to n do
    begin
     lowcost[i]:=cost[v0,i];
     closest[i]:=v0;
   end;
   for i:=1 to n-1 do
     begin
      min:=maxint;
      for j:=1 to n do
         if (lowcost[j]<min) and (lowcost[j]<>0) then
          begin
            min:=lowcost[j];
            k:=j;
         end;
      inc(ans, lowcost[k]);
      lowcost[k]:=0;
      for j:=1 to n do
         if cost[k,j]<lowcost[j] then
          begin
            lowcost[j]:=cost[k,j];
            closest[j]:=k;
         end;
   end;
 writeln(ans);
end;
</syntaxhighlight>

=== C语言代码 ===
<syntaxhighlight lang="cpp" style="overflow:hidden" line="1">

//来源：严蔚敏 吴伟民《数据结构(C语言版)》

void MiniSpanTree_PRIM (MGraph G, VertexType u) {
    /*  用普利姆算法從第u個頂點出發構造網G 的最小生成樹T,輸出T的各條邊。
        記錄從頂點集U到V-U的代價最小的邊的輔助數組定義：
        struct
        {
            VertexType adjvex;
            VRtype lowcost;
        }closedge[MAX_VERTEX_NUM];
    */
    
    k = LocateVex(G, u);
    for (j = 0 ; j < G.vexnum; j++) {           //輔助數組初始化
        if (j != k)
            closedge[j] = {u, G.arcs[k][j].adj}; //{adjvex, lowcost}
    }
    closedge[k].lowcost = 0;                 //初始，U={u}
    for (i = 1; i < G.vexnum ; i++) {           //選擇其餘G.vexnum -1 個頂點
        k = minimum(closedge);              //求出T的下個結點：第k結點
        //  此时 closedge[k].lowcost = MIN{ closedge[Vi].lowcost|closedge[Vi].lowcost>0,Vi∈V-U}
        printf(closedge[k].adjvex, G.vexs[k]);    //輸出生成樹的邊
        closedge[k].lowcost = 0;             //第k條邊併入U集
        for (j = 0; j < G.vexnum; j++) {
        
            //新頂點併入U後重新選擇最小邊
            if (G.arcs[k][j].adj < closedge[j].lowcost && closedge[j].lowcost!=0) 
                closedge[j] = {G.vex[k], G.arcs[k][j].adj};
        }
    }
}

</syntaxhighlight>
<syntaxhighlight lang="cpp" style="overflow:hidden" line="1">

//来源： 浙大-陈越 《数据结构》

#define ERROR -1
Vertex FindMinDist( MGraph Graph, WeightType dist[] )
{
    /* 返回未被收录顶点中dist最小者 */
    
    Vertex MinV, V;
    WeightType MinDist = INFINITY;

    for (V=0; V<Graph->Nv; V++) {
        if ( dist[V]!=0 && dist[V]<MinDist) {
            /* 若V未被收录，且dist[V]更小 */
            MinDist = dist[V]; /* 更新最小距离 */
            MinV = V; /* 更新对应顶点 */
        }
    }
    if (MinDist < INFINITY) /* 若找到最小dist */
        return MinV; /* 返回对应的顶点下标 */
    else return ERROR;  /* 若这样的顶点不存在，返回-1作为标记 */
}

int Prim( MGraph Graph, LGraph MST )
{ /* 将最小生成树保存为邻接表存储的图MST，返回最小权重和 */
    WeightType dist[MaxVertexNum], TotalWeight;
    Vertex parent[MaxVertexNum], V, W;
    int VCount;
    Edge E;

    /* 初始化。默认初始点下标是0 */
       for (V=0; V<Graph->Nv; V++) {
        /* 这里假设若V到W没有直接的边，则Graph->G[V][W]定义为INFINITY */
           dist[V] = Graph->G[0][V];
           parent[V] = 0; /* 暂且定义所有顶点的父结点都是初始点0 */
    }
    TotalWeight = 0; /* .

    ..........初始化权重和     */
    VCount = 0;      /* 初始化收录的顶点数 */
    /* 创建包含所有顶点但没有边的图。注意用邻接表版本 */
    MST = CreateGraph(Graph->Nv);
    E = (Edge)malloc( sizeof(struct ENode) ); /* 建立空的边结点 */

    /* 将初始点0收录进MST */
    dist[0] = 0;
    VCount ++;
    parent[0] = -1; /* 当前树根是0 */

    while (1) {
        V = FindMinDist( Graph, dist );
        /* V = 未被收录顶点中dist最小者 */
        if ( V==ERROR ) /* 若这样的V不存在 */
            break;   /* 算法结束 */

        /* 将V及相应的边<parent[V], V>收录进MST */
        E->V1 = parent[V];
        E->V2 = V;
        E->Weight = dist[V];
        InsertEdge( MST, E );
        TotalWeight += dist[V];
        dist[V] = 0;
        VCount++;

        for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
            if ( dist[W]!=0 && Graph->G[V][W]<INFINITY ) {
            /* 若W是V的邻接点并且未被收录 */
                if ( Graph->G[V][W] < dist[W] ) {
                /* 若收录V使得dist[W]变小 */
                    dist[W] = Graph->G[V][W]; /* 更新dist[W] */
                    parent[W] = V; /* 更新树 */
                }
            }
    } /* while结束*/
    if ( VCount < Graph->Nv ) /* MST中收的顶点不到|V|个 */
       TotalWeight = ERROR;
    return TotalWeight;   /* 算法执行完毕，返回最小权重和或错误标记 */
}
</syntaxhighlight>
=== Python语言实现 ===
此份源码使用了堆优化
<syntaxhighlight lang="python" line="1">
from queue import PriorityQueue as priority_queue
from math import inf
class Node:
    def __init__(self,id,**kwargs):
        self.id = id
        self.fst = self.lst = None

    def __iter__(self):
        return NodeIterator(self)

    def __repr__(self):
        return "Node(%d)"%self.id

class NodeIterator:
    def __init__(self,Node):
        self.prst = Node.fst

    def __next__(self):
        if self.prst == None:
            raise StopIteration()
        ret = self.prst
        self.prst = self.prst.nxt
        return ret

class Edge:
    def __init__(self,fr,to,**kwargs):
        if fr.fst == None:
            fr.fst = self
        else:
            fr.lst.nxt = self
        fr.lst = self
        self.to = to
        self.nxt = None
        self.w = 1 if 'w' not in kwargs else kwargs['w']

    def __repr__(self):
        return "Edge({},{},w = {})",format(self.fr,self.to,self.w)

class Graph:
    def __init__(self,V):
        self.nodecnt = V
        self.nodes = [Node(i) for i in range(V)]
        self.edges = []

    def add(self,u,v,**kwargs):
        self.edges.append(Edge(self.nodes[u],self.nodes[v],**kwargs))

    def MST_prim(self,begin):
        '''
        prim algorithm on a graph(with heap),
        returns the weight sum of the tree
        or -1 if impossible
        '''
        q = priority_queue()
        vis = [False for _ in range(self.nodecnt)]
        q.put((0,begin))
        ret = 0
        while not q.empty():
            prst = q.get()
            if vis[prst[1]]:
                continue
            vis[prst[1]] = True
            ret += prst[0]
            for i in self.nodes[prst[1]]:
                if not vis[i.to.id]:
                    q.put((i.w,i.to.id))
        if all(vis):
            return ret
        else:
            return -1
</syntaxhighlight>
=== Java语言实现 ===

<syntaxhighlight lang="java" line="1">
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Prim {
    public static List<Vertex> vertexList = new ArrayList<Vertex>();//结点集
    public static List<Edge> EdgeQueue = new ArrayList<Edge>();//边集
    public static List<Vertex> newVertex = new ArrayList<Vertex>();//已经 访问过的结点

    public static void main(String[] args) {
        primTree();
    }
    public static void buildGraph() {
        Vertex v1 = new Vertex("a");
        Prim.vertexList.add(v1);
        Vertex v2 = new Vertex("b");
        Prim.vertexList.add(v2);
        Vertex v3 = new Vertex("c");
        Prim.vertexList.add(v3);
        Vertex v4 = new Vertex("d");
        Prim.vertexList.add(v4);
        Vertex v5 = new Vertex("e");
        Prim.vertexList.add(v5);
        addEdge(v1, v2, 6);
        addEdge(v1, v3, 7);
        addEdge(v2, v3, 8);
        addEdge(v2, v5, 4);
        addEdge(v2, v4, 5);
        addEdge(v3, v4, 3);
        addEdge(v3, v5, 9);
        addEdge(v5, v4, 7);
        addEdge(v5, v1, 2);
        addEdge(v4, v2, 2);
    }
    public static void addEdge(Vertex a, Vertex b, int w) {
        Edge e = new Edge(a, b, w);
        Prim.EdgeQueue.add(e);
    }
    public static void primTree() {
        buildGraph();
        Vertex start = vertexList.get(0);
        newVertex.add(start);
        for (int n = 0; n < vertexList.size() - 1; n++) {
            Vertex temp = new Vertex(start.key);
            Edge tempedge = new Edge(start, start, 1000);
            for (Vertex v : newVertex) {
                for (Edge e : EdgeQueue) {
                    if (e.start == v && !containVertex(e.end)) {
                        if (e.key < tempedge.key) {
                            temp = e.end;
                            tempedge = e;
                        }
                    }
                }
            }
            newVertex.add(temp);
        }
        Iterator it = newVertex.iterator();
        while (it.hasNext()) {
            Vertex v = (Vertex) it.next();
            System.out.println(v.key);
        }
    }
    public static boolean containVertex(Vertex vte) {
        for (Vertex v : newVertex) {
            if (v.key.equals(vte.key))
                return true;
        }
        return false;
    }
}

class Vertex {
    String key;
    Vertex(String key) {
        this.key = key;
    }
}

class Edge {
    Vertex start;
    Vertex end;
    int key;
    Edge(Vertex start, Vertex end, int key) {
        this.start = start;
        this.end  = end;
        this.key = key;
    }
}
</syntaxhighlight>

== 參考 ==
普林演算法與[[迪科斯彻演算法]]的策略相似。

{{算法}}
[[Category:图算法]]