用c语言编写一个程序,要求使用Prim和Kruskal算法来求解建公路问题。假设有n个村庄,编号从1到n,现在修建一些道 路使任意两个村庄之间可以互相连通。所谓两个村庄A和B是连通的,指当且仅当A和B之间有一-条道路或者存在一个村庄C使得A和C之间有一条道路,并且C和B是连通的。有一-些村庄之间已经存在一些道路,这里的工作是建造一些道路,以使所有村庄都连通,并且所有道路的长度最小。
时间: 2023-07-14 20:14:32 浏览: 482
以下是使用Prim和Kruskal算法来求解建公路问题的C语言程序:
```
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>
#define MAX_VERTICES 100
typedef struct Edge {
int src;
int dest;
int weight;
} Edge;
typedef struct Graph {
int num_vertices;
int num_edges;
Edge edges[MAX_VERTICES * (MAX_VERTICES - 1) / 2];
} Graph;
Graph createGraph(int num_vertices, int num_edges) {
Graph graph;
graph.num_vertices = num_vertices;
graph.num_edges = 0;
return graph;
}
void addEdge(Graph* graph, int src, int dest, int weight) {
Edge edge = {src, dest, weight};
graph->edges[graph->num_edges++] = edge;
}
int findMinVertex(int* distances, bool* visited, int num_vertices) {
int min_vertex = -1;
for (int i = 0; i < num_vertices; i++) {
if (!visited[i] && (min_vertex == -1 || distances[i] < distances[min_vertex])) {
min_vertex = i;
}
}
return min_vertex;
}
void primMST(Graph* graph) {
bool visited[MAX_VERTICES] = {false};
int distances[MAX_VERTICES];
int parents[MAX_VERTICES];
for (int i = 0; i < graph->num_vertices; i++) {
distances[i] = INT_MAX;
}
distances[0] = 0;
parents[0] = -1;
for (int i = 0; i < graph->num_vertices - 1; i++) {
int min_vertex = findMinVertex(distances, visited, graph->num_vertices);
visited[min_vertex] = true;
for (int j = 0; j < graph->num_edges; j++) {
if (graph->edges[j].src == min_vertex || graph->edges[j].dest == min_vertex) {
int other_vertex = graph->edges[j].src == min_vertex ? graph->edges[j].dest : graph->edges[j].src;
if (!visited[other_vertex] && graph->edges[j].weight < distances[other_vertex]) {
distances[other_vertex] = graph->edges[j].weight;
parents[other_vertex] = min_vertex;
}
}
}
}
printf("Using Prim's algorithm:\n");
int total_weight = 0;
for (int i = 1; i < graph->num_vertices; i++) {
printf("Edge %d-%d with weight %d\n", parents[i], i, distances[i]);
total_weight += distances[i];
}
printf("Total weight: %d\n", total_weight);
}
int compareEdges(const void* a, const void* b) {
Edge* edge1 = (Edge*) a;
Edge* edge2 = (Edge*) b;
return edge1->weight - edge2->weight;
}
int findParent(int* parent, int vertex) {
if (parent[vertex] == vertex) {
return vertex;
}
return findParent(parent, parent[vertex]);
}
void kruskalMST(Graph* graph) {
int parent[MAX_VERTICES];
for (int i = 0; i < graph->num_vertices; i++) {
parent[i] = i;
}
qsort(graph->edges, graph->num_edges, sizeof(Edge), compareEdges);
printf("Using Kruskal's algorithm:\n");
int total_weight = 0;
for (int i = 0; i < graph->num_edges; i++) {
int src_parent = findParent(parent, graph->edges[i].src);
int dest_parent = findParent(parent, graph->edges[i].dest);
if (src_parent != dest_parent) {
printf("Edge %d-%d with weight %d\n", graph->edges[i].src, graph->edges[i].dest, graph->edges[i].weight);
parent[src_parent] = dest_parent;
total_weight += graph->edges[i].weight;
}
}
printf("Total weight: %d\n", total_weight);
}
int main() {
int num_vertices, num_edges;
printf("Enter number of vertices and edges: ");
scanf("%d %d", &num_vertices, &num_edges);
Graph graph = createGraph(num_vertices, num_edges);
printf("Enter %d edges with source, destination and weight:\n", num_edges);
for (int i = 0; i < num_edges; i++) {
int src, dest, weight;
scanf("%d %d %d", &src, &dest, &weight);
addEdge(&graph, src - 1, dest - 1, weight);
}
primMST(&graph);
kruskalMST(&graph);
return 0;
}
```
程序首先定义了Edge和Graph结构体,其中Edge包含源节点、目标节点和权重,Graph包含节点数和边数以及边列表。createGraph函数创建一个空图,addEdge函数向图中添加一条边。findMinVertex函数返回未访问过的距离最小的节点,primMST函数使用Prim算法求解最小生成树,并输出结果。compareEdges函数用于qsort函数排序边,findParent函数返回节点的祖先节点,kruskalMST函数使用Kruskal算法求解最小生成树,并输出结果。最后,main函数读取输入,并调用primMST和kruskalMST函数来求解建公路问题。
相关推荐
![exe](https://img-home.csdnimg.cn/images/20210720083343.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)