数据结构C语言版 普里姆算法
编译环境：Dev-C++ 4.9.9.2
此算法采用C语言实现
/*
输出效果：
请输入无向网G的顶点数,边数,边是否含其它信息(是:1,否:0):(空格区分) 4 4 0
请输入4个顶点的值(<3个字符):
a
b
c
d
请输入4条边的顶点1 顶点2 权值(以空格作为间隔):
a b 1
a c 2
b d 3
a d 1
最小代价生成树的各条边为:
(a-b)
(a-d)
(a-c)
请按任意键继续. . .
*/
### 数据结构C语言版-普里姆算法
#### 核心知识点概述
本文将详细介绍如何在C语言环境下实现普里姆算法（Prim's Algorithm），该算法用于求解加权无向图中的最小生成树问题。文章包括算法的基本原理、代码实现、运行环境介绍以及具体的示例演示等内容。
#### 普里姆算法基本原理
普里姆算法是一种贪心算法，主要用于构造一个加权无向图的最小生成树。所谓最小生成树是指在一个加权无向图中找到一棵包含所有顶点且权重之和最小的生成树。该算法的核心思想是从图中任选一个顶点开始，每次迭代时选择一个当前未加入生成树的顶点，并且这个顶点与已加入生成树的顶点之间的边权最小，直到所有顶点都被加入为止。
#### 编译环境及工具
本项目使用的开发环境为 **Dev-C++ 4.9.9.2** 版本。Dev-C++ 是一个免费的、面向教育和编程爱好者的集成开发环境，它基于GCC编译器，支持C/C++语言的开发。此外，为了确保程序的可移植性，本文档中的代码遵循C89/C90标准。
#### 代码实现详解
##### 数据结构定义
首先定义了几个必要的宏来简化代码：
```c
#define MAX_VERTEX_NUM 20 // 最大顶点数
#define MAX_NAME 3 // 顶点名称最大长度+1
#define MAX_INFO 20 // 边的信息最大长度+1
#define INFINITY INT_MAX // 无穷大的值
```
定义了一个结构体 `ArcCell` 来表示图中的每一条边，其中 `adj` 表示边的权重，`info` 存储边的相关信息。`AdjMatrix` 结构体则用来存储整个图的数据，它是一个二维数组，每个元素都是 `ArcCell` 类型。
```c
typedef struct
{
VRType adj; // 权重
InfoType *info; // 边的信息
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
```
`MGraph` 结构体用来表示整个图，它包含了顶点数组、邻接矩阵以及图的顶点数和边数等信息。
```c
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM]; // 顶点数组
AdjMatrix arcs; // 邻接矩阵
int vexnum, arcnum; // 图的顶点数和边数
} MGraph;
```
`minside` 结构体用于辅助计算过程中记录每个顶点到生成树中顶点的最短距离。
```c
typedef struct
{
VertexType adjvex; // 相邻顶点
VRType lowcost; // 最小距离
} minside[MAX_VERTEX_NUM];
```
##### 主要函数
- `LocateVex`: 该函数用于在图中查找指定顶点的位置。
- `CreateAN`: 该函数用于创建图的邻接矩阵表示。
- `minimum`: 该函数用于找出未加入生成树的顶点中距离最小的一个。
- `MiniSpanTree_PRIM`: 这是实现普里姆算法的主要函数，用于构建最小生成树。
##### 示例代码
下面是一段关键的示例代码片段，展示了如何利用普里姆算法生成最小生成树：
```c
// 构建最小生成树
void MiniSpanTree_PRIM(MGraph G, VertexType u)
{
int i, j, k;
minside closedge;
k = LocateVex(G, u); // 找到起始顶点的位置
for (j = 0; j < G.vexnum; ++j) // 初始化
{
if (j != k)
{
closedge[j].lowcost = G.arcs[k][j].adj; // 记录初始距离
closedge[j].adjvex = G.vexs[k]; // 记录相邻顶点
}
else
{
closedge[j].lowcost = 0; // 起始顶点距离为0
closedge[j].adjvex = G.vexs[j]; // 相邻顶点为自己
}
}
for (i = 1; i < G.vexnum; ++i) // 求解过程
{
k = minimum(closedge, G); // 找出下一个加入生成树的顶点
printf("(%c-%c)\n", closedge[k].adjvex[0], G.vexs[k][0]); // 输出结果
for (j = 0; j < G.vexnum; ++j) // 更新距离
{
if (closedge[k].lowcost + G.arcs[k][j].adj < closedge[j].lowcost)
{
closedge[j].lowcost = closedge[k].lowcost + G.arcs[k][j].adj;
closedge[j].adjvex = G.vexs[k];
}
}
}
}
```
#### 运行效果
根据提供的代码示例，当运行程序并输入以下测试数据时：
- 顶点数: 4
- 边数: 4
- 边是否含其他信息: 0
- 顶点值: a, b, c, d
- 边及其权值: a b 1, a c 2, b d 3, a d 1
程序将输出以下结果：
```
最小代价生成树的各条边为:
(a-b)
(a-d)
(a-c)
```
这表明，使用普里姆算法找到了包含所有顶点的最小生成树，并输出了该树的边及其权值。
#### 总结
通过以上内容，我们不仅了解了普里姆算法的基本概念，还学习了如何在C语言环境下实现这一算法。此外，还通过一个实际例子展示了算法的具体应用。普里姆算法是解决最小生成树问题的一种有效方法，在网络设计、电路布局等领域有着广泛的应用前景。
