小根堆排序怎么实现最小生成树C语言
时间: 2023-07-11 20:30:40 浏览: 71
以下是使用小根堆排序实现 Prim 算法生成最小生成树的 C 语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// 定义最大节点数
#define MAX_NODES 1000
// 定义图的节点结构体
struct Node {
int weight; // 权值
int dest; // 目标节点
};
// 定义小根堆结构体
struct MinHeap {
int size; // 当前堆的大小
int capacity; // 堆的容量
int *pos; // 存储每个节点在堆中的位置
struct Node **array; // 存储最小堆的数组
};
// 创建一个新的节点
struct Node* newNode(int w, int d) {
struct Node* node = (struct Node*) malloc(sizeof(struct Node));
node->weight = w;
node->dest = d;
return node;
}
// 创建一个最小堆
struct MinHeap* createMinHeap(int capacity) {
struct MinHeap* heap = (struct MinHeap*) malloc(sizeof(struct MinHeap));
heap->pos = (int*) malloc(sizeof(int) * capacity);
heap->size = 0;
heap->capacity = capacity;
heap->array = (struct Node**) malloc(sizeof(struct Node*) * capacity);
return heap;
}
// 交换两个节点
void swapNode(struct Node** a, struct Node** b) {
struct Node* tmp = *a;
*a = *b;
*b = tmp;
}
// 维护堆的性质
void minHeapify(struct MinHeap* heap, int idx) {
int smallest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
// 找到左右子节点中权值最小的节点
if (left < heap->size && heap->array[left]->weight < heap->array[smallest]->weight) {
smallest = left;
}
if (right < heap->size && heap->array[right]->weight < heap->array[smallest]->weight) {
smallest = right;
}
// 如果最小的节点不是当前节点,则交换节点并继续递归维护堆性质
if (smallest != idx) {
struct Node* smallestNode = heap->array[smallest];
struct Node* idxNode = heap->array[idx];
heap->pos[smallestNode->dest] = idx;
heap->pos[idxNode->dest] = smallest;
swapNode(&heap->array[smallest], &heap->array[idx]);
minHeapify(heap, smallest);
}
}
// 判断堆是否为空
int isEmpty(struct MinHeap* heap) {
return heap->size == 0;
}
// 从堆中取出最小节点
struct Node* extractMin(struct MinHeap* heap) {
if (isEmpty(heap)) {
return NULL;
}
struct Node* root = heap->array[0];
struct Node* lastNode = heap->array[heap->size - 1];
heap->array[0] = lastNode;
heap->pos[root->dest] = heap->size - 1;
heap->pos[lastNode->dest] = 0;
--heap->size;
minHeapify(heap, 0);
return root;
}
// 将节点的权值更新为新的值
void decreaseKey(struct MinHeap* heap, int dest, int weight) {
int i = heap->pos[dest];
heap->array[i]->weight = weight;
while (i && heap->array[i]->weight < heap->array[(i - 1) / 2]->weight) {
heap->pos[heap->array[i]->dest] = (i - 1) / 2;
heap->pos[heap->array[(i - 1) / 2]->dest] = i;
swapNode(&heap->array[i], &heap->array[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
// 判断节点是否在堆中
int isInHeap(struct MinHeap* heap, int dest) {
return heap->pos[dest] < heap->size;
}
// Prim 算法生成最小生成树
void primMST(int graph[MAX_NODES][MAX_NODES], int numNodes) {
int parent[numNodes];
int key[numNodes];
struct MinHeap* heap = createMinHeap(numNodes);
// 初始化所有节点的权值为无穷大
for (int i = 0; i < numNodes; ++i) {
parent[i] = -1;
key[i] = INT_MAX;
heap->array[i] = newNode(key[i], i);
heap->pos[i] = i;
}
// 将第一个节点的权值设为0,并将其插入堆中
key[0] = 0;
heap->array[0] = newNode(key[0], 0);
heap->pos[0] = 0;
// 堆中节点数为所有节点数
heap->size = numNodes;
// 开始生成最小生成树
while (!isEmpty(heap)) {
struct Node* minNode = extractMin(heap);
int u = minNode->dest;
// 遍历所有相邻节点
for (int v = 0; v < numNodes; ++v) {
// 如果当前节点与相邻节点之间存在一条边,则判断是否需要更新相邻节点的权值
if (graph[u][v] && isInHeap(heap, v) && graph[u][v] < key[v]) {
key[v] = graph[u][v];
parent[v] = u;
decreaseKey(heap, v, key[v]);
}
}
}
// 输出最小生成树的边
for (int i = 1; i < numNodes; ++i) {
printf("%d - %d\t%d\n", parent[i], i, graph[i][parent[i]]);
}
}
int main() {
int graph[MAX_NODES][MAX_NODES];
int numNodes, numEdges;
// 读入节点数和边数
scanf("%d%d", &numNodes, &numEdges);
// 初始化图的邻接矩阵
for (int i = 0; i < numNodes; ++i) {
for (int j = 0; j < numNodes; ++j) {
graph[i][j] = 0;
}
}
// 读入每条边的信息,将其添加到邻接矩阵中
for (int i = 0; i < numEdges; ++i) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
graph[u][v] = graph[v][u] = w;
}
// 生成最小生成树
primMST(graph, numNodes);
return 0;
}
```
其中,graph 是一个邻接矩阵,存储了图中每个节点之间的边的权值信息。numNodes 是图中的节点数,numEdges 是图中的边数。函数 primMST 实现了 Prim 算法生成最小生成树的过程。在主函数中,首先读入了节点数和边数,然后将每条边的信息添加到邻接矩阵中,最后调用 primMST 函数生成最小生成树。