c言語バージョンの最小生成ツリー(Primアルゴリズム)の概要

750 ワード

1、Primアルゴリズムの概要:図論のアルゴリズムで、重み付け連通図の中で最小生成ツリーを検索することができる.すなわち、このアルゴリズムによって探索されたエッジサブセットからなるツリーには、連通図のすべての頂点(英語:Vertex(graph theory))だけでなく、そのすべてのエッジの重み値の和も最小である.
2、最小生成ツリー:n個のノードを有する連通図の生成ツリーは、原図の極小連通サブ図であり、原図中のすべてのn個のノードを含み、図連通を保持する最小限のエッジを有する.最小生成ツリーはkruskal(クルーズカール)アルゴリズムまたはprim(プリム)アルゴリズムで求めることができる.
3、重点部分コードセグメントの実現
//prim         
void MiniSpanTree_Prim(MGraph G){

	int min,i,j,k;
	int adjvex[MAXVEX]; //        
	int lowcost[MAXVEX];//          
	lowcost[0] = 0;     //v0             ,   0
	adjvex[0] = 0;		//V0     

	//     
	for(int i = 1;i