C语言边比较函数详解：使用qsort对边按权重排序

在图算法中，我们经常需要对边进行排序，例如在 Kruskal 算法中，我们需要按照权重从小到大对边进行排序。在 C 语言中，我们可以使用 qsort() 函数来实现排序，但需要提供一个自定义的比较函数。

以下是一个典型的边比较函数 cmp()：

int cmp(const void *a, const void *b) {
    Edge *e1 = (Edge *)a;
    Edge *e2 = (Edge *)b;
    return e1->weight - e2->weight;
}

代码解释：

函数声明：
- 函数名：cmp
- 返回值类型：int，用于指示比较结果
- 参数：两个指向 void 类型的指针 a 和 b，这是因为 qsort() 函数需要一个通用的比较函数，可以处理任何数据类型。
类型转换：
- Edge *e1 = (Edge *)a; 和 Edge *e2 = (Edge *)b; 将传入的 void 指针强制转换为指向 Edge 结构体的指针，以便访问边的权重信息。
比较逻辑：
- return e1->weight - e2->weight; 计算两条边的权重差值并返回。
  - 如果返回值小于 0，则 e1 的权重小于 e2 的权重，e1 应该排在 e2 前面。
  - 如果返回值等于 0，则 e1 和 e2 的权重相等，它们可以保持原有顺序。
  - 如果返回值大于 0，则 e1 的权重大于 e2 的权重，e1 应该排在 e2 后面。

使用示例：

#include <stdio.h>
#include <stdlib.h>

typedef struct Edge {
    int src, dest, weight;
} Edge;

// ... (cmp 函数定义)

int main() {
    Edge edges[] = {{0, 1, 2}, {0, 2, 6}, {1, 2, 3}, {1, 3, 8}, {2, 4, 5}};
    int n = sizeof(edges) / sizeof(edges[0]);

    qsort(edges, n, sizeof(Edge), cmp);

    // 打印排序后的边
    for (int i = 0; i < n; i++) {
        printf('(%d, %d, %d) ', edges[i].src, edges[i].dest, edges[i].weight);
    }
    printf('
');

    return 0;
}

在这个例子中，我们首先定义了一个 Edge 结构体来表示边，然后创建了一个 edges 数组来存储多条边。最后，我们使用 qsort() 函数对 edges 数组进行排序，并将 cmp 函数作为比较函数传递给 qsort()。

通过使用自定义的边比较函数，我们可以方便地利用 qsort() 函数对边进行排序，从而实现各种图算法。