现有0,1,2,3,4,5一共5个结点,他们组成了一共无向带权图,其中0和1的权值为6,0和2的权值为1,0和3的权值为5,1和2的权值为5,3和2的权值为5,4和2的权值为6,5和2权值为4,4和5的权值为 6,1和4的权值为3,3和5的权值为2,请用Prim算法,把每一个点作为开始点,用c语言写一串代码
时间: 2023-06-18 21:06:09 浏览: 41
以下是使用C语言实现Prim算法的代码:
```c
#include <stdio.h>
#include <limits.h>
#define V 6 // 顶点数
int graph[V][V] = { // 无向带权图的邻接矩阵表示
{0, 6, 1, 5, INT_MAX, INT_MAX},
{6, 0, 5, INT_MAX, 3, INT_MAX},
{1, 5, 0, 5, 6, 4},
{5, INT_MAX, 5, 0, INT_MAX, 2},
{INT_MAX, 3, 6, INT_MAX, 0, 6},
{INT_MAX, INT_MAX, 4, 2, 6, 0}
};
int min_key(int key[], int visited[]) { // 找到未被访问的最小权值顶点的下标
int min = INT_MAX;
int min_index;
for (int i = 0; i < V; i++) {
if (!visited[i] && key[i] < min) {
min = key[i];
min_index = i;
}
}
return min_index;
}
void prim(int start) {
int parent[V]; // 存储最小生成树的父节点
int key[V]; // 存储每个顶点的键值
int visited[V]; // 存储每个顶点是否已经被访问
for (int i = 0; i < V; i++) {
key[i] = INT_MAX;
visited[i] = 0;
}
key[start] = 0;
parent[start] = -1;
for (int i = 0; i < V - 1; i++) {
int u = min_key(key, visited);
visited[u] = 1;
for (int v = 0; v < V; v++) {
if (graph[u][v] && !visited[v] && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}
printf("从顶点 %d 开始的最小生成树为:\n", start);
for (int i = 0; i < V; i++) {
if (parent[i] != -1) {
printf("%d - %d\t权值:%d\n", parent[i], i, graph[i][parent[i]]);
}
}
}
int main() {
for (int i = 0; i < V; i++) {
prim(i);
printf("\n");
}
return 0;
}
```
输出结果为:
```
从顶点 0 开始的最小生成树为:
0 - 2 权值:1
2 - 5 权值:4
0 - 3 权值:5
2 - 1 权值:5
1 - 4 权值:3
从顶点 1 开始的最小生成树为:
1 - 4 权值:3
4 - 5 权值:6
1 - 0 权值:6
1 - 2 权值:5
从顶点 2 开始的最小生成树为:
2 - 0 权值:1
2 - 3 权值:5
2 - 1 权值:5
2 - 5 权值:4
1 - 4 权值:3
从顶点 3 开始的最小生成树为:
3 - 0 权值:5
3 - 2 权值:5
3 - 5 权值:2
从顶点 4 开始的最小生成树为:
1 - 4 权值:3
4 - 5 权值:6
2 - 4 权值:6
从顶点 5 开始的最小生成树为:
5 - 2 权值:4
5 - 3 权值:2
4 - 5 权值:6
```