最小生成树(Prim算法和Kruskal算法)

Prim算法：

设图G =（V，E），其生成树的顶点集合为U。

①、把v0放入U。

②、在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。

③、把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。

其算法的时间复杂度为O(n^2)

#define MAXN  

bool flag[MAXN];  

double graph[MAXN][MAXN];   // graph[i][j] 表示节点i到j的距离  

   

double Prim(int n)  // 一共n个节点  

{  

    int i, j, k;  

    double t, lowcase[105], ans = 0;  

    for (i = 2; i <= n; i++)  

        lowcase[i] = graph[1][i], flag[i] = false;  

    flag[1] = true;  

   

    for (i = 1; i < n; i++)  

    {  

        k = 1;  

        t = INF;  

        for (j = 2; j <= n; j++)  

            if (!flag[j] && lowcase[j] < t)  

                k = j, t = lowcase[j];  

           

        ans += t;  

        flag[k] = true;  

   

        for (j = 1; j <= n; j++)  

            if (!flag[j] && graph[k][j] < lowcase[j])  

                lowcase[j] = graph[k][j];  

    }  

   

    return ans;  

} 

Kruskal算法：

假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。

// 并查集  

class UFSet  

{  

    int n;  

    int *root;  

   

public:  

    ~UFSet();  

    UFSet(int n);  

    int Find(int x);  

    void Merge(int x, int y);  

}*ufset;  

   

UFSet::UFSet(int n)  

{  

    this->n = n;  

    root = new int[n+1];  

   

    for (int i = 0; i < n; i++)  

        root[i] = i;  

}  

   

UFSet::~UFSet()  

{  

    delete[] root;  

}  

   

int UFSet::Find(int x)  

{  

    int t, r = root[x];  

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

    while (root[x] != r) // 路径压缩  

    {  

        t = root[x];  

        root[x] = r;  

        x = t;  

    }  

    return r;  

}  

   

void UFSet::Merge(int x, int y)  

{  

    int fx = Find(x);  

    int fy = Find(y);  

    if (fx != fy) root[fx] = fy;  

}  

   

// 边  

struct Edge  

{  

    int left;  

    int right;  

    double dis;  

   

    bool operator < (const Edge& e) const 

    {  

        return dis < e.dis;  

    }  

    bool operator > (const Edge& e) const 

    {  

        return dis > e.dis;  

    }  

}e;  

   

// 边集合  

priority_queue<Edge, vector<Edge>, greater<Edge> > pq;  

   

double Kruskal(int n)  

{  

    double ans = 0;  

   

    while (!pq.empty())  

    {  

        e = pq.top();  

        pq.pop();  

        int fx = ufset->Find(e.left);  

        int fy = ufset->Find(e.right);  

        if (fx != fy)  

        {  

            ufset->Merge(e.left, e.right);  

            ans += e.dis;  

        }  

    }  

       

    return ans;  

}