什么是Prim算法？详述Prim算法的原理，用C语言实现Prim算法。内附完整代码。

大家好，我是贤弟！

一、什么是Prim算法？

Prim算法是一种用于在加权连通图中求解最小生成树的贪心算法。

具体来说，Prim算法从某个点开始构建最小生成树，然后不断向其它尚未加入最小生成树的节点添加边，直到整个图都被覆盖为止。

二、Prim算法的原理

Prim算法的具体实现过程如下：

1、首先任选一个起始节点，将该节点加入最小生成树中。

2、依次找出与最小生成树中已有节点相邻的、权值最小的边（即所谓的“横切边”），将对应节点加入最小生成树中。

3、重复第2步，直到所有的节点都被加入最小生成树中。

这个过程可以用一个visited数组来记录哪些节点已经被加入了最小生成树，用一个dist数组来记录每个节点与最小生成树中已有节点的最短距离，用一个pre数组来记录与当前节点最短距离的节点是哪个。

在实际操作中，Prim算法可以通过维护一个优先队列来加速查找最小边的过程。

具体而言，每次需要找到与最小生成树中已有节点相邻的、权值最小的边时，只需要从优先队列中弹出队头元素即可。

总的来说，Prim算法是一种较为简单高效的求解最小生成树的算法，时间复杂度为O(ElogV)，其中E表示边的个数，V表示节点的个数。

三、用C语言写一段Prim算法

#include #include

#define INFINITY 65535 // 定义正无穷

typedef struct { char vex; // 点名字 int adjvex; // 邻接矩阵中的位置 int weight; // 权值} Edge;

typedef struct { char vexs[100]; // 存放点信息 int arcs[100][100]; // 邻接矩阵 int numVertexes, numEdges; // 图中当前点数和边数} Graph;

// 初始化void CreateGraph(Graph *g) { printf("输入点数和边数\n"); scanf("%d %d", &(g->numVertexes), &(g->numEdges));

printf("输入点信息\n"); for (int i = 0; i < g->numVertexes; i++) { scanf(" %c", &(g->vexs[i])); } // 将邻接矩阵初始化为正无穷 for (int i = 0; i < g->numVertexes; i++) { for (int j = 0; j < g->numVertexes; j++) { if (i == j) { g->arcs[i][j] = 0; } else { g->arcs[i][j] = INFINITY; } } }

printf("输入边信息\n"); for (int k = 0; k < g->numEdges; k++) { char head, tail; int w; int i, j;

scanf(" %c %c %d", &head, &tail, &w);

// 找到对应点的位置 for (int m = 0; m < g->numVertexes; m++) { if (g->vexs[m] == head) { i = m; } if (g->vexs[m] == tail) { j = m; } }

// 添加边信息 g->arcs[i][j] = w; g->arcs[j][i] = w; }}

void Prim(Graph *g) { Edge edges[g->numEdges]; // 存储生成树中的边 int visited[g->numVertexes]; // 记录每个节点是否被访问 int v = 0; // 从0号节点开始

// 初始化visited数组 for (int i = 0; i < g->numVertexes; i++) { visited[i] = 0; }

visited[v] = 1;

for (int k = 0; k < g->numVertexes - 1; k++) { // 一共要找numVertexes-1条边 int i, j; int min = INFINITY;

// 找到当前还没被访问的节点中，与已经访问过的节点距离最小的那一个 for (int m = 0; m < g->numVertexes; m++) { if (visited[m] == 1) { for (int n = 0; n < g->numVertexes; n++) { if (visited[n] == 0 && g->arcs[m][n] < min) { i = m; j = n; min = g->arcs[m][n]; } } } }

// 标记已经访问过的节点，并记录生成树中的边 visited[j] = 1; edges[k].vex = g->vexs[i]; edges[k].adjvex = j; edges[k].weight = g->arcs[i][j]; }

// 输出结果 printf("生成树中的边：\n"); for (int k = 0; k < g->numVertexes - 1; k++) { printf("(%c, %c) %d\n", edges[k].vex, g->vexs[edges[k].adjvex], edges[k].weight); }}

int main() { Graph g; CreateGraph(&g); Prim(&g);

return 0;}