二话不说直接贴代码
原图传送门:
但是上面展现的是克鲁斯卡尔算法。我这里是普里姆算法。
#include#include #include
#include using namespace std;typedef struct Line{ int Dot1; int Dot2; int Power;}Line;static const int arr[] = {0,1,6, 0,2,1, 0,3,5, 1,2,5, 1,4,3, 2,3,7, 2,4,5, 2,5,4, 3,5,2, 4,5,6};void BuildMap(list & vet){ /*do { Line temp; cin>>temp.Dot1>>temp.Dot2>>temp.Power; vet.push_back(temp); }while(getchar() != '#');*/ for(int i = 0;i < sizeof(arr)/(sizeof(int)*3);++i) { Line temp; temp.Dot1 = arr[i*3]; temp.Dot2 = arr[i*3+1]; temp.Power = arr[i*3+2]; vet.push_back(temp); }}void MST(list &map,list & tree){ list Open; list OpenId; for(auto p = map.begin();p != map.end();++p) { Open.push_back(&*p); if(find(OpenId.begin(),OpenId.end(),p->Dot1) == OpenId.end()) OpenId.push_back(p->Dot1); if(find(OpenId.begin(),OpenId.end(),p->Dot2) == OpenId.end()) OpenId.push_back(p->Dot2); } Open.sort([](const Line* a,const Line* b){return a->Power < b->Power;});//支持C++11的编译器 tree.push_back(**Open.begin()); OpenId.erase(find(OpenId.begin(),OpenId.end(),(*Open.begin())->Dot1)); OpenId.erase(find(OpenId.begin(),OpenId.end(),(*Open.begin())->Dot2)); Open.pop_front(); auto q = Open.begin(); while(!OpenId.empty()) { if(find(OpenId.begin(),OpenId.end(),(*q)->Dot1) == OpenId.end() && find(OpenId.begin(),OpenId.end(),(*q)->Dot2) == OpenId.end()) {//已加入 Open.erase(q); q = Open.begin(); } else if(find(OpenId.begin(),OpenId.end(),(*q)->Dot1) == OpenId.end() || find(OpenId.begin(),OpenId.end(),(*q)->Dot2) == OpenId.end()) {//已加入 if(find(OpenId.begin(),OpenId.end(),(*q)->Dot1) == OpenId.end()) OpenId.erase(find(OpenId.begin(),OpenId.end(),(*q)->Dot2)); else if(find(OpenId.begin(),OpenId.end(),(*q)->Dot2) == OpenId.end()) OpenId.erase(find(OpenId.begin(),OpenId.end(),(*q)->Dot1)); tree.push_back(**q); Open.erase(q); q = Open.begin(); } else { ++q; } }}int main(){ list map; list tree; BuildMap(map); MST(map,tree); return 0;}