三元组形式的普利姆算法

三元组形式的普利姆算法实现与邻接矩阵和邻接表的实现类似，只是在读取图数据和处理边的权值时需要使用三元组的形式。以下是三元组形式的普利姆算法的基本思路：

1. 从图中任选一个节点作为起始节点，将其标记为已访问。
2. 将起始节点的所有边加入到一个小根堆中，按照边的权值从小到大排序。
3. 从小根堆中取出一条边，如果该边所连接的节点未被访问过，则将该节点标记为已访问，并将该节点的所有边加入到小根堆中。
4. 重复第3步，直到所有节点都被访问过或小根堆为空。

以下是使用三元组形式实现普利姆算法的代码：

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

#define MAX_NODE_NUM 100  // 最大节点数
#define MAX_EDGE_NUM 1000 // 最大边数

// 三元组结构体
typedef struct Triple
{
    int start;   // 起始节点
    int end;     // 终止节点
    int weight;  // 边的权值
} Triple;

// 小根堆结构体
typedef struct MinHeap
{
    Triple heap[MAX_EDGE_NUM]; // 堆数组
    int size;                  // 堆大小
} MinHeap;

// 普利姆算法求最小生成树
void prim(Triple graph[MAX_EDGE_NUM], int nodeNum, int edgeNum)
{
    int visited[MAX_NODE_NUM] = {0}; // 标记节点是否被访问
    int count = 0, sum = 0;          // 已经访问的节点数和最小生成树的权值和
    MinHeap heap = {0};              // 小根堆

    // 从第一个节点开始
    visited[graph[0].start] = 1;
    count++;

    // 将起始节点的所有边加入到小根堆中
    for (int i = 0; i < edgeNum; i++)
    {
        if (graph[i].start == graph[0].start)
        {
            heap.heap[heap.size++] = graph[i];
        }
    }

    // 循环取出小根堆中的边
    while (count < nodeNum && heap.size > 0)
    {
        // 取出堆顶元素
        Triple t = heap.heap[0];
        heap.heap[0] = heap.heap[--heap.size];
        heapify(heap.heap, heap.size, 0); // 重新调整堆

        // 如果该边所连接的节点未被访问过，则将该节点标记为已访问
        if (!visited[t.end])
        {
            visited[t.end] = 1;
            count++;
            sum += t.weight;

            // 将该节点的所有边加入到小根堆中
            for (int i = 0; i < edgeNum; i++)
            {
                if (graph[i].start == t.end)
                {
                    heap.heap[heap.size++] = graph[i];
                    heapify(heap.heap, heap.size, heap.size - 1); // 重新调整堆
                }
            }
        }
    }

    printf("最小生成树的权值和为：%d\n", sum);
}

// 堆调整函数
void heapify(Triple heap[MAX_EDGE_NUM], int size, int i)
{
    int smallest = i;

    // 找到左子节点和右子节点中的最小值
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < size && heap[left].weight < heap[smallest].weight)
        smallest = left;
    if (right < size && heap[right].weight < heap[smallest].weight)
        smallest = right;

    // 如果最小值不是当前节点，则交换节点并继续调整堆
    if (smallest != i)
    {
        Triple temp = heap[i];
        heap[i] = heap[smallest];
        heap[smallest] = temp;
        heapify(heap, size, smallest);
    }
}

int main()
{
    int nodeNum, edgeNum;
    Triple graph[MAX_EDGE_NUM];

    printf("请输入节点数和边数：");
    scanf("%d %d", &nodeNum, &edgeNum);

    printf("请输入每条边的起始节点、终止节点和权值：\n");
    for (int i = 0; i < edgeNum; i++)
    {
        scanf("%d %d %d", &graph[i].start, &graph[i].end, &graph[i].weight);
    }

    prim(graph, nodeNum, edgeNum);

    return 0;
}

注意，在使用小根堆时，需要实现堆调整函数 `heapify`，用于将小根堆调整为符合要求的堆结构。在每次取出堆顶元素后，需要将堆尾元素移动到堆顶，并通过 `heapify` 函数重新调整堆。调整堆的时间复杂度为 $O(\log n)$，因此整个算法的时间复杂度为 $O(m \log n)$，其中 $m$ 为边数，$n$ 为节点数。