最小生成树数据结构课设C语言
时间: 2024-03-09 11:42:36 浏览: 25
最小生成树(Minimum Spanning Tree,简称MST)是图论中的一个重要概念,用于解决连通图的最小权重生成树问题。在C语言中,可以通过使用邻接矩阵或邻接表来表示图,并使用适当的算法来计算最小生成树。
以下是一个简单的C语言实现最小生成树的示例:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100
#define INF 9999
// 邻接矩阵表示图
typedef struct {
int vertices[MAX_VERTICES][MAX_VERTICES];
int numVertices;
} Graph;
// 初始化图
void initGraph(Graph* graph, int numVertices) {
graph->numVertices = numVertices;
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
graph->vertices[i][j] = INF;
}
}
}
// 添加边
void addEdge(Graph* graph, int src, int dest, int weight) {
graph->vertices[src][dest] = weight;
graph->vertices[dest][src] = weight;
}
// 寻找最小生成树
void primMST(Graph* graph) {
int parent[MAX_VERTICES]; // 记录最小生成树的父节点
int key[MAX_VERTICES]; // 记录顶点的权重
bool mstSet[MAX_VERTICES]; // 记录顶点是否已经加入最小生成树
// 初始化key和mstSet
for (int i = 0; i < graph->numVertices; i++) {
key[i] = INF;
mstSet[i] = false;
}
// 第一个顶点作为起始点
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < graph->numVertices - 1; count++) {
int minKey = INF;
int minIndex;
// 选择权重最小的顶点
for (int v = 0; v < graph->numVertices; v++) {
if (mstSet[v] == false && key[v] < minKey) {
minKey = key[v];
minIndex = v;
}
}
mstSet[minIndex] = true;
// 更新相邻顶点的权重和父节点
for (int v = 0; v < graph->numVertices; v++) {
if (graph->vertices[minIndex][v] != INF && mstSet[v] == false && graph->vertices[minIndex][v] < key[v]) {
parent[v] = minIndex;
key[v] = graph->vertices[minIndex][v];
}
}
}
// 打印最小生成树
printf("Edge \tWeight\n");
for (int i = 1; i < graph->numVertices; i++) {
printf("%d - %d \t%d\n", parent[i], i, graph->vertices[i][parent[i]]);
}
}
int main() {
Graph graph;
int numVertices, numEdges;
printf("Enter the number of vertices: ");
scanf("%d", &numVertices);
initGraph(&graph, numVertices);
printf("Enter the number of edges: ");
scanf("%d", &numEdges);
for (int i = 0; i < numEdges; i++) {
int src, dest, weight;
printf("Enter edge %d (source, destination, weight): ", i + 1);
scanf("%d %d %d", &src, &dest, &weight);
addEdge(&graph, src, dest, weight);
}
primMST(&graph);
return 0;
}
```
这个示例使用了Prim算法来计算最小生成树。用户需要输入图的顶点数和边数,以及每条边的起始顶点、目标顶点和权重。程序将输出最小生成树的边及其权重。