用C语言写出一个用快速排序算法和克鲁斯卡尔算法生成一个由邻接矩阵存储的有权无向图的最小生成树的程序

以下是用C语言实现快速排序算法和克鲁斯卡尔算法生成一个由邻接矩阵存储的有权无向图的最小生成树的程序：

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

#define MAXVEX 100
#define MAXEDGE 100

typedef struct
{
    int u, v; // 边的起始点和终止点
    int w; // 权值
} Edge;

typedef struct
{
    int vexs[MAXVEX]; // 存储顶点的数组
    int matrix[MAXVEX][MAXVEX]; // 存储邻接矩阵的二维数组
    int num_vexs, num_edges; // 顶点数和边数
} Graph;

// 快速排序算法
void quick_sort(Edge edges[], int left, int right)
{
    if (left < right)
    {
        int i = left, j = right;
        Edge pivot = edges[i]; // 以第一个元素为枢轴
        while (i < j)
        {
            while (i < j && edges[j].w >= pivot.w)
                j--;
            if (i < j)
                edges[i++] = edges[j];
            while (i < j && edges[i].w <= pivot.w)
                i++;
            if (i < j)
                edges[j--] = edges[i];
        }
        edges[i] = pivot;
        quick_sort(edges, left, i - 1);
        quick_sort(edges, i + 1, right);
    }
}

// 克鲁斯卡尔算法生成最小生成树
void kruskal(Graph g)
{
    Edge edges[MAXEDGE]; // 存储所有边的数组
    int i, j, k = 0;
    for (i = 0; i < g.num_vexs; i++)
    {
        for (j = i + 1; j < g.num_vexs; j++)
        {
            if (g.matrix[i][j] > 0 && g.matrix[i][j] < MAXEDGE)
            {
                edges[k].u = i;
                edges[k].v = j;
                edges[k].w = g.matrix[i][j];
                k++;
            }
        }
    }
    quick_sort(edges, 0, k - 1); // 对边按权值从小到大排序
    int parent[MAXVEX]; // 存储结点的父节点
    for (i = 0; i < g.num_vexs; i++)
        parent[i] = 0;
    for (i = 0; i < k; i++)
    {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        int pu = parent[u], pv = parent[v];
        while (pu)
        {
            u = pu;
            pu = parent[u];
        }
        while (pv)
        {
            v = pv;
            pv = parent[v];
        }
        if (u != v) // 判断是否形成回路
        {
            printf("(%d,%d,%d)\n", edges[i].u, edges[i].v, edges[i].w);
            parent[u] = v; // 合并两个连通分量
        }
    }
}

int main()
{
    Graph g;
    int i, j;
    printf("输入顶点数和边数：");
    scanf("%d%d", &g.num_vexs, &g.num_edges);
    for (i = 0; i < g.num_vexs; i++)
    {
        printf("输入第%d个顶点：", i + 1);
        scanf("%d", &g.vexs[i]);
    }
    for (i = 0; i < g.num_vexs; i++)
    {
        for (j = 0; j < g.num_vexs; j++)
        {
            if (i == j)
                g.matrix[i][j] = 0;
            else
                g.matrix[i][j] = MAXEDGE;
        }
    }
    for (i = 0; i < g.num_edges; i++)
    {
        int u, v, w;
        printf("输入第%d条边的起始点、终止点和权值：", i + 1);
        scanf("%d%d%d", &u, &v, &w);
        g.matrix[u][v] = w;
        g.matrix[v][u] = w;
    }
    printf("最小生成树为：\n");
    kruskal(g);
    return 0;
}

该程序首先读入顶点数和边数，然后读入每个顶点的编号和每条边的起始点、终止点和权值。接着，它生成所有边的数组，并对其按权值从小到大排序。最后，它使用克鲁斯卡尔算法生成最小生成树，并输出每个边的起始点、终止点和权值。