最小生成树算法――Kruskal - c++编程基础

Kruskal算法的原理是先将图中的所有边按照权从小到大排序，然后循环取边，判断添加上该边后是子图中否有闭合回路，如果没有，则添加该边，否则舍弃该边。直到所有的边都遍历一遍。我认为该算法的核心是排序和判断闭合。下面是具体的代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       struct path { int start ; int end ; int weight ; }; static bool compare( path pi, path pj){ return pi.weight < pj.weight; } static int find( const std::vector 
      
       & array, int i){ while(array[i]) i = array[i]; return i; } int main(){ std:: vector
       
         vertexs; std:: vector
        
          paths; std::cout << "请输入顶点数：" << std::flush; int sum; std::cin >> sum; int tmp; for(int i = 0; i != sum; ++i){ vertexs.push_back(tmp); } std::cout << "请输入边数：" << std::flush; std::cin >




> sum; for(int i = 0; i != sum; ++i){ path p; std::cin >> p. start >> p.end >> p.weight; paths.push_back(p); } std::sort(paths.begin(), paths.end(), compare); std:: vector
         
           array(vertexs.size(), 0); for(size_t i = 0; i != paths.size(); ++i){ int m = find(array, paths[i].start ); int n = find(array, paths[i].end ); if(m != n){ array[m] = n; std::cout << paths[i].start << "->" << paths[i]. end << std::endl; } } }

本文链接：http://blog.csdn.net/girlkoo/article/details/17435951

本文作者：girlkoo