学步园

最小生成树

假设在n个城市中要建立通信网络，那么连接n个点需要n-1条边。任意两个城市间建立通信网络都是需要费用的，这个可以认为是边的权值，用来表示响应的代价。对于n个顶点的连通图可以构建不同的生成树，而这个代价最小的生成树称为最小生成树。

最小生成树的MST特性，假设N = （V，{E}）是一个连通网，U是顶点集V的一个非空子集。若（u，v）是一条具有最小权值的边，其中u属于U，v属于V-U，则必存在一颗包含（u，v）的最小生成树，证明略。根据MST，求最小生成树有两种方法，普利姆（prim）和克鲁斯卡尔（kruskal）。

Prim算法

假设N = （V，{E}），TE是最小生成树中边的集合。算法从U = {u0}， u属于V，TE = {}开始，重复执行以下操作：在所有u属于U，v属于V - U的边（u，v）属于E中找一条权值最小的边（u0，v0）并入集合TE，同时v0并入U，直到 U = V为止。此时TE中必有n-1条边，则T = （V，{TE}）为N的最小生成树。

如图，计算过程如下：

//由于每个顶点都需要与其他的顶点比较找寻lowcost，所以本算法采用邻接矩阵存储，
//并利用辅助数组closedge来存放每个顶点的最小cost

void Prim(MGraph *G, int v){
    k = v;
    struct Closedge closedge[G -> vexnum];
    for(int i = 0; i < G -> vexnum; i++){
        if(i != k)
            closedge[i]= G -> arcs[k][i];
    }
    closedge[k].lowcost = 0;
    for(int i = 1; i < G -> vexnum; i++){
        k = min_closedge(closedge, G -> vexnum);            //寻找不为0的最小权值的顶点
        cout << k << " " << closedge[k].adjvex;
        for(int j = 0; j < G -> vexnum; j++){
            if(G -> arcs[k][j] < closedge[j])
                closedge[j] = G -> arcs[k][j];
        }
    }
}

int min_closedge(struct Closedge closedge[], int n){
    int min = INT_MAX, ans = 0;
    for(int i = 0; i < n; i++)
        if(closedge[i]!= 0 && min > closedge[i]){
            min = closedge[ans = i];
        }
    return ans;
}

Prim算法时间复杂度为O(n^2)，与顶点有关，与边无关，适用于稠密图。

Kruskal算法

假设连通网 N = （V，{ E }），令最小生成树的初始状态为只有n个顶点而无边的非连通图 T = （V，{ }），图中的每个顶点自称一个连通分量。在E中选取边中权值最小的，如果将此边加入T不产生回路，那么就将其加入T，否则舍去此边，寻找下一个最小权值的边，直到T中所有顶点都在同一连通分量上。由此可以看出Kruskal是基于边来做的，又每次都是挑选权值最小的边，所以在这里可以用一个指针数组存储边信息，并对其按权值由小到大排序，这样按数组由小到大遍历一次即可。为了判断新加入的边是否会构成回路，使用一个辅助数组
parent 来判断，parent[ i ] = k，表示顶点 i 和顶点 k 在边集合A中，而当k = 0时，表示集合A暂时到头。

#define MAX_NODE 20
struct Node{
    int begin, end, weight;
};

struct Node edge[MAX_NODE];

//此处的读入输入数据，并对edge排序省略
void kruskal(){
    int i = 0, n = 0, m = 0;
    int parent[MAX_NODE];
    for(; i < MAX_NODE; i++)
        parent[i] = i;
    for(i = 0; i < MAX_NODE; i++){
        n = find(parent, edge[i].begin);
        m = find(parent, edge[i].end);
        if(n != m){
            parent[n] = m;
            cout << edge[i].begin << " " << edge[i].end << " " << edge.weight << endl;
        }
    }
}

int find(int parent[], int v){
    while(parent[v] != v)
        v = parent[v];
    return v;
}

由于find时间复杂度O(loge)，一共循环e次，所以kruskal时间复杂度为O(eloge)，只和边个数有关，适合稀疏图。