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

Prim算法是任选一顶点作为起始点，从当前已纳入的顶点与未纳入的顶点间的所有路径中找出权最小的一条进行连接，循环直到所有的顶点都被纳入。代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       class graphic { public: graphic(int n){ std::cout << "请输入顶点信息" << std::endl; int tmp; for(int i = 0; i != n; ++i){ std::cin >> tmp; vertexs.push_back(tmp); } for(int i = 0; i != n; ++i){ paths.push_back(std::vector 
      
       (n, std:: numeric_limits
       
        ::max())); paths[i][i] = 0; } std::cout << "请输入边数：" << std::flush; int sum; std::cin >> sum; int vi, vj, weight; for(int i = 0 ; i != sum; ++i){ std::cout << "请输入边" << (i+1) << ":" << std:: flush; std::cin >> vi >> vj >> weight; paths[vi][vj] = weight; paths[vj][vi] = weight; } } void prim(){ int k = 0; std:: vector
        
          vec; std:: vector
         
           adj; for(size_t i = 0; i != vertexs.size(); ++i){ vec.push_back( paths[0][i]); adj.push_back(0); } while(true ){ int min = std::numeric_limits 
          
           :: max(); for(size_t j = 0; j != vertexs.size(); ++j){ if(vec[j] != 0 && vec[j] < min){ min = vec[j]; k = j; } } if(min < std::numeric_limits 
           
            :: max()){ std::cout << adj[k] << "->" << k << std::endl; vec[k] = 0; } else{ std::cout << "over" << std::endl; break; } for(size_t j = 0; j != vertexs.size(); ++j){ if(vec[j] && paths [k][j] < vec[j]){ vec[j] = paths[k][j]; adj[j] = k; } } } } private: std:: vector
            
              vertexs; std:: vector
             
               > paths; }; int main(){ graphic g(9); g.prim(); }

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

本文作者：girlkoo