一.prim算法重述
基本思想：
1.从任意顶点开始；
2.逐步扩展边界；
3.每次扩展，选择当前边界边中 最小权重者加入T；
4.直至T中包含的顶点覆盖原图。
伪代码：
X={s} //目前已覆盖顶点集合
T=空集；
WHILE X≠V
令e(u,v)为权重最小的边界边(u∈X, v∉X)
将e加入T;
将v加入X;
ENDWHILE
二.prim算法证明
1.基本概念介绍
割：图G(V,E)的一个割(cut)是V的一个划分，该划分将集合V分为两个非空的集合。
Empty-Cut引理：图G不连通，当且仅当存在cut(A, B)没有割边。
圈与割边的关系：
Double-Crossing Lemma：如果某个圈C⊆E中有边跨越了cut(A, B),则C中必有其他边跨越cut(A, B)。 【至少还有一条】
Lonely-Cut Corollary：如果边e是跨越了cut(A, B)的唯一一条边,则e不可能在任一圈中。
2.prim算法证明
第一部分：Prim算法算出的是生成树。
注：上述图片来源于电子科技大学网络算法挑战性课程PPT。
第二部分：
注：上述图片来源于电子科技大学网络算法挑战性课程PPT。
3.prim的实现方式
1.最直接的实现方式
注：上述图片来源于电子科技大学网络算法挑战性课程PPT。
2.边界边集合
注：上述图片来源于电子科技大学网络算法挑战性课程PPT。
3. 引入边界点集合
伪代码：
FOR all vertex j in V DO
d(j) = ; p(j) = NULL;
X = {s}; T = NULL；
d(s) = 0; p(s) = NULL;
WHILE X V DO
i = FindMin(V-X);
T = T U { (p(i), i) };
X = X U {i};
FOR every neighbor t of i
IF w(i, t) < d(t) DO
d(t) = w(i, t); p(t) = i;
ENDFOR
ENDWHILE
4.数据结构堆实现
文章来源：https://www.toymoban.com/news/detail-406204.html
文章来源地址https://www.toymoban.com/news/detail-406204.html
注：上述图片来源于电子科技大学网络算法挑战性课程PPT。
三.项目代码
from collections import defaultdict
data_edge=defaultdict(list)
nodes=[] #储存点
def build_graph(filepath,data_edge,nodes):#构造图
f=open(filepath,'r')
edge_num=f.readline()
node_num=f.readline()
for i in f.readlines():
node_a,node_b,edge_c=i.split()
data_edge[node_a].append((int(edge_c),node_a,node_b))
data_edge[node_b].append((int(edge_c),node_b,node_a))
if node_a not in nodes:
nodes.append(node_a)
if node_b not in nodes:
nodes.append(node_b)
f.close()
class heap(object): #数据结构堆
def _init_(self):
self.data=[]
def get_parent_index(self,index):#获取父节点的下标
if index==0 or index>len(self.data)-1:
return None
else:
return (index-1)>>1
def Exact_min(self):#取出最小值
remove_data = self.data[0]
self.data[0] = self.data[-1]
del self.data[-1]
self.heapify(self.data)# 将剩余数据堆化
return remove_data
def swap(self,index_a,index_b):#交换结点数据
self.data[index_a], self.data[index_b]=self.data[index_b], self.data[index_a]
def insert(self,data_key):#插入新来结点数据
self.data.append(data_key)#先加到最后
index=len(self.data)-1
parent=self.get_parent_index(index)#先加入到堆的后面
while parent is not None and self.data[parent][0]>=self.data[index][0]:# 交换操作
self.swap(parent, index)
index=parent
parent=self.get_parent_index(parent)
def heapify(self, arr):#建堆
self.data=arr
#print(arr)
#print(self.data)
index=self.get_parent_index(len(arr)-1)
#print(index)
while index!=None and index>=0:#从底部向上比较，把最小值弄到根节点
if(2*index+1)<len(self.data):
if self.data[(2*index+1)]<self.data[index]:
self.swap(2*index+1,index)
if (2*index+2)<len(self.data) and (self.data[(2*index+2)]<self.data[index]):
self.swap(2*index+2,index)
index=index-1
heap1=heap()
def prim(data_edge,nodes,start_node,heap1):#prim
tree=[]#存储最小生成树边数据
visited=[]#已探索过结点的集合
visited.append(start_node)
#print(data_edge[start_node])
heap1.heapify(data_edge[start_node])
while len(visited)!=len(nodes):
edge_c,node_a,node_b=heap1.Exact_min()#选出距离最小的边数据
if node_b not in visited:
visited.append(node_b)
tree.append((int(edge_c),node_a,node_b))
for neighbor in data_edge[node_b]:#更新边集合
if neighbor[2] not in visited:
heap1.insert(neighbor)
return tree
build_graph('MST-test-3',data_edge,nodes)
ans=prim(data_edge,nodes,'1',heap1)
a=0
for i in ans:#计算权重和
a+=i[0]
print(a)
到了这里，关于网络算法-python实现prim(基于堆)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
