最小生成树

• 是一棵树
  • 无回路
  • v 个顶点一定有 v-1 条边
• 是生成树
  • 包含全部顶点
  • v-1 条边都在图里
  • 向生成树中加入一条边都一定构成回路
• 边权重和最小

最小生成树问题的相关算法都基本按照贪心算法来实现

Prim算法

形象地来说，此算法就是让一棵小树长大——在图中任意选取一结点作为树根，然后继续在图中选取结点让这棵树长大

代码：

Vertex FindMinDist (MGraph graph, WeightType dist[]){
    /* 返回未收录顶点之中dist的最小者 */
    Vertex minV, v;
    WeightType minDist = INFINITY;
    for (v = 0; v < graph->nv; ++v) {
        if (dist[v] != 0 && dist[v] < minDist){ // 若v被收录，且dist[v]更小
            minDist = dist[v];  // 更新最小距离
            minV = v;   // 更新对应顶点
        }
    }
    if (minDist < INFINITY) // 若找到最小的dist
        return minV;
    else    // 不存在 返回-1
        return ERROR;
}


int Prim(MGraph graph, MGraph MST){
    /* 将最小生成树保存为邻接表储存的图MST 返回最小权重和 */
    WeightType dist[MAXSIZE], totalWeight;
    Vertex parent[MAXSIZE], v, w;
    int vCount;
    Edge e;
    /* 初始化，默认初始点下标为0 */
    for (v = 0; v < graph->nv; ++v) {   // 若v到w有直接的边 则graph->g[w][v]定义为INFINITY
        dist[v] = graph->g[0][v];
        parent[v] = 0;  // 定义所有顶点的父顶点都是初始点0
    }
    totalWeight = 0;    // 初始化权重
    vCount = 0; // 初始化收录的顶点数
    MST = CreateGraph(graph->nv);
    e = (Edge)malloc(sizeof(struct ENode)); // 建立空的边结点
    
    dist[0] = 0;    // 收录初始点0进入MST
    vCount++;
    parent[0] = -1; // 初始化树根结点的父节点为-1
    
    while (1){
        v = FindMinDist(graph, dist);
        if (v == ERROR)
            break;
        e->v1 = parent[v];
        e->v2 = v;
        e->weight = dist[v];
        InsertEdge(MST, e);
        totalWeight += dist[v];
        dist[v] = 0;
        vCount++;
        for (w = 0; w < graph->nv; ++w) // 对图中每一个顶点
            if (dist[w] != 0 && graph->g[v][w] < INFINITY){ // w未被收录并且w和v是邻接点
                if (graph->g[v][w] < dist[w]){  // 收录v使得dist[w]变得更小 更新dist[w]
                    dist[w] = graph->g[v][w];
                    parent[w] = v;
                }
            }
    }
    if (vCount < graph->nv)
        totalWeight = ERROR;
    return totalWeight;
}

代码分析：

• 首先对 dist[] 数组进行初始化，使数组值下标所在结点与初始结点的权重，parent[] 数组全部初始化为0，建立只有结点的邻接表存储的图MST来保存最小生成树，建立空结点e
• 将初始点0收录进MST，即将 dist[0] 的值设为0，收录的顶点数+1，根节点的父节点设为-1
• 进入循环，直至所有可以收录的结点都被收录
  • 调用 FindMinDist() 函数，找到未收录结点中 dist 的最小者 v
  • 将 v 结点加入到树中，即边的一端接 v 的父结点，一端接 v 结点，将边插入到MST树中
  • 调整总权重，收录的顶点数加一
  • 如有其他结点到 v 结点比已知路径断，对 dist 和 parent 数组进行更新
• 判断是否有未访问结点，如有，则说明图有独立结点，返回-1；否则，返回总权重

Kruskal算法

Kruskal算法的主要思想是让森林合并成一棵树——也就是从整个图中从权值最小的边开始，依次挑选，判断是否构成回路，一条边及其两端的两个结点可看作一棵树，挑选完n-1条边之后，形成了n-1棵树，将之合并为一棵生成树

• 那么应该如何选取最小权重的边呢？

  ——利用最小堆

• 如何判断找出来的边在已有的树中不构成回路呢？

  ——利用并查集

最小堆的定义

最小堆的调整：

/* 将n个元素的边数组以ESet[p]为根的子堆调整为关于Weight的最小堆 */
void PercDown(Edge Eset, int p, int n){ 
    int parent, child;
    struct ENode x;
    x = Eset[p];	// 取出根节点存放的值
    for (parent = p; (parent*2) + 1 < n; parent = child) {
        child = parent*2 + 1;
        if ((child != n-1) && (Eset[child].weight > Eset[child+1].weight))
            child++;	// child指向左右结点中最小者
        if (x.weight <= Eset[child].weight)	// 找到了合适位置
            break;
        else	// 向下过滤结点
            Eset[parent] = Eset[child];
    }
    Eset[parent] = x;
}

最小堆的初始化：

/* 将图的边存入数组ESet中，并且初始化为最小堆 */
void InitializeESet(LGraph graph, Edge eSet){
    Vertex v;
    PtrToAdjVNode w;
    int eCount;
    eCount = 0;
    /* 将图的边存入数组eSet */
    for (v = 0; v < graph->nv; ++v)
        for (w = graph->g[v].firstEdge; w; w = w->next)
            if (v < w->adjv){	// 避免重复录入的无向图的边， 只收v1<v2的边
                eSet[eCount].v1 = v;
                eSet[eCount].v2 = w->adjv;
                eSet[eCount++].weight = w->weight;
            }
    /* 初始化为最小堆 */
    for (eCount = graph->ne/2; eCount >= 0; --eCount)
        PercDown(eSet, eCount, graph->ne);
}

/* 给定当前堆的的大小currentSize 将当前最小边位置弹出并调整堆 */
int GetEdge(Edge eSet, int currentSize){    
    Swap(&eSet[0], &eSet[currentSize-1]);	// 将最小边与当前堆的最后一个位置的边交换
    PercDown(eSet, 0, currentSize-1);
    return currentSize-1;	// 返回最小边所在位置
}

顶点并查集的定义

开始之前：

typedef Vertex ElementType;
typedef Vertex  SetName;
typedef ElementType SetType[MAXSIZE];

初始化并查集：

void InitializeVSet(SetType s, int n){  // 初始化并查集
    ElementType x;
    for (x = 0; x < n; ++x)	// 集合元素全部初始化为-1
        s[x] = -1;
}

并集运算：

void Union(SetType s, SetName root1, SetName root2){
	/* 保证小集合并入大集合 */
    if (s[root1] < s[root2]){	
        s[root2] += s[root1];
        s[root1] = root2;
    } else {
        s[root1] += s[root2];
        s[root2] = root1;
    }
}

查找：

SetName Find(SetType s, ElementType x){ 
    if (s[x]  < 0)	// 找到集合的根
        return x;
    else
        return s[x] = Find(s, s[x]);
}

检查找出的边是否在已有的子集中构成回路：

/* 检查连接v1和v2的边是否存在现有的最小生成树子集中构成回路 */
bool CheckCycle(SetType vSet, Vertex v1, Vertex v2){
    Vertex root1, root2;
    root1 = Find(vSet, v1);	// 得到v1所属联通集名称
    root2 = Find(vSet, v2);	// 得到v2所属联通集名称
    if (root1 == root2)	// 判断v1和v2是否已经相连
        return false;	// 相连 不收录
    else {
        Union(vSet, root1, root2);	// 不相连 将v1和v2并入同一联通集 
        return true;
    }
}

Kruskal算法实现

代码：

/* 将最小生成树保存为邻接表存储的图MST 并返回最小权重和 */
int Kruskal(LGraph graph, LGraph MST){ 
    WeightType totalWeight;
    int eCount, nextEdge;
    SetType vSet;	// 顶点数组
    Edge eSet;	// 边数组
    
    InitializeVSet(vSet, graph->nv);	// 初始化顶点并查集
    eSet = (Edge)malloc(sizeof(struct ENode) * graph->ne);
    InsertEdge(graph, eSet);	// 初始化边的最小堆
    
    MST = CreateGrape(graph->nv);	// 创建只有顶点没有边的图
    totalWeight = 0;	// 总权重
    eCount = 0;	// 总收录的边数
    nextEdge = graph->ne;	// 原始边集的规模 

    while (eCount < graph->nv-1){
        nextEdge = GetEdge(eSet, nextEdge);	// 从边集中得到最小边的位置
        if (nextEdge < 0)	// 边集空
            break;
        if (CheckCycle(vSet, eSet[nextEdge].v1, eSet[nextEdge].v2) == true){
            /* 如此边可以收录 */
            InsertEdge(MST, eSet+nextEdge);	// 将边插入图
            totalWeight += eSet[nextEdge].weight;
            eCount++;
        }
    }

    if (eCount < graph->nv-1)	// 边数不够 
        totalWeight = -1;	// 设置错误标记
    return totalWeight;
}

代码说明：

• 初始化顶点并查集以及边的最小堆
• 初始化目标图MST
• 循环寻找最小边（直至收录了graph->nv-1条边或者所有边都被收录），判断此边是否可以收录-
  • 如可以，插入图MST，并将相应的变量进行更新
  • 不可以，继续寻找最小边