最小生成树的源代码（C++实现）

应用普里姆算法和克鲁斯卡尔算法实现的最小生成树代码 为了实现上的方便，每个结点用数字0,1,2...表示

#include
using namespace std;
const int MAX_VERTEX_NUM=50;
const int INFINITY=1000;
typedef struct{
	int vexs[MAX_VERTEX_NUM];
	int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
	int vexnumarcnum;
}MGraph;
class MiniSpanTree{
public:
	MiniSpanTree（ ）;
	void MiniSpanTree_K（MGraph G）;
	void update（int int ）;
private:
	MGraph G;
	int father;
	int F[MAX_VERTEX_NUM][1];
	int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM][1];
};
MiniSpanTree::MiniSpanTree（ ）{
	cout<<“输入连通网的顶点数和边数“<	cout<<“顶点数“;
	cin>>G.vexnum ;
	cout<<“边数“;
	cin>>G.arcnum ;
	for（int i=0;i		for（int j=0;j			G.arcs [i][j]=INFINITY;
			D[i][j][0]=0;
		}
	int abc;
	for（int i=0;i		cin>>a>>b>>c;
		G.arcs [a][b]=c;
	}
	for（int i=0;i		for（int j=0;j			cout<		cout<	}
	for（int i=0;i		F[i][0]=-1;
	father=-1;
	MiniSpanTree_K（G）;
}
void MiniSpanTree::MiniSpanTree_K（MGraph G） {
	int minpqsum;
	sum=G.vexnum-1;
	while（sum）{
		min=INFINITY;
		for（int i=0;i			for（int j=0;j				if（!D[i][j][0]&&G.arcs[i][j]					p=i;
					q=j;
					min=G.arcs[i][j];
				}
				D[p][q][0]=1;
				sum--;
				if（F[p][0]==-1||F[q][0]==-1）{
					if（F[p][0]==-1&&F[q][0]!=-1）
						F[p][0]=F[q][0];
					else
						if（F[p][0]!=-1&&F[q][0]==-1）
							F[q][0]=F[p][0];
						else
							F[p][0]=F[q][0]=++father;
				}
				else{
					if（F[p][0]!=F[q][0]）
						update（F[p][0]F[q][0]）;
					else{
						sum++;
						D[p][q][0]=2;
					}
				}
				if（D[p][q][0]==1）
					cout<<“第“<<5-sum<<“条边（“<	}
}
void MiniSpanTree::update（int aint b）{
	int MN;
	if（a>b）{
		M=a;
		N=b;
	}
	else{
		M=b;
		N=a;
	}
	for（int i=0;i		if（F[i][0]!=-1）{
			if（F[i][0]==M）
				F[i][0]=N;
			else
				if（F[i][0]>M）
					F[i][0]--;
		}
	}
	father--;
}
int main（ ）{
	MiniSpanTree T;
}


			

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       2035  2009-05-27 13:43  最小生成树\克鲁斯卡尔.cpp

     文件       1705  2009-05-27 13:42  最小生成树\普里姆.cpp

     目录          0  2009-05-27 13:44  最小生成树

     文件         96  2009-05-27 13:46  使用说明.txt

----------- ---------  ---------- -----  ----

                 3836                    4