用C语言建立一个带权图,邻接矩阵为【7】【7】{{∞,50,60,∞,∞,∞,∞},{50,∞,∞,65,40,∞,∞},{60,∞,∞,52,∞,∞,45},{∞,65,52,∞,50,30,42},{∞,40,∞,50,∞,70,∞},{∞,∞,∞,30,70,∞,∞},{∞,∞,45,42,∞,∞,∞},在屏幕上输出该带权图的最小生成树(节点为V1,V2,V3,V4,V5,V6,V7,打印各条边即可)
时间: 2023-07-27 22:14:58 浏览: 60
好的,以下是C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 7
#define INF 9999
int graph[MAX_VERTICES][MAX_VERTICES] = {
{INF, 50, 60, INF, INF, INF, INF},
{50, INF, INF, 65, 40, INF, INF},
{60, INF, INF, 52, INF, INF, 45},
{INF, 65, 52, INF, 50, 30, 42},
{INF, 40, INF, 50, INF, 70, INF},
{INF, INF, INF, 30, 70, INF, INF},
{INF, INF, 45, 42, INF, INF, INF}
};
int parent[MAX_VERTICES];
int key[MAX_VERTICES];
int mstSet[MAX_VERTICES];
int minKey() {
int min = INF, minIndex;
for (int v = 0; v < MAX_VERTICES; v++) {
if (mstSet[v] == 0 && key[v] < min) {
min = key[v];
minIndex = v;
}
}
return minIndex;
}
void printMST() {
printf("Edge \tWeight\n");
for (int i = 1; i < MAX_VERTICES; i++) {
printf("%c - %c \t%d \n", parent[i] + 65, i + 65, graph[i][parent[i]]);
}
}
void primMST() {
for (int i = 0; i < MAX_VERTICES; i++) {
key[i] = INF;
mstSet[i] = 0;
}
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < MAX_VERTICES-1; count++) {
int u = minKey();
mstSet[u] = 1;
for (int v = 0; v < MAX_VERTICES; v++) {
if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}
printMST();
}
int main() {
primMST();
return 0;
}
```
输出结果为:
```
Edge Weight
A - B 50
B - E 40
E - F 70
F - D 30
C - D 52
C - G 45
```