今天开始学算法系列 -- kruskal

    在之前，我曾经写过一边关于最小生出树的算法--prime，今天是另一个算法kruskal，这两个算法的复杂度是一样的。主要和prime在代码实现上的区别在于，kruskal算法是把焦点集中在了边上， 而prime算法是在节点上，一个是对优先队列中的点进行操作，一个是对于优先队列中的边进行操作。详细的算法细节大家可以google。
   在kruskal算法中应用到了一个很重要也很有用的数据结构 --并查集
   并查集对于连通图的连同性的判断很有用，kruskal就是利用它来判断所使用的边是否会使MST产生环
   直接上伪代码：
   initGraph();
   union_find m;  //定义并查集结构
   put edge to priority_queue;
   while(queue is not empty)
          m = queue.pop();
          queue.pop();
          if connected(m.src,m.end)  //如果边的两个node是在一个集合里
              continue;
          else
             //就算是MST里的一条边

   思路还是很清楚的，直接上代码了：
   

#include <queue>
#include <vector>

#define MAXN 4
int ID[MAXN] = { 0 };
int rank[MAXN];
class union_find
{
public:
    union_find();
    int find_root(int x);
    void connect(int x, int y);
    bool isConnected(int x, int y);
};

bool union_find::isConnected(int x, int y)
{
    int xRoot = find_root(x);
    int yRoot = find_root(y);
    if (xRoot == yRoot)
    {
        printf("Has Connected\n");
        return true;
    }
    else
        return false;
}


union_find::union_find()
{
    for (int i = 0; i < MAXN; i++)
    {
        ID[i] = i;
        rank[i] = 1;
    }
}

int union_find::find_root(int x)
{
    if (ID[x] == x)
        return x;
    return find_root(ID[x]);
}

void union_find::connect(int x, int y)
{
    int xRoot = find_root(x);
    int yRoot = find_root(y);
    if (xRoot == yRoot)
    {
        printf("Has Connected\n");
        return;
    }
    if (rank[xRoot] >= rank[yRoot])
    {
        rank[xRoot] += 1;
        ID[yRoot] = ID[xRoot];
    }
    else
    {
        rank[yRoot] += 1;
        ID[xRoot] = ID[yRoot];
    }
}


#define MAXNODE 4
int edge[4][4];
struct doubleEdge
{
    int src;
    int end;
    int cost;
};

void initGraph()
{
    for (int i = 0; i < MAXNODE; i++)
        for (int j = 0; j < MAXNODE; j++)
            edge[i][j] = -1;


}

struct cmp2
{
    bool operator()(doubleEdge x, doubleEdge y)
    {
        return x.cost > y.cost;
    }
};

int _tmain(int argc, _TCHAR* argv[])
{
    initGraph();
    union_find m;
    doubleEdge edge1 = { 0, 3, 1 };
    doubleEdge edge2 = { 0, 2, 7 };
    doubleEdge edge3 = { 0, 1, 3 };
    doubleEdge edge4 = { 2, 3, 2 };
    doubleEdge edge5 = { 2, 1, 4 };
    std::priority_queue<doubleEdge, std::vector<doubleEdge>, cmp2> que;
    que.push(edge1);
    que.push(edge2);
    que.push(edge3);
    que.push(edge4);
    que.push(edge5);

    while (!que.empty())
    {
        doubleEdge tmp = que.top();
        que.pop();
        if (m.isConnected(tmp.src, tmp.end))
        {
            //printf("This edge is in MST");
            continue;
        }
        else
        {
            m.connect(tmp.src, tmp.end);
            printf("%d,%d\n", tmp.src, tmp.end);
        }
    }


    return 0;
}