Kruskal算法

本文作业主要实现 Max-Spacing  k-Clusterings ，利用Kruskal算法实现，数据结构采用了并查集。

步骤：

(1) 每个点分别在自己的cluster中。

(2)令p,q =最小权重的边的两个点，且两个点在分离的cluster中。

(3)将p,q两个点融合进一个cluster中。

重复上述步骤直到 cluster 的数目为 k 为止。

1.用优先队列存储边，按照权重的从小到大排列。

2.用并查集实现find, union操作。

并查集代码如下：

/************并查集**********/
class UnionFind
{
public:
    UnionFind(int len)//初始化
    {
        length = len;
        rank.resize(len);
        parent.resize(len);
        for(int i = 0; i < length; i++)
        {
            rank[i] = 0;
            parent[i] = i;
        }
    }
/********判断能否融合*****/
    bool unite(int x, int y)
    {
        int a = find(x);
        
        int b = find(y);
        if(a == b)
        {
            return false;
        } else {
            if(rank[a] == rank[b])
            {
                parent[a] = b;
                rank[b]++;
            } else if(rank[a] < rank[b]) {
                parent[a] = b;
            } else {
                parent[b] = a;
            }
        }
        return true;
    }
    int find(int x) //返回根结点
    {
        if(parent[x] == x)
        {
            return x;
        } else {
            return find(parent[x]);
        }
    }
public:
    vector<int> rank; 
        //rank[x] = the max number of hops from a leaf to x
    vector<int> parent; //根结点
    int length; 
};    

并查集的小细节：

(1)根节点以外的rank值是不发生变化的。

(2)根节点发生变化时也只有融合两个rank值相同的时候，被融合的那一方rank值是加1的。

关于并查集还有根据path-compression的优化方案。在此不再赘述。

2.关于Kruskal 算法的实现，代码仅供参考。

//优先队列根据边的权重排列,
//union-find来识别会形成环的边
/*************优先队列+并查集***********/
class Kruskal
{
public:
    Kruskal(int k, Graph graph)
    {

        length = graph.numVertexes;
        int cnt = length;
        UnionFind set(length);
        init_pq(graph);
        while(cnt > k)
        {
            EdgeNode *temp = new EdgeNode(0, 0, 0);            
            temp = pq.top();
            pq.pop();
            int x = temp->v;
            int y = temp->w;
            if(set.unite(x, y))
            {
                cnt--;
            }
            delete temp;
        }
        while(!pq.empty())
        {
            EdgeNode *p = new EdgeNode(0,0,0);
            p = pq.top();
            if(set.find(p->v) != set.find(p->w))
            {
                cout << "Max spacing:";
                cout <<  p->dist << endl;
                break;
            }
            pq.pop();
            delete p;
        }
        ofstream fout;
        fout.open("output.txt");
        for(int i = 0; i < length; i++)
        {
            fout << "parent[" << i << "]:" << set.parent[i] << endl;
        }
    }    

    void init_pq(Graph graph)
    {
        for(int i = 0; i < length; i++)    
        {
            EdgeNode *p = new EdgeNode(0,0,0);
            p = graph.vertex[i].firstEdge;
            while(p)
            {
                pq.push(p);
                p = p->next;
            }
            delete p;
        }
    }
public:
    int length;
    //优先队列
    priority_queue<EdgeNode*, vector<EdgeNode*>, mycompare> pq;
};