数据结构与算法-最小生成树

概念

连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一颗树的n-1条边。

构造连通网的最小代价生成树简称为最小生成树。

Prim 算法

算法思路

定义2个数组，adjvex 用来保存相关顶点下标，lowcost 保存顶点之间的权值
初始化2个数组, 从v0开始寻找最小⽣成树, 默认v0是最小生成树上第一个顶点
循环lowcost 数组,根据权值,找到顶点 k;
更新lowcost 数组
循环所有顶点,找到与顶点k 有关系的顶点. 并更新lowcost 数组与adjvex 数组;

注意更新lowcost 数组与adjvex 数组的条件:

与顶点k 之间有连接

当前结点 j 没有加入过最小生成树;

顶点 k 与当前顶点 j 之间的权值小于顶点j 与其他顶点 k 之前的权值. 则更新. 简单说就是要比较之前存储的值要小,则更新;

代码实现

/*
 Prim算法生成最小生成树
 */

void MiniSpanTree_Prim(MGraph G) {
    int min, i, j, k;
    int sum = 0;
    
    int adjvex[MAXVEX];
    int lowcost[MAXVEX];
    
    lowcost[0] = 0;
    adjvex[0] = 0;
    
    for (i = 1; i < G.numVertexes; i++) {
        lowcost[i] = G.arc[0][i];
        adjvex[i] = 0;
    }
    
    for (i = 1; i < G.numVertexes; i++) {
        min = INFINITYC;
        
        j = 1;
        k = 0;
        for (j = 1; j < G.numVertexes; j++) {
            if (lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
        }
        
        printf("(V%d, V%d) = %d\n", adjvex[k], k , G.arc[adjvex[k]][k]);
        sum += G.arc[adjvex[k]][k];
        lowcost[k] = 0;
        
        for (j = 1; j < G.numVertexes; j++) {
            if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j]) {
                lowcost[j] = G.arc[k][j];
                adjvex[j] = k;
            }
        }
    }
    printf("sum = %d\n", sum);
}

Kruskal 算法

算法思路

将邻接矩阵转化成边表数组；
对边表数组根据权值按照从小到大的顺序排序；
遍历所有的边，通过parent 数组找到边的连接信息，避免闭环问题；
如果不存在闭环问题,则加入到最小生成树中，并且修改parent 数组；

代码实现

typedef struct Edge {
    int begin;
    int end;
    int weight;
} Edge;

/*
 Prim算法生成最小生成树
 */

void Swapn(Edge *edges, int i, int j) {
    int temp;
    temp = edges[i].begin;
    edges[i].begin = edges[j].begin;
    edges[j].begin = temp;
    
    temp = edges[i].end;
    edges[i].end = edges[j].end;
    edges[j].end = temp;
    
    temp = edges[i].weight;
    edges[i].weight = edges[j].weight;
    edges[j].weight = temp;
}

void Sort(Edge edges[], MGraph *G) {
    int i, j;
    for (i = 0; i < G->numEdges; i++) {
        for (j = i + 1; j < G->numEdges; j++) {
            if (edges[i].weight > edges[j].weight) {
                Swapn(edges, i, j);
            }
        }
    }
}

int Find(int *parent, int f) {
    while (parent[f] > 0) {
        f = parent[f];
    }
    return f;
}

void MiniSpanTree_Kruskal(MGraph G)  {
    int i, j, n, m;
    int sum = 0;
    int k = 0;
    
    Edge edges[MAXVEX];
    
    for (i = 0; i < G.numVertexes; i++) {
        for (j = i + 1; j < G.numVertexes; j++) {
            if (G.arc[i][j] < INFINITYC) {
                edges[k].begin = i;
                edges[k].end = j;
                edges[k].weight = G.arc[i][j];
                k++;
            }
        }
    }
    
    Sort(edges, &G);
    
    int parent[MAXVEX] = {0};
    for (i = 0; i < G.numEdges; i++) {
        m = Find(parent, edges[i].begin);
        n = Find(parent, edges[i].end);
        
        if (m != n) {
            parent[m] = n;
            sum += edges[i].weight;
            printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
        }
    }
    printf("sum = %d\n", sum);
}