【树论 1】 prim算法的学习和使用

进阶版神犇可以看看本题解的姊妹篇 Kruskal算法的学习和使用  
下面的内容是prim算法

但是最小生成树是什么呢？

标准定义如下：在边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。

听起来非常的带劲，我们就一起来探讨这一求最小生成树的算法！

prim 的四大特征：

●最小生成树算法中prim算法是耗时最长的

●最小生成树算法中prim算法是适用于求稠密图的

●最小生成树算法中prime算法最简单易懂

●请不要多打一个e否则就是prime质数了（手动滑稽）

例子：

P3366 【模板】最小生成树

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出orz

输入输出格式

输入格式：

第一行包含两个整数N、M，表示该图共有N个结点和M条无向边。（N<=5000，M<=200000）

接下来M行每行包含三个整数Xi、Yi、Zi，表示有一条长度为Zi的无向边连接结点Xi、Yi

输出格式：

输出包含一个数，即最小生成树的各边的长度之和；如果该图不连通则输出orz

输入输出样例

输入样例#1：

输出样例#1：

说明

时空限制：1000ms,128M

数据规模：

对于20%的数据：N<=5，M<=20

对于40%的数据：N<=50，M<=2500

对于70%的数据：N<=500，M<=10000

对于100%的数据：N<=5000，M<=200000

样例解释：

所以最小生成树的总边权为2+2+3=7

【解析】

先来看一个例子，鲜明的阐释了prim算法的工作原理

原理：假设G＝(V，E)是连通的，TE是G上最小生成树中边的集合。算法从U＝{u0}（u0∈V）、TE＝{}开始。重复执行下列操作：

在所有u∈U，v∈V－U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到V＝U为止。

此时，TE中必有n-1条边，T=(V，TE)为G的最小生成树。

Prim算法的核心:始终保持TE中的边集构成一棵生成树。

图例	说明	不可选	可选	已选（Vnew）
	此为原始的加权连通图。每条边一侧的数字代表其权值。	-	-	-
	顶点D被任意选为起始点。顶点A、B、E和F通过单条边与D相连。A是距离D最近的顶点，因此将A及对应边AD以高亮表示。	C, G	A, B, E, F	D
	下一个顶点为距离D或A最近的顶点。B距D为9，距A为7，E为15，F为6。因此，F距D或A最近，因此将顶点F与相应边DF以高亮表示。	C, G	B, E, F	A, D
	算法继续重复上面的步骤。距离A为7的顶点B被高亮表示。	C	B, E, G	A, D, F
	在当前情况下，可以在C、E与G间进行选择。C距B为8，E距B为7，G距F为11。点E最近，因此将顶点E与相应边BE高亮表示。	无	C, E, G	A, D, F, B
	这里，可供选择的顶点只有C和G。C距E为5，G距E为9，故选取C，并与边EC一同高亮表示。	无	C, G	A, D, F, B, E
	顶点G是唯一剩下的顶点，它距F为11，距E为9，E最近，故高亮表示G及相应边EG。	无	G	A, D, F, B, E, C
	现在，所有顶点均已被选取，图中绿色部分即为连通图的最小生成树。在此例中，最小生成树的权值之和为39。	无	无	A, D, F, B, E, C, G

对于题目里的例子：我们来分析：

由于求的是最小生成树的边权之和，所以那边是最小生成树的根就无所谓了

这里假设1为最小生成树的根;

与集合{1}相连的边中只有权为2的边权最小，有2条边满足条件，

为了操作方便，选择靠后的1 3这条边加入集合（等价于前面的加入集合）把3加入集合{1}==>{1,3}

与集合{1,3}相连的边一共有4条，其中1 2之间的边权最小，所以把2加入集合{1,,3}==>{1,2,3}

与集合{1,2,3}相连的边一共有两条，都是3，

为了操作方便，选择靠后的1 4这条边加入集合（等价于前面的加入集合）{1,2,3}==>{1,2,3,4}

发现所有的点都被加入集合，结束权值和为2+2+3=7

【实现】

var n,m,i,j,u,v,d:longint;
    g:array[0..5000,0..5000]of longint;
function min(a,b:longint):longint;
begin
 if a<b then exit(a)
 else exit(b);
end;
procedure prim(v0:longint);
var u:array[0..5000]of boolean;
    min:array[0..5000]of longint;
    i,j,k,tot:longint;
begin
 fillchar(min,sizeof(min),$7f);//min表示各点到集合{}的权值
 fillchar(u,sizeof(u),true);//判断这个点是否加入集合
 min[v0]:=0;
 d[v0]:=0;//自己到自己设为0
 for i:=2 to n do begin//由于下面加入点为1则从2开始遍历（1也可以）
  k:=0;//k表示下一个被加入集合的点
  for j:=1 to n do
     if u[j] and (min[j]<min[k]) then k:=j;//迭代法找到下一个与集合{}间权值最小的点
  u[k]:=false;//把这个点加入集合
  for j:=1 to n do
   if u[j] and (g[k,j]<min[j]) then min[j]:=g[k,j];
//由于新加入一个点也属于集合中所以各点到集合的距离可能会是这个点到k点的距离，所以判
 end;
 tot:=0;
 for i:=1 to n do tot:=tot+min[i];//求出集合到各点之间的距离记为tot
 writeln(tot);//tot就是最小生成树的权值和
end;
begin
 readln(n,m);
 if m<n-1 then begin writeln('orz'); halt; end;//最小生成树的边一定等于点数-1，边数小于点数-1就不构成一个联通的图
 fillchar(g,sizeof(g),$7f);//清零，用fillchar快不少
 for i:=1 to m do begin
  readln(u,v,d);
  g[u,v]:=min(g[u,v],d);
  g[v,u]:=g[u,v];//避免重复读入求最小边
 end;
 prim(1);//假定最小生成树的根为1
end.

【区别】

看完prim算法实现后，我们思考这样一个问题，单元最短路径的dijkstra的算法和prim有何相似之处呢？

不妨把dijkstra放在这里给大家显示一下区别吧！

例子：

P3371 【模板】单源最短路径

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入输出格式

输入格式：

第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。

接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。

输出格式：

一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647）

输入输出样例

输入样例#1：

输出样例#1：

0 2 4 3

说明

时空限制：1000ms,128M

数据规模：

对于20%的数据：N<=5，M<=15

对于40%的数据：N<=100，M<=10000

对于70%的数据：N<=1000，M<=100000

对于100%的数据：N<=10000，M<=500000

样例说明：

dijkstra算法详解：

单源最短路径问题，即在图中求出给定顶点到其它任一顶点的最短路径。在弄清楚如何求算单源最短路径问题之前，必须弄清楚最短路径的最优子结构性质。

一.最短路径的最优子结构性质

该性质描述为：如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，k和s是这条路径上的一个中间顶点，那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。

假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，则有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是从k到s的最短距离，那么必定存在另一条从k到s的最短路径P'(k,s)，那么P'(i,j)=P(i,k)+P'(k,s)+P(s,j)<P(i,j)。则与P(i,j)是从i到j的最短路径相矛盾。因此该性质得证。

二.Dijkstra算法

由上述性质可知，如果存在一条从i到j的最短路径(Vi.....Vk,Vj)，Vk是Vj前面的一顶点。那么(Vi...Vk)也必定是从i到k的最短路径。为了求出最短路径，Dijkstra就提出了以最短路径长度递增，逐次生成最短路径的算法。譬如对于源顶点V0，首先选择其直接相邻的顶点中长度最短的顶点Vi，那么当前已知可得从V0到达Vj顶点的最短距离dist[j]=min{dist[j],dist[i]+matrix[i][j]}。根据这种思路，

假设存在G=<V,E>，源顶点为V0，U={V0},dist[i]记录V0到i的最短距离，path[i]记录从V0到i路径上的i前面的一个顶点。

1.从V-U中选择使dist[i]值最小的顶点i，将i加入到U中；

2.更新与i直接相邻顶点的dist值。(dist[j]=min{dist[j],dist[i]+matrix[i][j]})

3.知道U=V，停止。

三、流程图

【dijkstra程序实现】

const longlong=2147483647;
      maxn=5000;
var i,j,n,m,s,x,y,z:longint;
    d:array[1..maxn]of longint;
    g:array[1..maxn,1..maxn]of longint;
function min(a,b:longint):longint;
begin
 if a>b then exit(b) else exit(a);
end;
procedure dijkstra(v0:longint);
var i,j,k,minn:longint;
    u:array[1..maxn]of boolean;
begin
 fillchar(u,sizeof(u),false);
 for i:=1 to n do d[i]:=g[v0,i];d[v0]:=0;//初始值设为所有点到这个点的最短距离
 u[v0]:=true;//加入v0到集合{}
 for i:=1 to n do begin//由于不知道是那个点所以不能简单从2开始，若从2开始就是当v0=1时才正确
  minn:=longlong; k:=0;//minn表示d[]数组中最小的数，k表示这个最小的数是属于哪个点的
  for j:=1 to n do
   if (not u[j])and(d[j]<minn) then begin
    minn:=d[j]; k:=j;//求minn和k
   end;
  if k=0 then break;// 如果找不到点说明所有点都找完了说明d[]存储的就是各点到v0的单源最短路，跳出循环
  u[k]:=true;//加入最短距离k到集合{}表明此时k到v0的距离已经是最短了
  for j:=1 to n do
   if (not u[j])and(g[k,j]+d[k]<d[j])then//由于集合中新加入一个点，所以相对应的所有点可能通过到这个新加入的点在到v0是最短路
      d[j]:=g[k,j]+d[k];//更改最短距离
 end;
end;
begin
 readln(n,m,s);
 for i:=1 to n do
  for j:=1 to n do
   if i<>j then g[i,j]:=longlong
   else g[i,j]:=0;
 for i:=1 to m do begin
  readln(x,y,z);
  g[x,y]:=min(g[x,y],z);
 end;
 dijkstra(s);
 for i:=1 to n do write(d[i],' ');//d数组中存的是点1-n到点s的最短单源路径！
 writeln;
end.

【异同点】

区别：

1.用途：

Prim是计算最小生成树的算法，比如为N个村庄修路，怎么修花销最少。

Dijkstra是计算最短路径的算法，比如从a村庄走到其他任意村庄的距离。

2.概念

Prim出现点到集合的距离（这里用贪心），即这个点到集合中各元素的距离最小才加入最小的边

dijkstra中出现的点到集合的距离是通过每个待定的中转点来实现两点之间距离最短的

相似：

1.有关负权回路，prim和dijkstra在该问题上都是不能运行的

2.朴素的时间复杂度都是O(N²)的

3.求解方法，都是假设全部顶点的集合是V，已经被挑选出来的点的集合是U，那么二者都是从集合V-U中不断的挑选权值最低的点加入U的

【prim的优化】

这里引用百度百科的一段话：

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

最小边、权的数据结构	时间复杂度（总计）
邻接矩阵、搜索	O(V^2)
二叉堆、邻接表	O((V + E) log(V)) = O(E log(V))
斐波那契堆、邻接表	O(E + V log(V))

接下来给大家推荐几个好的关于prim 优化的文章，供大家参考：

●二叉堆维护+邻接表：链接

●斐波那契堆维护+邻接表：链接