#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