prim.cpp

这是数据结构课程的试验作业

#include <iostream.h>

const int ItemNum = 6; 

char Vexs[ItemNum] = {'a','b','c','d','e','f'};
int ArcCell [ItemNum][ItemNum] = {{0,6,1,5,0,0},{6,0,5,0,3,0},{1,5,0,5,6,4},
									{5,0,5,0,0,2},{0,3,6,0,0,6},{0,0,4,2,6,0}};
int flag[ItemNum] = {0};
int lowcost[ItemNum] = {0};

int MiniNum(int a[ItemNum]){
	bool ff =true;
	int MiniNumP = 0;
	for (int i = 1;i < ItemNum;i++) {
		if (a[i] != 0) {
			if (ff == true) {
				MiniNumP = i;
				ff=false;
			}

			else 
				if (a[MiniNumP] > a[i]) {
				MiniNumP = i;
				}
		}
	}
	return MiniNumP;
}

void MiniSpanTree_Prim(char S){
	int i,j,StartNum,MiniNump;
	for (i = 0;i < ItemNum;i++) {
		if (Vexs[i] == S) {
			StartNum = i;
			break;
		}
	}
	flag[StartNum] = 1;
	for (int b = 0;b < ItemNum;b++) {
		for (j = 0;j < ItemNum;j++) {
			bool first = true;
			if (flag[j] == 1) {
				for (int k = 0;k < ItemNum;k++) {
					if (flag[k] !=1 && ArcCell[j][k] != 0) {
						if(first == true) {
							lowcost[j] = ArcCell[j][k];
							first = false;
						}
						else if(lowcost[j] > ArcCell[j][k]) lowcost[j] = ArcCell[j][k];
					}
				}
			}
		}
		MiniNump=MiniNum(lowcost);
		for (int a = 0;a < ItemNum;a++) {
			if (lowcost[MiniNump] == ArcCell[MiniNump][a] && flag[a] != 1) {
				cout<<"<"<<Vexs[MiniNump]<<Vexs[a]<<">"<<endl;
				flag[a] = 1;
				break;
			}
		}
	}
	
}


void main(){
//	Prim me;
	char ent;
	cout<<"请选择一个开始顶点(a,b,c,d,e): "<<endl;
	cin>>ent;
	cout<<"由Prim生成最小树算法得出从顶点"<<ent<<"开始的输出边为:"<<endl;
	MiniSpanTree_Prim(ent);
}