c语言【输入形式】 第一行输入城市,城市之间用空格分开,输入q结束。 后面若干行,每行输入两座城市及城市间的公路长度,用空格分开。输入q结束。 输入起点城市名称。 【输出形式】起点城市出发得到的最小生成树,输出格式为(起点城市, 终点城市). 注:城市之间是英文逗号,并且没有空格。 【样例输入】 成都 西安 昆明 贵阳 武汉 株洲 q 成都 西安 842 成都 昆明 1100 成都 贵阳 967 西安 武汉 740 贵阳 武汉 1042 贵阳 株洲 607 武汉 株洲 409 q 成都 【样例输出】 (成都,西安) (西安,武汉) (武汉,株洲) (株洲,贵阳) (成都,昆明)
时间: 2024-02-25 07:58:13 浏览: 20
以下是一个参考的 C 语言实现,需要注意的是该代码实现的是 Prim 算法,而不是 Kruskal 算法,但是实现思路类似,只是一些细节上的差别。
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define MAX_CITY_NUM 100
#define MAX_EDGE_NUM 1000
struct Edge {
int city1;
int city2;
int length;
};
int city_count = 0;
char cities[MAX_CITY_NUM][20];
struct Edge edges[MAX_EDGE_NUM];
int edge_count = 0;
void add_city(const char* city) {
strcpy(cities[city_count++], city);
}
int find_city(const char* city) {
for (int i = 0; i < city_count; i++) {
if (strcmp(cities[i], city) == 0) {
return i;
}
}
return -1;
}
void add_edge(const char* city1, const char* city2, int length) {
int i = find_city(city1);
int j = find_city(city2);
edges[edge_count].city1 = i;
edges[edge_count].city2 = j;
edges[edge_count].length = length;
edge_count++;
}
int min_index(int* dist, int* visited, int n) {
int min = INT_MAX;
int min_index = -1;
for (int i = 0; i < n; i++) {
if (!visited[i] && dist[i] < min) {
min = dist[i];
min_index = i;
}
}
return min_index;
}
void prim(int start) {
int dist[MAX_CITY_NUM];
int visited[MAX_CITY_NUM];
memset(visited, 0, sizeof(visited));
for (int i = 0; i < city_count; i++) {
dist[i] = INT_MAX;
}
dist[start] = 0;
for (int i = 0; i < city_count - 1; i++) {
int u = min_index(dist, visited, city_count);
visited[u] = 1;
for (int j = 0; j < edge_count; j++) {
if (edges[j].city1 == u && !visited[edges[j].city2]
&& edges[j].length < dist[edges[j].city2]) {
dist[edges[j].city2] = edges[j].length;
}
if (edges[j].city2 == u && !visited[edges[j].city1]
&& edges[j].length < dist[edges[j].city1]) {
dist[edges[j].city1] = edges[j].length;
}
}
}
for (int i = 0; i < city_count; i++) {
if (dist[i] != INT_MAX) {
printf("(%s,%s) ", cities[start], cities[i]);
}
}
}
int main() {
char city1[20], city2[20];
int length;
scanf("%s", city1);
while (strcmp(city1, "q") != 0) {
add_city(city1);
scanf("%s", city1);
}
scanf("%s", city1);
while (strcmp(city1, "q") != 0) {
scanf("%s %d", city2, &length);
add_edge(city1, city2, length);
scanf("%s", city1);
}
scanf("%s", city1);
prim(find_city(city1));
return 0;
}
```
其中,`add_city` 和 `find_city` 函数分别用于添加和查找城市,`add_edge` 函数用于添加边,`prim` 函数用于实现 Prim 算法求解最小生成树,最后在 `main` 函数中按照输入输出格式读入数据并调用相应函数即可。