图的最小生成树

Prim

主要思想

从一个源点开始生长，每次从剩余的点中找到离生成树最近的点，加入生成树后更新剩下点到生成树的最小距离。

代码

#define INF 10000

void Print(int u, int v)
{
    printf("%d -> %d\n", u, v);
}

/// <summary>
/// 用Prim算法计算图的最小生成树权值
/// </summary>
/// <param name="n">图中点的个数</param>
/// <param name="M">图的权值矩阵（邻接矩阵）</param>
/// <param name="v0">起始点</param>
/// <param name="sum">最小生成树的权值和</param>
void Prim(int n, float** M, int v0, float& sum)
{
    float* lowCost = new float[n];  // 到生成树的最小距离
    int* lowVex = new int[n];       // 对应最小距离路径上的前一个点
    bool* set = new bool[n];        // 是否已加入生成树
    int v;                          // 当前加入最小生成树的点
    for (int i = 0; i < n; i++) {
        set[i] = false;             // 不在生成树中
        lowCost[i] = M[v0][i];      // 初始化为到v0的权
        lowVex[i] = v0;             // 生成树中只有v0
    }
    v = v0;   // 加入源点
    set[v] = true;
    sum = 0;
    for (int i = 0; i < n - 1; i++) {  // 逐个加入剩余的n-1个点
        float min = INF;  // 剩余点到生成树的最小距离
        int k;            // 最小距离对应的点
        for (int j = 0; j < n; j++) {
            if (!set[j] && M[v][j] < lowCost[j]) {
                min = lowCost[j];
                k = j;
            }
        }
        set[k] = true;       // 加入生成树
        v = k;
        Print(lowVex[v], v); // 输出加入的边
        sum += min;
        for (int j = 0; j < n; j++) {               // 更新剩余点到生成树的最小距离
            if (!set[j] && M[v][j] < lowCost[j]) {  // 通过刚刚加入生成树的v可以减少到生成树的距离
                lowCost[j] = M[v][j];
                lowVex[j] = v;
            }
        }
    }
}

Kruskal

主要思想

每次都从图中找到一条权值最小的边，如果这条边加入生成树后不会产生环则加入，否则尝试次一等的边。

判断是否会产生环

• 可以联想到在同一棵树上的任意两个点之间连线都会造成环，而Kruskal算法进行的过程中不是像Prim算法一样只有一颗树在生长，而是有多棵树（单独一个点也是树）。

• 连接不同树上的点不会造成环，因此只需要判断当前选择的边的两个顶点是否属于同一棵树就可以知道是否会产生环。

• 判断是否属于同一棵树可以通过判断所在树的树根是否相同来实现，所以一整棵树都可以用树根来代表。进而这整棵树都可以看成是由树根代表的集合。

• 判断是否属于同一个集合可以用并查集实现。这里的并查集实际上就是一个数组parent，记录了结点的双亲。通过双亲向上回溯，最后当parent[i]==i时，就表示树根为i。

代码

typedef struct Edge {
    int a, b;  // 边的两个顶点
    int w;     // 边的权值
}Edge;

void Sort(Edge edges[], int e)
{
    std::sort(edges, edges + e, [](const Edge& e1, const Edge& e2) { return e1.w < e2.w; });
}

int GetRoot(int parent[], int i)
{
    while (i != parent[i]) {
        i = parent[i];
    }
    return i;
}

/// <summary>
/// 用Kruskal算法计算最小生成树的权值和
/// </summary>
/// <param name="edges">图的所有边</param>
/// <param name="n">图的顶点数</param>
/// <param name="e">图的边数</param>
/// <param name="sum">最小生成树的权值和</param>
void Kruskal(Edge edges[], int n, int e, int& sum)
{
    int a, int b;
    int* parent = new int[n];
    sum = 0;
    for (int i = 0; i < n; i++) {
        parent[i] = i;  // 只有一个结点，自己就是树根
    }
    Sort(edges, e);     // 将所有边按找权值递增排序
    for (int i = 0; i < e; i++) {
        a = GetRoot(parent, edges[i].a); // a所在的树根
        b = GetRoot(parent, edges[i].b); // b所在的树根
        if (a != b) {
            parent[a] = b;  // 把树a挂到b上，作为b的子树
            sum += edges[i].w;
            Print(edges[i].a, edges[i].b);
        }
    }
}