轻松掌握最小生成树算法:C语言实现与实战解析

引言
最小生成树算法是图论中的一个重要算法,它用于在加权无向图中找到连接所有节点的边的权重之和最小的生成树。最小生成树在许多实际应用中都有广泛的应用,如网络设计、电路设计等。本文将详细介绍最小生成树算法的原理,并使用C语言实现Kruskal算法和Prim算法,同时提供实战解析。
最小生成树算法原理
1. 最小生成树的定义
最小生成树是指在一个图中,连接所有节点的边的权重之和最小的生成树。
2. Kruskal算法原理
Kruskal算法的基本思想是将所有边按照权重从小到大排序,然后依次将边加入生成树中,如果加入某条边会形成环,则不加入该边,直到生成树中包含所有节点为止。
3. Prim算法原理
Prim算法的基本思想是从图中的某个顶点开始,逐步添加边和顶点,直到生成树中包含所有节点。每次添加的边都是与已生成的生成树相连的顶点中权重最小的边。
Kruskal算法C语言实现
1. 数据结构定义
#include
#include

#define MAXEDGENUM 1000
#define MAXVERTEXNUM 100

typedef struct {
int start;
int end;
int weight;
} Edge;

typedef struct {
int parent;
int rank;
} Node;
2. 辅助函数
int find(Node parent[], int x) {
if (parent[x] != x) {
parent[x] = find(parent, parent[x]);
}
return parent[x];
}

void unionset(Node parent[], int rank[], int x, int y) {
int px = find(parent, x);
int py = find(parent, y);
if (px != py) {
if (rank[px] < rank[py]) { parent[px] = py; } else if (rank[px] > rank[py]) {
parent[py] = px;
} else {
parent[px] = py;
rank[py]++;
}
}
}
3. Kruskal算法实现
void kruskal(Edge edges[], int numEdges, int numVertices) {
// 初始化并查集
Node parent[MAXVERTEXNUM];
int rank[MAXVERTEXNUM];
for (int i = 0; i < numVertices; i++) { parent[i] = i; rank[i] = 0; } // 按权重排序 qsort(edges, numEdges, sizeof(Edge), cmp); // 构建最小生成树 int numEdgesInMST = 0; for (int i = 0; i < numEdges; i++) { int u = edges[i].start; int v = edges[i].end; int pu = find(parent, u); int pv = find(parent, v); if (pu != pv) { unionset(parent, rank, u, v); printf("Edge %d: %d - %d\n", ++numEdgesInMST, u, v); } } } Prim算法C语言实现 1. 数据结构定义 #include

typedef struct {
int start;
int end;
int weight;
} Edge;

typedef struct {
int vertex;
int weight;
} MinHeapNode;

typedef struct {
MinHeapNode *array;
int size;
int capacity;
} MinHeap;
2. 辅助函数
void swap(MinHeapNode *a, MinHeapNode *b) {
MinHeapNode t = *a;
*a = *b;
*b = t;
}

void minHeapify(MinHeap *minHeap, int idx) {
int smallest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;

if (left < minHeap->size && minHeap->array[left].weight < minHeap->array[smallest].weight) {
smallest = left;
}

if (right < minHeap->size && minHeap->array[right].weight < minHeap->array[smallest].weight) {
smallest = right;
}

if (smallest != idx) {
swap(&minHeap->array[smallest], &minHeap->array[idx]);
minHeapify(minHeap, smallest);
}
}

int isEmpty(MinHeap *minHeap) {
return minHeap->size == 0;
}

MinHeapNode extractMin(MinHeap *minHeap) {
MinHeapNode root = minHeap->array[0];
minHeap->array[0] = minHeap->array[minHeap->size – 1];
–minHeap->size;
minHeapify(minHeap, 0);
return root;
}

void decreaseKey(MinHeap *minHeap, int v, int key) {
int i = v;
while (i && minHeap->array[(i – 1) / 2].weight > key) {
minHeap->array[i] = minHeap->array[(i – 1) / 2];
i = (i – 1) / 2;
}
minHeap->array[i].weight = key;
}
3. Prim算法实现
void prim(Edge edges[], int numEdges, int numVertices) {
int parent[MAXVERTEXNUM];
int key[MAXVERTEXNUM];
int visited[MAXVERTEXNUM];

// 初始化
for (int i = 0; i < numVertices; i++) { parent[i] = -1; key[i] = INT_MAX; visited[i] = 0; } // 选择第一个顶点 key[0] = 0; MinHeap minHeap; minHeap.size = numVertices; minHeap.capacity = numVertices; minHeap.array = (MinHeapNode *)malloc(numVertices * sizeof(MinHeapNode)); for (int i = 0; i < numVertices; i++) { minHeap.array[i].vertex = i; minHeap.array[i].weight = key[i]; } // 构建最小生成树 while (!isEmpty(&minHeap)) { MinHeapNode minHeapNode = extractMin(&minHeap); int u = minHeapNode.vertex; visited[u] = 1; for (int i = 0; i < numEdges; i++) { int v = edges[i].end; int weight = edges[i].weight; if (visited[v] == 0 && weight < key[v]) { key[v] = weight; parent[v] = u; decreaseKey(&minHeap, v, key[v]); } } } // 打印最小生成树 for (int i = 1; i < numVertices; i++) { printf("Edge %d: %d - %d\n", i, parent[i], i); } } 实战解析 1. Kruskal算法实战 假设有一个图,其顶点为0到5,边的权重如下: (0, 1): 10 (0, 2): 6 (0, 3): 5 (1, 3): 15 (1, 4): 10 (2, 4): 8 (3, 4): 9 (3, 5): 20 (4, 5): 7 使用Kruskal算法得到的最小生成树为: Edge 1: 0 - 1 Edge 2: 0 - 3 Edge 3: 1 - 4 Edge 4: 2 - 4 Edge 5: 3 - 5 2. Prim算法实战 假设有一个图,其顶点为0到5,边的权重如下: (0, 1): 10 (0, 2): 6 (0, 3): 5 (1, 3): 15 (1, 4): 10 (2, 4): 8 (3, 4): 9 (3, 5): 20 (4, 5): 7 使用Prim算法得到的最小生成树为: Edge 1: 0 - 1 Edge 2: 0 - 3 Edge 3: 1 - 4 Edge 4: 2 - 4 Edge 5: 3 - 5 总结 本文详细介绍了最小生成树算法的原理,并使用C语言实现了Kruskal算法和Prim算法。通过实战解析,展示了如何使用这些算法解决实际问题。希望本文能帮助您轻松掌握最小生成树算法。