prim算法

Prim算法代码实现

求无向网的最小生成树的算法有两种：Prim和Kruskal，它们都是利用最小生成树的MST性质得到的。我们先来介绍Prim算法，Kruskal我们后续介绍。

Prim算法思想：
逐渐长成一棵最小生成树。假设G=（V，E）是连通无向网，T=（V，TE）是求得的G的最小生成树中边的集合，U是求得的G的最小生成树所含的顶点集。初态时，任取一个顶点u加入U，使得U=｛u｝，TE=Ø。重复下述操作：找出U和V-U之间的一条最小权的边（u，v），将v并入U，即U=U∪｛v｝，边（u，v）并入集合TE，即TE=TE∪｛（u，v）｝。直到V=U为止。最后得到的T=（V，TE）就是G的一棵最小生成树。也就是说，用Prim求最小生成树是从一个顶点开始，每次加入一条最小权的边和对应的顶点，逐渐扩张生成的。

代码片如下
#include
#include
#include
#include
using namespace std;
int b[100][100]={0};//储存信息
int s[100]={0};//顶点是否被标记过
int F[100][100]={0};//F标记两个顶点的边是否被标记过
int m=100,n;//m为初始化权值
int v[100][150];//v[k][0]存储与k连接的节点，v[k][1]存储边的权值
//初始化图，让图从开始节点找出最小的边，并保存在v中
void intial(){
int b[10][10]={{0,1,6},{0,2,1},{0,3,5},{1,2,5},{1,4,3},{2,3,5},{2,4,6},{2,5,4},{3,5,2},{4,5,6}};
//对顶点遍历
for(int k=0;k<6;k++)
//对边遍历
for(int i =0;i<10;i++){
//判断要找的点是否被标记过,并取相应点的最小边
if(b[i][0]==k && s[b[i][1]] == 0 && b[i][2]<=v[k][1]){
//看相邻两个点的边是否被标记过
if(F[k][v[k][0]]==0){

				v[k][0]=b[i][1];
				
				v[k][1]=b[i][2];
				
			}
		}	 

}
}

void prim(){
int b[10][10]={{0,1,6},{0,2,1},{0,3,5},{1,2,5},{1,4,3},{2,3,5},{2,4,6},{2,5,4},{3,5,2},{4,5,6}};
//初始化v的值 ，便于求最小值
for (int i=0;i<6;i++)
{
v[i][0]=50;
v[i][1]=50;
}
//对顶点遍历
for(int k=0;k<6;k++) {

//对边遍历 
	for(int j =0;j<10;j++){
			//判断要找的点是否被标记过,并取相应点的最小边 
		if((F[b[j][0]][b[j][1]]==0) && (s[b[j][1]] + s[b[j][0]] == 1) && (b[j][2]<=v[k][1])&&b[j][0]==k){
					//判断两个顶点之间有哪一个是被标记过的，没标记的点赋值给v[k][0] 
					if(s[b[j][1]] != 0){
							v[k][0]=b[j][0];
							v[k][1]=b[j][2];
					}else{
					}
					if(s[b[j][0]]!=0){
							v[k][0]=b[j][1];
							v[k][1]=b[j][2];
					}else{
					}
					//用m储存边权值的最小值 ,n存贮在剩下的点中的最小权重的点 
					if(v[k][1]<= m){
						m=v[k][1];
						n=v[k][0]; 
					}
					
				}
			}
		
		}
	}

void print(){

int p=0;
int h=0;

// 5比较特殊，特别对待
s[5]=1;
while(h<3){
if(s[p]==0&&p<5){
//输出节点数
cout <<“V”<<p<<“的下一个节点为”<<“V”<<v[p][0]<<"\n"<<endl;
F[p][v[p][0]]=1;
F[v[p][0]][p]=1;
s[p]=1;
p=v[p][0];
}
h++;

}
//第一轮搜索结束后，继续完成后续工作
while(h<6){

prim();
s[n]=1;
F[n][p]=1;
F[p][n]=1;
cout <<"V"<<p<<"的下一个节点为"<<"V"<<n<<"\n"<<endl;
p=n;
m=100;
h++;
}

}

int main(){

for (int i=0;i<6;i++)
	{
		v[i][0]=50;
		v[i][1]=50;
	}
	
intial();
cout<<"准备好了吗，开始执行prim算法了......开始节点是：V0"<<"\n"<<endl;
print();
cout<<"还在看吗？已经结束了哦。。。。。"<<endl;
return 0;

}