数据结构_最小生成树Prim算法(C语言)
#include<>
#include<>
#define MaxVex 10
#define INF 65535
typedef char VertexType; // 顶点的数据类型
typedef int EdgeType; // 边的数据类型
typedef struct
{
VertexType *vertexs; // 一维数组存放顶点数据
EdgeType **edges; // 二维数组存放边的数据
int numVertexs, numEdges;//顶点数、边数
}AMGraph;
// 初始化领接矩阵
void InitAMGraph(AMGraph *G)
{
// 初始化顶点一维数组
G->vertexs = (VertexType *)malloc(MaxVex*sizeof(VertexType));
// 初始化边的二维数组
int i, j;
G->edges = (EdgeType **)malloc(MaxVex*sizeof(EdgeType *));
for (i = 0; i < MaxVex; i++)
{
G->edges[i] = (EdgeType *)malloc(MaxVex*sizeof(EdgeType));
// 初始化每条边都为INF（无穷大）
for ( j = 0; j < MaxVex; j++)
{
if (i == j)
{
G->edges[i][j] = 0; // 对角线初始位为0
}
else
{
G->edges[i][j] = INF; // 初始化为无穷大
}
}
}
// 初始化顶点和边的数量
G->numVertexs = 0;
G->numEdges = 0;
printf("已初始化邻接矩阵!\n");
}
// 创建领接矩阵
void CreateAMGraph(AMGraph *G)
{
printf("请输入顶点数和边数:");
scanf("%d %d", &G->numVertexs, &G->numEdges);
int i, j, k, weight;
// 输入顶点数据
for (i = 0; i < G->numVertexs; i++)
{
fflush(stdin);
printf("请输入第%d个顶点数据:", i + 1);
scanf("%c", &G->vertexs[i]);
}
// 输入边的权值
for (k = 0; k < G->numEdges; k++)
{
printf("请输入第%d条边的两顶点及其权值:", k + 1);
scanf("%d %d %d", &i, &j, &weight);
G->edges[i - 1][j - 1] = weight;
// 无向图中，边的两个方向权值相同
G->edges[j - 1][i - 1] = weight;
}
printf("已完成邻接矩阵的创建!\n");
}
// 取最小边的相邻顶点下标
int minAdjVex(EdgeType *minEdge, int size)
{
EdgeType min;
int i, j, k = -1;
for (i = 0; i < size; i++)
{
if (minEdge[i] > 0)
{
min = minEdge[i];
for (j = 0; j < size; j++)
{
if (minEdge[j] > 0 && min >= minEdge[j])
{
min = minEdge[j];
k = j;
}
}
break;
}
}
return k;
}
void MiniSpanTree_Prim(AMGraph G, int v)
{
EdgeType *minEdge;
minEdge = (EdgeType *)malloc(G.numVertexs * sizeof(EdgeType));
int i, j, k;
// 初始化辅助数组，用于表示最小生成树的顶点集合
for (i = 0; i < G.numVertexs; i++)
{
// 初始化 顶点[v]到各个顶点[i]的权值
minEdge[i] = G.edges[v][i];
}
// 设置顶点[v]到顶点[v]的权值为0（代表顶点[v]加入最小生成树的顶点集合）
minEdge[v] = 0;
// 依次将最小边相邻的顶点加入集合
for (i = 1; i < G.numVertexs; i++)
{
// 获取最小生成树集合与其他顶点之间最小边的相邻顶点下标
k = minAdjVex(minEdge, G.numVertexs);
printf("{ ");
for (j = 0; j < G.numVertexs; j++)
{
if (minEdge[j] == 0)
{
printf("%c ", G.vertexs[j]);
}
}
printf("}---(%d)---[%c]\n", minEdge[k], G.vertexs[k]);
// 设置集合到顶点[k]的权值为0（代表顶点[k]加入最小生成树顶点集合）
minEdge[k] = 0;
// 更新集合 到 其他各顶点最小边的权值
for ( j = 0; j < G.numVertexs; j++)
{
// 顶点[k]到顶点[j]的边权值 小于 原来集合到顶点[j]的边权值
if (G.edges[k][j] < minEdge[j])
{
minEdge[j] = G.edges[k][j];
}
}
}
}
int main()
{
AMGraph G;
InitAMGraph(&G);
CreateAMGraph(&G);
MiniSpanTree_Prim(G, 0);
system("pause");
return 0;
}