#include?
using?namespace?std;
const?int?MAX=1000;?
int?M=0x3f3f3f;?????//代表無窮大?
int?n;
int?ans[MAX][MAX];????//能建立MAX個城市的通信網絡?
struct?node{
	int?xy;??????//城市坐標?
}v[MAX];
void?init（）{???????????????????//初始化及其界面?
????printf（“\t\t\t歡迎使用建立通信網絡系統\n“）;
????printf（“請輸入城市個數（>=10）:“）;
????scanf（“%d“?&n）;
????while（n<10）{
????????printf（“輸入出錯，請重新輸入城市個數（>=10）:“）;
????????scanf（“%d“?&n）;
????}
}
void?city（）{????//隨機生成城市坐標?
	printf（“\n\n“）;
	printf（“正在隨機生成城市坐標...\n“）;
	
	srand（time（NULL））;????//設置隨機種子?
	
	for（int?i=0;i		v[i].x=rand（）%100;
		v[i].y=rand（）%100;
	}
	
	printf（“\n\n“）;
	
	printf（“城市坐標生成完畢！\n“）;
	printf（“\n\n城市編號???城市x坐標????城市y坐標\n“）;
	for（int?i=0;i	printf（“%-12d%-12d%-12d\n“iv[i].xv[i].y）;
	
}
void?count（）{???//計算任意兩個城市間的距離
				//生成無向圖的鄰接矩陣?
	for（int?i=0;i		for（int?j=0;j			if（i!=j）{
				ans[i][j]=sqrt（（v[i].x-v[j].x）*（v[i].x-v[j].x）+（v[i].y-v[j].y）*（v[i].y-v[j].y））;
			}?
		}
	}?
	
}?
void?prim（int?ans[MAX][MAX]int?n）{
	printf（“\n\n“）;
	printf（“使用prim算法計算最小生成樹\n“）;
	int?ijkminlow[MAX]close[MAX];
	for（int?i=1;i		low[i]=ans[0][i];
		close[i]=0;
	}
	close[0]=-1;
	printf（“打印最小生成樹\n“）;
	printf（“------------------------------------------------\n“）;
	printf（“起點--->終點\t起點坐標???\t終點坐標\t權值\n“）?;
	for（int?i=1;i		min=M;
		k=i;
		for（int?j=0;j			if（low[j]				min=low[j];
				k=j;
			}
		}
		
		printf（“%-3d--->%-3d?\t（%-3d%-3d）\t（%-3d%-3d）\t權值%-3d?\n“close[k]kv[close[k]].xv[close[k]].yv[k].xv[k].ylow[k]）;
		close[k]=-1;
		for（int?j=1;j			if（close[j]!=-1&&ans[k][j]				low[j]=ans[k][j];
				close[j]=k;
			}
		}
	}
	
	
	
}
int?main（）{
????init（）;
	city（）;
	count（）;
	prim（ansn）;
????return?0;
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件????????1998??2019-04-26?20:14??prim.cpp
?????文件??????107857??2019-04-26?20:28??《數據結構課程設計報告》.docx
?????文件????????1996??2019-04-26?20:35??新建文本文檔?（3）.txt