الگوریتم کروسکال

الگوریتم کروسکال 

برای دیدن این برنامه روی ادامه مطلب کلیک کنید.

Msmas.blogfa.com

/****************************************************

  *  Bachelor Project:                               *

  *  External Memory Minimum Spanning Trees          *

  *  by Dominik Schultes <[e-mail]>  *

  *                                                  *

  *                kruskal.h                         *

  *                                                  *

  *  April 13, 2003                                  *

  ****************************************************/

 #ifndef KRUSKAL_H

 #define KRUSKAL_H

 #include <vector>

 #include "../data_structures/edgeVector.h"

 #include "../data_structures/mst.h"

 template < typename EdgeType = Edge >

 class Kruskal

 {

  public:

     Kruskal(EdgeVector<EdgeType> &graph, MST &result)

         : _graph( graph ), _result( result )

         {

             computeMST();

         }

     ~Kruskal() {delete &_graph;}

  private:

     void computeMST();

     void initUnionFind();

     NodeID find(NodeID node);

     bool unite(NodeID node1, NodeID node2);

     EdgeVector<EdgeType> &_graph;

     MST &_result;

     std::vector<NodeID> _parent;

     std::vector<char> _height;

     EdgeCount edgesAddedToResult;

 };

 template < typename EdgeType >

 inline NodeID Kruskal<EdgeType>::find(NodeID node)

 {

     // find the root

     NodeID root = node;

     while (_parent[root] != root) root = _parent[root];

     // apply path compression

     NodeID tmp;

     while (_parent[node] != node) {

         tmp = _parent[node];

         _parent[node] = root;

         node = tmp;

     }

     return root;

 }

 template < typename EdgeType >

 inline bool Kruskal<EdgeType>::unite(NodeID node1, NodeID node2)

 {

     NodeID root1 = find(node1);

     NodeID root2 = find(node2);

     // A cycle would be produced. Therefore the union operation is cancelled.

     if (root1 == root2) return false;

     // Add the smaller tree to the bigger tree

     if (_height[root1] < _height[root2]) {

         _parent[root1] = root2;

     }

     else {

         _parent[root2] = root1;

         // Increment the height of the resulting tree if both trees have

         // the same height

         if (_height[root1] == _height[root2]) _height[root1]++;

     }

     return true;

 }

 #endif // KRUSKAL_H