能够运行。麻烦再给出用kruskal算法编写的代码
时间: 2024-04-08 08:32:55 浏览: 30
以下是使用C语言实现Kruskal算法求解最小生成树的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义边的结构体
typedef struct {
int src, dest, weight;
} Edge;
// 定义图的结构体
typedef struct {
int numNodes, numEdges;
Edge* edges;
} Graph;
// 创建图的函数
Graph* createGraph(int numNodes, int numEdges) {
Graph* graph = (Graph*) malloc(sizeof(Graph));
graph->numNodes = numNodes;
graph->numEdges = numEdges;
graph->edges = (Edge*) malloc(numEdges * sizeof(Edge));
return graph;
}
// 查找父节点的函数
int find(int parent[], int i) {
if (parent[i] == -1)
return i;
return find(parent, parent[i]);
}
// 合并两个集合的函数
void unionSet(int parent[], int x, int y) {
int xset = find(parent, x);
int yset = find(parent, y);
parent[xset] = yset;
}
// 比较边的权值的函数(用于排序)
int compare(const void* a, const void* b) {
Edge* edge1 = (Edge*) a;
Edge* edge2 = (Edge*) b;
return edge1->weight - edge2->weight;
}
// Kruskal算法求解最小生成树
void kruskalMST(Graph* graph) {
int numNodes = graph->numNodes;
Edge result[numNodes]; // 存储最小生成树的边
int e = 0; // 表示result数组中当前添加的边的索引
int i = 0; // 表示按权值排序后的边的索引
qsort(graph->edges, graph->numEdges, sizeof(Edge), compare); // 将边按照权值从小到大排序
int parent[numNodes]; // 用于判断两个节点是否在同一集合中(即是否形成环路)
for (int v = 0; v < numNodes; v++)
parent[v] = -1;
while (e < numNodes - 1 && i < graph->numEdges) {
Edge nextEdge = graph->edges[i++];
int x = find(parent, nextEdge.src);
int y = find(parent, nextEdge.dest);
if (x != y) {
result[e++] = nextEdge;
unionSet(parent, x, y);
}
}
printf("Edges in Minimum Spanning Tree:\n");
for (i = 0; i < e; i++) {
printf("%d - %d\n", result[i].src, result[i].dest);
}
}
int main() {
int numNodes, numEdges;
printf("Enter the number of nodes: ");
scanf("%d", &numNodes);
printf("Enter the number of edges: ");
scanf("%d", &numEdges);
Graph* graph = createGraph(numNodes, numEdges);
printf("Enter the edges (source destination weight):\n");
for (int i = 0; i < numEdges; i++) {
int src, dest, weight;
scanf("%d %d %d", &src, &dest, &weight);
graph->edges[i].src = src;
graph->edges[i].dest = dest;
graph->edges[i].weight = weight;
}
kruskalMST(graph);
return 0;
}
```
请注意,这只是一个基本的实现示例,可能需要根据具体需求进行调整和优化。
阅读全文