最小生成树(C语言, prim算法)

图（来源：<<大话数据结构>>p250）

#include <stdio.h>#include <stdlib.h>#include <stdbool.h>/* * 邻接矩阵, prim普里姆算法(属贪婪算法)，无向图，最小生成树 * 代码实现<<大话数据结构>>p250 图7-6-6,v0至v8分别用ABCDEFGHI代替（不过打印过程还是用的下标） * 最终成生n-1条边的树，路径权值和最小 */#define MAX 9#define INFINITY 65535// 图结构体typedef struct {    char vexs[MAX]; // 顶点的数组，顶点类型为了简单使用char    int arc[MAX][MAX]; // 边表二维数组，值为权    int numVex;}GRAPH, *PGRAPH;void create(PGRAPH);void gprint(GRAPH);void prim(GRAPH);void prim(GRAPH graph){    int i, j, k, min;    // 保存相关节点的数组（也可叫作父子(前后)关系，下标为当前节点，值为前一个节点，形成1条边）    int adjVex[MAX];    // 保存节点相关的边的最小权值(这个是随着程序不断迭代而更新的)    int lowcost[MAX];    // 循环处理前的初始化工作    adjVex[0] = 0; // 以第1个顶点为开头，直接加入v0节点    lowcost[0] = 0; // v0节点不需要再计算权值，标识为0，0还有个意思表示该节点已经加入最小生成树    // 使用v0节点相关的数据，初始化上面2个数组    for (i=0; i<graph.numVex; i++) {        //先全部初始化为0，表示所有节点的前1个节点都先为v0        adjVex[i] = 0;         // v0节点相关的边权值加入数组，因为入口是v0节点，这些是目前可以看到的相关的边        lowcost[i] = graph.arc[0][i];     }    /*     * 开始循环处理，次数为n-1，n为节点数     */     // v0入口节点已经加入过数组不需要处理，所以从1开始    for (i=1; i<graph.numVex; i++) {        // 每轮都需要计算当前未加入最小生成树中的节点相关的最小权的边        int min = INFINITY;         // 先在lowcost数组中找出当前可以看到的边中，权值最小的那条边            for (j=1; j<graph.numVex; j++) {            if (lowcost[j] !=0 && lowcost[j] < min) {                min = lowcost[j];                k = j;            }         }        // 新找到的最小权值的边的相关节点为新查找根节点，标识为0，放入最小生成树        lowcost[k] = 0;        printf("%d->%d\n", adjVex[k], k); //adjVex可以知道相关节点前后关系        // 把符合条件的与新根节点(行)有关的边、节点信息更新到数组，供下一轮查找        for (j=1; j<graph.numVex; j++) {            if (lowcost[j] != 0 && graph.arc[k][j] < lowcost[j]) {                lowcost[j] = graph.arc[k][j];                adjVex[j] = k; // 只要找到的更新其前节点为k;            }        }    }}void create(PGRAPH g){    int i, j;    g->numVex = 9;    // 创建顶点    g->vexs[0] = 'A';    g->vexs[1] = 'B';    g->vexs[2] = 'C';    g->vexs[3] = 'D';    g->vexs[4] = 'E';    g->vexs[5] = 'F';    g->vexs[6] = 'G';    g->vexs[7] = 'H';    g->vexs[8] = 'I';    // 初始化边表    for (i=0; i<g->numVex; i++) {        for (j=0; j<g->numVex; j++) {            g->arc[i][j] = INFINITY;            if (j == i)                g->arc[i][j] = 0; //行列相等时表示自身，标识为0        }    }    // 添加边及权值    // A v0, B v1, C v2, D v3, E v4, F v5, G v6, H v7, I, v8    g->arc[0][1] = 10;    g->arc[1][0] = 10;    g->arc[0][5] = 11;    g->arc[5][0] = 11;    g->arc[1][2] = 18;    g->arc[2][1] = 18;    g->arc[1][8] = 12;    g->arc[8][1] = 12;    g->arc[1][6] = 16;    g->arc[6][1] = 16;    g->arc[2][8] = 8;    g->arc[8][2] = 8;    g->arc[2][3] = 22;    g->arc[3][2] = 22;    g->arc[3][8] = 21;    g->arc[8][3] = 21;    g->arc[3][6] = 24;    g->arc[6][3] = 24;    g->arc[3][7] = 16;    g->arc[7][3] = 16;    g->arc[3][4] = 20;    g->arc[4][3] = 20;    g->arc[4][7] = 7;    g->arc[7][4] = 7;    g->arc[4][5] = 26;    g->arc[5][4] = 26;    g->arc[5][6] = 17;    g->arc[6][5] = 17;    g->arc[6][7] = 19;    g->arc[7][6] = 19;}void gprint(GRAPH graph){    int i, j;    for (i=0; i<graph.numVex; i++) {        for (j=0; j<graph.numVex; j++){            printf("%6d ", graph.arc[i][j]);        }        putchar('\n');    }}int main(void){    GRAPH graph;    create(&graph);    gprint(graph);    prim(graph);    return 0;}

output

[root@8be225462e66 c]# gcc prim.c && ./a.out     0     10  65535  65535  65535     11  65535  65535  65535    10      0     18  65535  65535  65535     16  65535     12 65535     18      0     22  65535  65535  65535  65535      8 65535  65535     22      0     20  65535     24     16     21 65535  65535  65535     20      0     26  65535      7  65535    11  65535  65535  65535     26      0     17  65535  65535 65535     16  65535     24  65535     17      0     19  65535 65535  65535  65535     16      7  65535     19      0  65535 65535     12      8     21  65535  65535  65535  65535      00->10->51->88->21->66->77->47->3[root@8be225462e66 c]#

©著作权归作者所有：来自51CTO博客作者sndapk的原创作品，如需转载，请注明出处，否则将追究法律责任

好知识，才能预见未来

赞赏

0人进行了赞赏支持

图（来源：<<大话数据结构>>p250）

好知识，才能预见未来

更多相关文章

随机推荐