用C++写prim算法
时间: 2023-11-04 20:11:12 浏览: 39
Prim算法是一种求无向加权连通图的最小生成树的贪心算法,可以用C语言来实现。下面是一份示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_VERTICES 1000 // 最大顶点数
typedef struct {
int v1, v2, weight;
} Edge;
typedef struct {
int count;
int parent[MAX_VERTICES];
int key[MAX_VERTICES];
int mst[MAX_VERTICES][MAX_VERTICES];
} Graph;
Graph create_graph(int vertices) {
Graph G;
G.count = vertices;
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
G.mst[i][j] = 0;
}
G.key[i] = INT_MAX;
G.parent[i] = -1;
}
return G;
}
void add_edge(Graph *G, int v1, int v2, int weight) {
G->mst[v1][v2] = weight;
G->mst[v2][v1] = weight;
}
int extract_min(Graph *G, int *visited) {
int min = INT_MAX, min_index = -1;
for (int i = 0; i < G->count; i++) {
if (visited[i] == 0 && G->key[i] < min) {
min = G->key[i];
min_index = i;
}
}
return min_index;
}
void prim(Graph *G) {
int visited[MAX_VERTICES] = {0};
G->key[0] = 0;
for (int i = 0; i < G->count-1; i++) {
int u = extract_min(G, visited);
visited[u] = 1;
for (int v = 0; v < G->count; v++) {
if (G->mst[u][v] != 0 && visited[v] == 0 && G->mst[u][v] < G->key[v]) {
G->parent[v] = u;
G->key[v] = G->mst[u][v];
}
}
}
for (int i = 1; i < G->count; i++) {
add_edge(G, G->parent[i], i, G->mst[G->parent[i]][i]);
}
}
void print_mst(Graph G) {
for (int i = 1; i < G.count; i++) {
printf("(%d, %d) -> %d\n", G.parent[i], i, G.mst[G.parent[i]][i]);
}
}
int main() {
Graph G = create_graph(6);
add_edge(&G, 0, 1, 4);
add_edge(&G, 0, 2, 3);
add_edge(&G, 1, 2, 1);
add_edge(&G, 1, 3, 2);
add_edge(&G, 2, 3, 4);
add_edge(&G, 3, 4, 2);
add_edge(&G, 4, 5, 6);
prim(&G);
print_mst(G);
return 0;
}
```
这份代码实现了Prim算法,使用邻接矩阵来表示图,其中`create_graph`函数用来创建一个空的图,`add_edge`函数用来添加一条边,`extract_min`函数用来从尚未访问的顶点中选取key值最小的顶点,`prim`函数用来求出最小生成树,`print_mst`函数用来输出最小生成树的边。