最小生成树(已经更新)-白红宇

最小生成树(已经更新)

阅读量：6036 次

发布时间：2019-06-20

本文共 8504 字，大约阅读时间需要 28 分钟。

#include 
    
     #include 
     
      #include 
      
       #include

template
    
     struct Node{  //最小生成树的结点.  X key;  Node()=default;  template
     
       Node(const Ty& k);  template
      
        Node(const Node
       
        & otherNode);  template
        
          bool operator!=(const Node
         
          & otherNode);  //template
          
            Node
           
            & operator=(const Node
            
             & otherNode);  Node
             
              (Node
              
               && otherNode);  ~Node(){ std::cout<<"destroy node"<

template
    
     template
     
      Node
      
       ::Node(const Ty& k)        :key(k){ //}

template
    
     Node
     
      ::Node(Node
      
       && otherNode)        :key(otherNode.key){ std::cout<<"移动构造函数."<

template
    
     template
     
      Node
      
       ::Node(const Node
       
        & otherNode)        :key(otherNode.key){ //std::cout<<"copy constructor in node"<

template
    
     template
     
      bool Node
      
       ::operator!=(const Node
       
        & other){ return (this->key != other.key) ? true : false;}

template
    
     //template
     
      Node
      
       & Node
       
        ::operator=(const Node
        
         & otherNode){ this->key = otherNode.key; //std::cout<<"operator = in node"<

template
    
     class Edge{ public:  Node
     
      * startNode;  Node
      
       * endNode;  int weighting; //start和end两个结点之间的加权值.     Edge();    template
       
          Edge(const Ty& s, const Ty& e, const int& wg=1);    //这里写成Ty* s,而上面的则应该用std::is_class,而不是std::is_pointer,因为如果传递过来的是一个指针例如Node
        
         * ptr,  //那么Ty则被推断为Node
         
           因为其中解引号(*)我们已经给出了.   template
          
           < std::is_class
           
            ::value, void >::type >    Edge(Ty* s, Ty* e, const int& wg=1);      template
            
               friend bool operator<=(const Edge
             
              & lhs, const Edge
              
               & rhs);  //注意这里以为在SortNode中我们用的Type是一个Edge
               
                *(指针)所以这里也要接个指针.     ~Edge(){ std::cout<<"destroy edge"<

template
    
     Edge
     
      ::Edge()        :startNode(nullptr),         endNode(nullptr),         weighting(0){ //}

template
    
     template
     
      Edge
      
       ::Edge(const Ty& s, const Ty& e, const int& wg)        :startNode(new Node
       
        (s)),         endNode(new Node
        
         (e)),         weighting(wg){ // //std::cout<<"success to create"<

template
    
     template
     
      Edge
      
       ::Edge(Ty* s, Ty* e, const int& wg)        :startNode(s),         endNode(e),         weighting(wg){ //}

template
    
     bool operator<=(const Edge
     
      & lhs, const Edge
      
       & rhs){ //std::cout<<"operator<="<
       
        <= rhs.weighting);}

class SortNode{ //注意这里一个class,有一个模板函数,对edge根据加权值从小到大排序.  public:  template
    
       bool operator()(const Edge
     
      & lhs, const Edge
      
       & rhs); //注意这里是为了个下面的MiniTree中的edgeArray按加权值从小到大排序. };

template
    
     bool SortNode::operator()(const Edge
     
      & lhs, const Edge
      
       & rhs){ //std::cout<<"use operator()"<
       
        <= rhs;}

template
    
     class MiniTree{ private:  int EdgeNumber;  //图有多少条边(edge).   int NodeNumber;  //图中结点的个数.   Edge
     * edgeArray;  Node* nodeArray;  //每条边都有两个结点和一个加权值组成，而nodeArray这个数组则是用来存放各个边的代表的(代表指的是一个结点).   int* nodes;    void sortFunction();  //对所有的边按权值大小排序.     template
       
          void makeCell(const Ty& k); //创建一个单元     template
        
          //压缩路径   const Ty findCell(const Ty& k);      template
         
             void union_node(const Ty& lhs, const Ty& rhs); //合并结点.       template
          
              void link_node(const Ty& lhs, const Ty& rhs);     public:   MiniTree(const unsigned int& edgeNumber, const unsigned int& nodeNumber);   ~MiniTree();      template
           
            < std::is_same
            
             ::value, void >::type > //确定U,Ty的类型是否一致.    void createTree(const Ty (&array)[N][3]);      void Kruskal();};

template
    
     MiniTree
     ::MiniTree(const unsigned int& edgeNumber, const unsigned int& nodeNumber)            :EdgeNumber(edgeNumber),             NodeNumber(nodeNumber),             edgeArray(nullptr),             nodeArray(nullptr),             nodes(nullptr){ this->edgeArray = new Edge[EdgeNumber];  //分配一个存储各个边的数组.  this->nodeArray = new Node[EdgeNumber];  //注意这里创建了一个结点的数组， 但是它的个数为EdgeNumber，该数组内存储的都是每条边的代表(即一个结点) this->nodes = new int[edgeNumber*edgeNumber];  std::uninitialized_fill_n(this->nodes, edgeNumber*edgeNumber, 0); std::cout<<"success"<

template
    
     template
     
      void MiniTree
      ::createTree(const Ty (&array)[N][3]){ std::cout<<"the N:"<
       
        <
        
         EdgeNumber){  throw std::bad_cast(); }  for(int i=0; i
         
          EdgeNumber; ++i){ //初始化各个边.   /*Node
          
           * sNode = new Node
           
            (array[i][0]);  Node
            
             * eNode = new Node
             
              (array[i][2]);    Edge
              
                edge(array[i][0], array[i][2], array[i][1]);  this->makeCell(array[i][0]);   //this->edgeArray[i].startNode = sNode;  //this->edgeArray[i].endNode = eNode;  //this->edgeArray[i].weighting = array[i][1];  //std::cout<
               
                <<"  "<
                
                 <<"  "<
                 
                  <
                  
                   edgeArray[i] = edge;  std::cout<
                   
                    key<
                    
                     * edge=new Edge
                     
                      (array[i][0], array[i][2], array[i][1]);  this->edgeArray[i] = *edge;   }   for(int i=0; i
                      
                       EdgeNumber; ++i){  this->makeCell(i); }  std::cout<<"before sort function"<
                       
                        sortFunction();  std::cout<<"after sort function"<

template
    
     void MiniTree
     ::sortFunction(){ std::sort(this->edgeArray, this->edgeArray+EdgeNumber,  SortNode()); //对所有的边按照加权值从小到大的顺序排序. }

template
    
     template
     
      void MiniTree
      ::makeCell(const Ty& k) {     Node
       
        * node=new Node
        
         (k);  this->nodeArray[k] = *node; //注意这里nodeArray中每个元素存储的都是一个边代表(代表:即一个结点).   //this->nodes[i] = 0; }

template
    
     template
     
      const Ty MiniTree
      ::findCell(const Ty& k) //压缩路径 {  if(k != this->nodeArray[k].key){  this->nodeArray[k].key = this->findCell(this->nodeArray[k].key);   } return this->nodeArray[k].key;}

template
    
     template
     
      void MiniTree
      ::link_node(const Ty& lhs, const Ty& rhs){ std::cout<
       
        <<"--link--"<
        
         <
         
          nodes[lhs] > this->nodes[rhs]){  this->nodeArray[rhs].key = lhs;   }else{  this->nodeArray[lhs].key = rhs;  if(this->nodes[lhs] == this->nodes[rhs]){   ++(this->nodes[lhs]);  }   } }

template
    
     template
     
      void MiniTree
      ::union_node(const Ty& lhs, const Ty& rhs){ this->link_node(this->findCell(lhs), this->findCell(rhs)); //查找lhs,rhs的父节点然后把rhs的父结点连到lhs上. }

template
    
     void MiniTree
     ::Kruskal(){ std::cout<<"enter Kruskal"<
      
       
        EdgeNumber; ++i){  U start = (this->edgeArray[i].startNode)->key; //获得改变startNode结点的key值.   U end = (this->edgeArray[i].endNode)->key;  int wgValue = (this->edgeArray[i]).weighting; //获得该边的加权值.   std::cout<
        
         <<"and"<
         
          <
          
           findCell(start) != this->findCell(end)){   std::cout<
           
            <<"-----"<
            
             <<"-----"<
             
              <
              
               union_node(start, end);     } }}

template
    
     MiniTree
     ::~MiniTree(){ if(this->edgeArray != nullptr){    for(int i=0; i
      
       EdgeNumber; ++i){   if(this->edgeArray[i].startNode != nullptr){    delete edgeArray[i].startNode;        if(this->edgeArray[i].endNode != nullptr){     delete edgeArray[i].endNode;     std::cout<<"endNode"<
       <
        
         <<"delete edge-----------"<
         
          edgeArray = nullptr; }  if(this->nodeArray != nullptr){  delete[] nodeArray;  std::cout<<"delete node--------------"<
          
           nodeArray = nullptr; }  if(this->nodes != nullptr){  delete[] nodes;  this->nodes = nullptr; }  std::cout<<"destroy tree"<

int main(){ int edges[][3]= {
    {1, 4, 2}, //注意{1, 4, 2}中1对应edge中的start, 4对应end, 2对应加权值weighting;                 {1, 8, 8},                {2, 8, 3},                {2, 11, 8},                {3, 7, 4},                {3, 2, 9},                {3, 4, 6},                {4, 9, 5},                {4, 14, 6},                {5, 10, 6},                {6, 2, 7},                {7, 6, 9},                {7, 1, 8},                {8, 7, 9}               }; MiniTree
    
      myMinimumTree(14, 28); myMinimumTree.createTree(edges);  myMinimumTree.Kruskal(); std::cout<<"the end"<

最小生成树

最小生成树其实就是不相交集合的运用.其中非常重要的一步是根据每条边的加权值，对每条边进行排序，然后执行Kruskal的时候查找每条边两个节点的父结点，通过压缩路径的方法。

参考这里:

转载于:https://my.oschina.net/SHIHUAMarryMe/blog/598795

你可能感兴趣的文章

《服务器SSH Public Key认证指南》-补充