prim-プリムアルゴリズム-MST-最小生成ツリー
16579 ワード
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;
}