Loading AI tools
来自维基百科,自由的百科全书
普里姆算法(英语:Prim's algorithm)是图论中的一种贪心算法,可在一个加权连通图中找到其最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点,且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克发现;并在1957年由美国计算机科学家罗伯特·C·普里姆独立发现;1959年,艾兹格·迪科斯彻再次发现了该算法。因此,在某些场合,普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆-亚尔尼克算法。
此条目或许过多或不当使用受版权保护的文字、图像及多媒体文件。 (2020年4月8日) |
从单一顶点开始,普里姆算法按照以下步骤逐步扩大树中所含顶点的数目,直到遍及连通图的所有顶点。
通过邻接矩阵图表示的简易实现中,找到所有最小权边共需的运行时间。使用简单的二叉堆与邻接表来表示的话,普里姆算法的运行时间则可缩减为,其中为连通图的边集大小,为点集大小。如果使用较为复杂的斐波那契堆,则可将运行时间进一步缩短为,这在连通图足够密集时(当满足条件时),可较显著地提高运行速度。
图例 | 说明 | 不可选 | 可选 | 已选 |
---|---|---|---|---|
![]() |
此为原始的加权连通图。每条边一侧的数字代表其权值。 | - | - | - |
![]() |
顶点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距D为15,F距D为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 |
已知图G的边数量为numEdge, 顶点数量为numVert, prim生成的树为T0, 最小生成树(MST)为Tmin
则有,cost(Tmin)<=cost(T0)
设: T0 的 numVert-1 条边按照权重由小到大排列依次为:ek1, ek2, ek3, ..., ekn
Tmin 的 numVert-1 条边按照权重由小到大排列依次为:eg1, eg2, eg3, ..., egn
其中n=numVert-1
两棵树的边从小到大权重比较,设第一个属于 T0 但不属于 Tmin 的边为 ed1, 连接该边的两个顶点为 (vs, ve1)
同时存在第一个属于 Tmin 但不属于 T0 且以vs为顶点的边,记为 ed2, 连接该边的两个顶点为 (vs, ve2)。
两个边的起点相同。由Prim算法性质可知,w(ed2) >= w(ed1)
此时,在 Tmin 中删除 ed2 ,添加 ed1,边的数量和顶点数量均不变,且不存在环,因此得到新的生成树Tnew,且cost(Tmin)>=cost(Tnew)
又因为 Tmin 是MST 所以 cost(Tmin)=cost(Tnew)。
以此类推,cost(Tmin)=cost(T0)
T0是最小生成树, 得证.
部分主程序段:
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;
此份源码使用了堆优化
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
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;
}
}
普林演算法与迪科斯彻演算法的策略相似。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.