prim-プリムアルゴリズム-MST-最小生成ツリー

prim
頂点セットの操作:
ソース:

#include

using namespace std;

const int adjacent_matri_max=1000;

int vertex_num,edge_num;									//        
int	price=0;												//        
int	adjacent_matri[adjacent_matri_max][adjacent_matri_max];	//    
bool visitied[adjacent_matri_max];							//       
int  l_cost[adjacent_matri_max];
int path[adjacent_matri_max];

//       INT_MAX 
void init(){
	for(int i=0;i<vertex_num;i++){
		for(int j=0;j<vertex_num;j++){
			adjacent_matri[i][j]=INT_MAX;
		}
	}
	fill(visitied,visitied+vertex_num,false);
	fill(l_cost,l_cost+vertex_num,INT_MAX); 
	return ;
}

//Prim          
void Prim(int key){
	//key  0-vertex 
	int k=0;
	path[k++]=key;
	do{
		visitied[key]=true;						//         
		for(int i=0;i<vertex_num;i++){			//       
			l_cost[i]=min(l_cost[i],adjacent_matri[key][i]);	
		}
		int min_cost=INT_MAX;
		
		//            
		for(int i=0;i<vertex_num;i++){
			if(visitied[i]==false && l_cost[i]<min_cost){
				min_cost=l_cost[i];
				key=i;
			}
		}
		price+=min_cost;
		path[k]=key;
		cout<<k+1<<":"<<endl;
		cout<<"mint_cost:"<<min_cost<<endl;
		cout<<"price:"	<<price<<endl<<endl;
	}while(++k<vertex_num);
	
	return;
}

void PrintTree(int key){
	cout<<"         :"<<endl;
//	cout<";
	int count=0;
	for(int i=0;i<vertex_num;i++){
//		if(key!=path[i]){
			cout<<path[i]<<" ";
//			if(count++!=vertex_num-2)
//				cout<";
//		}
	}
}

int main(){
	int row,col;
	int key;
	int weight;
	cout<<"       ："<<endl;
	cout<<"       ："<<endl;
	cin>>vertex_num;
	cout<<"       :"<<endl;
	cin>>edge_num;
	
	//      INT    	
	init();
	
	

	//   (    ） 
	cout<<"    (      )     ：( "<<edge_num<<" ( ))"<<endl;
	for(int i=0;i<edge_num;i++){
		cin>>row>>col;
		cin>>weight;
		adjacent_matri[row][col]=adjacent_matri[col][row]=weight;
	}
	
	for(int i=0;i<vertex_num;i++){
		for(int j=0;j<vertex_num;j++){
			cout<<adjacent_matri[i][j]<<" ";
		}
		cout<<endl;
	}
	
	cout<<"       ："<<endl;	
	cin>>key;
	Prim(key);
	cout<<"        :"<<price<<endl;		
 	PrintTree(key); 
	
	return 0;
}