今日主要学习了图中寻找最小生成树的算法：克鲁斯卡尔算法和普利姆算法
克鲁斯卡尔算法：
构建边结构体：用于存储图中的边信息，包括边的两个端点以及边的权值。
typedef struct Edge {
int src;
int dest;
int weight;
} Edge;

对边进行排序：可以使用 C 语言标准库中的 qsort 函数来实现对边数组的排序，按照边的权值从小到大排序。排序比较函数示例如下：
int compareEdges(const void *a, const void *b) {
Edge *edgeA = (Edge *)a;
Edge *edgeB = (Edge *)b;
return edgeA->weight - edgeB->weight;
}

并查集操作：为了判断加入一条边是否会形成环，需要使用并查集数据结构。并查集用于维护元素的分组信息，每个组有一个代表元素，通过查找操作可以快速确定两个元素是否属于同一组。以下是并查集的一些基本操作函数：
// 初始化并查集，每个顶点的父节点初始化为自身
void initUnionFind(int parent[], int numVertices) {
for (int i = 0; i < numVertices; i++) {
parent[i] = i;
}
}

// 查找元素所在集合的代表元素（根节点）
int find(int parent[], int i) {
if (parent[i] == i) {
return i;
}
return find(parent, parent[i]);
}

// 合并两个集合，将一个集合的根节点的父节点设置为另一个集合的根节点
void unionSets(int parent[], int x, int y) {
int setX = find(parent, x);
int setY = find(parent, y);
if (setX!= setY) {
parent[setX] = setY;
}
}

执行克鲁斯卡尔算法：遍历排序后的边数组，对于每条边，判断其两个端点是否属于不同的集合（即加入这条边不会形成环），如果是，则将这条边加入最小生成树的边集合，并合并两个端点所在的集合。
void kruskal(Graph *graph) {
int numVertices = graph->numVertices;
Edge *result = (Edge *)malloc((numVertices - 1) * sizeof(Edge)); // 存储最小生成树的边
int e = 0; // 结果数组的索引
int i = 0; // 排序后的边数组的索引

// 对图中的边进行排序
Edge *edges = getEdges(graph);  // 假设已有函数获取图的所有边
qsort(edges, graph->numEdges, sizeof(Edge), compareEdges);

// 初始化并查集
int *parent = (int *)malloc(numVertices * sizeof(int));
initUnionFind(parent, numVertices);

while (e < numVertices - 1 && i < graph->numEdges) {
    Edge nextEdge = edges[i++];
    int x = find(parent, nextEdge.src);
    int y = find(parent, nextEdge.dest);
    if (x!= y) {
        e++;
        result[e - 1] = nextEdge;
        unionSets(parent, x, y);
    }
}

// 输出最小生成树的边及总权值
int totalWeight = 0;
for (int j = 0; j < e; j++) {
    printf("Edge: %d - %d, Weight: %d\n", result[j].src, result[j].dest, result[j].weight);
    totalWeight += result[j].weight;
}
printf("Total weight of minimum spanning tree: %d\n", totalWeight);

free(edges);
free(result);
free(parent);

}
普利姆算法：
定义辅助数组：用于记录每个顶点到已生成树的最小距离，以及标记顶点是否已被加入已生成树。

define INF 99999 // 表示无穷大，用于初始化未连接顶点的距离

int minKey(int key[], bool mstSet[], int numVertices) {
int min = INF, min_index;
for (int v = 0; v < numVertices; v++) {
if (mstSet[v] == false && key[v] < min) {
min = key[v];
min_index = v;
}
}
return min_index;
}

执行普利姆算法：从一个起始顶点开始，初始化距离数组和标记数组，然后重复选择距离最小的未加入顶点，更新与其相邻顶点的距离，直到所有顶点都被加入已生成树。
void prim(Graph *graph, int startVertex) {
int numVertices = graph->numVertices;
int parent[numVertices]; // 存储最小生成树中每个顶点的父节点
int key[numVertices]; // 存储每个顶点到已生成树的最小距离
bool mstSet[numVertices]; // 标记顶点是否已在最小生成树中

// 初始化
for (int i = 0; i < numVertices; i++) {
    key[i] = INF;
    mstSet[i] = false;
}

key[startVertex] = 0;
parent[startVertex] = -1;  // 起始顶点没有父节点

for (int count = 0; count < numVertices - 1; count++) {
    int u = minKey(key, mstSet, numVertices);
    mstSet[u] = true;

    AdjListNode *temp = graph->adjLists[u];
    while (temp!= NULL) {
        int v = temp->dest;
        int weight = temp->weight;
        if (mstSet[v] == false && weight < key[v]) {
            parent[v] = u;
            key[v] = weight;
        }
        temp = temp->next;
    }
}

// 输出最小生成树的边及总权值
int totalWeight = 0;
for (int i = 1; i < numVertices; i++) {
    printf("Edge: %d - %d, Weight: %d\n", parent[i], i, key[i]);
    totalWeight += key[i];
}
printf("Total weight of minimum spanning tree: %d\n", totalWeight);

}