基于邻接矩阵的克鲁斯卡尔算法和普利姆算法

typedef struct {
    int vexs[5]; // 顶点
    int arcs[5][5]; //领接矩阵
    int vexnum, arcnum; //顶点数和边数
} AmGraph;
//region 克鲁斯卡尔算法
/**
 * 克鲁斯卡尔算法  最小生成树 以边为排序
 * 算法思想：
 *  将边按照权值进行升序排序，依次选择权值最小的、且不构成环的边
 * 算法步骤：
 *  1.需要借助辅助结构体数组，用于存储边的起始点start，和终点end 以及权值weight
 *  2.初始化边的数组（边数组），边数组的大小为边的大小。采用二维数组进行初始化
 *  3.将初始化完成之后的边数组，按照权值weight的大小进行升序排序
 *  4.初始化父节点数组parent（父数组），初始值设为-1，表示根节点。父数组的大小等于顶点的大小
 *  5.for循环边数组生成最小生成树
 *      ①：拿取当前节点的 起始节点start，终点节点end
 *      ②：在父数组中，分别找到这两个节点的根节点。采用while循环 =-1时说明找到根节点
 *      ③：如果两个节点的根节点不相同说明不存在环，输出结果。
 *      ④：合并根节点，将终点节点的父节点设为起始节点。（start为根节点） parent[end] = start
 *      重复上述步骤
 */
typedef struct {
    int start;
    int end;
    int weight;
} Edge;
// Kruskal算法需要的辅助函数，用于比较边的权值
int CompareEdges(const void *a, const void *b) {
    return ((Edge *) a)->weight - ((Edge *) b)->weight;
}
void kruskal(AmGraph *g) {
    Edge edges[g->arcnum]; // 存储边的数组
    int index = 0;

    // 初始化edges数组
    for (int i = 0; i < g->vexnum; ++i) {
        for (int j = i + 1; j < g->vexnum; ++j) {
            if (g->arcs[i][j] == INT_MAX) {
                continue;
            }
            if (g->arcs[i][j] != -1) {
                edges[index].start = i;
                edges[index].end = j;
                edges[index].weight = g->arcs[i][j];
                index++;
            }
        }
    }

    // 对边按权值升序排序
    qsort(edges, index, sizeof(Edge), CompareEdges);

    // 初始化并查集
    int parent[g->vexnum];
    for (int i = 0; i < g->vexnum; i++) {
        parent[i] = -1;
    }

    printf("Kruskal算法生成的最小生成树边集合:\n");
    for (int i = 0; i < index; i++) {
        int start = edges[i].start;
        int end = edges[i].end;

        // 查找两个顶点的根节点
        while (parent[start] != -1) { // 找到start的根节点  =-1时start就是根节点
            start = parent[start];
        }
        while (parent[end] != -1) { // 找到end的根节点
            end = parent[end];
        }

        // 如果两个顶点的根节点不相同，说明不构成环路
        if (start != end) {
            printf("(%d, %d) -> %d\n", edges[i].start, edges[i].end, edges[i].weight);
            parent[end] = start; // 合并,保留一个根节点
        }
    }
}
//endregion

//region 普利姆算法
/**
 * 普利姆算法  最小生成树 以点为排序
 * 算法思想：
 *  从起始节点开始，选择与起始节点连接的边最小的、且不构成环的节点，作为下一起始节点。
 * 算法步骤：
 *  b站，up主详细讲解
 *  https://www.bilibili.com/video/BV1Ua4y1i7tf/?spm_id_from=333.788&vd_source=99c6f1474e6726258fc34b2c9334a458
 *  1.初始化辅助数组
 *  2.起始节点设为已访问，即weight设为0
 *  3.for循环遍历，注意遍历次数-1，因为已经将起始节点标记为已访问
 *  4.寻找最短的邻接点
 *  5.输出结果
 *  6.将该点标记为已访问，即weight设为0
 *  7.更新辅助数组
 */
typedef struct {
    int adjvex; // 顶点序号
    int weight; // 权值  ，weight=0表示已经访问
} ShortArc; // 记录最短边
void Prim(AmGraph *g, int start) {
    ShortArc shortArc[g->vexnum];

    //初始化辅助数组
    for (int i = 0; i < g->vexnum; ++i) {
        shortArc[i].weight = g->arcs[start][i];
        shortArc[i].adjvex = start;
    }

    // 标记已经被访问过，加入结果集中
    shortArc[start].weight = 0;

    printf("Prim算法生成的最小生成树边集合:\n");
    for (int i = 0; i < g->vexnum - 1; i++) {
        int k = INT_MAX;
        int minadj;
        // 寻找最短边的邻接点 minadj
        for (int j = 0; j < g->vexnum; ++j) {
            if (shortArc[j].weight < k && shortArc[j].weight != 0) {
                minadj = j;
                k = shortArc[j].weight;
            }
        }

        // 输出最小生成树的路径
        printf("(%d,%d)=>%d\n", shortArc[minadj].adjvex, minadj, shortArc[minadj].weight);
        shortArc[minadj].weight = 0; //  标记已经被访问过。加入结果集中

        //调整shortArc数组
        for (int j = 0; j < g->vexnum; ++j) {
            if (g->arcs[minadj][j] < shortArc[j].weight) {
                shortArc[j].weight = g->arcs[minadj][j];
                shortArc[j].adjvex = minadj;
            }
        }
    }
}
//endregion
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139