数据结构与算法基础-学习-25-图之MST（最小代价生成树）之Prim（普利姆）算法
目录
一、生成树概念
1、所有顶点均由边连接在一起，但不存在回路的图。
2、一个图可以有许多棵不同的生成树。
二、生成树特点
1、生成树的顶点个数与图的顶点个数相同。
2、生成树是图的极小连通子图，去掉一条边则非连通。
3、一个有n个顶点的连通图的生成树有n-1条边。
4、在生成树中再加一条边必然形成回路。
5、生成树中任意两个顶点间的路径是唯一的。
三、最小代价生成树（MST）
给定一个无向网，在该网的所有生成树中，使得各边权值之和最小的那颗生成树称为该网的最小生成树，也叫最小代价生成树。
四、MST实际中的应用
城市中需要铺设线路，怎么样铺设，使得成本低且覆盖所有城市。
五、Prim（普利姆）
1、宏定义
#define PARENT_INIT_VALUE -1
#define LOWEST_WEIGHT_VALUE 0
#define LOWEST_EDGE_VERTEX_INIT_INDEX -12、结构体定义
//最小生成树
typedef struct MinimumSpanningTree
{
VertexIndexType StartIndex;//起始顶点
VertexIndexType EndIndex; //结束顶点
WeightType Weight; //起始顶点到结束顶点边上的权值
}MinimumSpanningTree;
typedef struct MstType
{
MinimumSpanningTree* MstArray;
WeightType ArrayLen;
WeightType ArrayMaxLen;
}MstType;
//Prim
//普利姆算法适用于稠密图，所以我们这边用邻接矩阵实现。
typedef struct ShortestEdgeType
{
VertexIndexType VertexIndex;
WeightType LowestWeight;
}ShortestEdgeType;
typedef struct ShortestEdgeArray
{
ShortestEdgeType* Array;
VertexIndexType ArrayLen;
VertexIndexType ArrayMaxLen;
}ShortestEdgeArray;3、函数定义
（1）InitShortestEdgeArray
VertexIndexType InitShortestEdgeArray(ShortestEdgeArray** SEA, AMGraph* AMG, VertexIndexType StartVertexIndex)
{
JudgeAllNullPointer(SEA);
JudgeAllNullPointer(AMG);
*SEA = (ShortestEdgeArray*)MyMalloc(sizeof(ShortestEdgeArray));
(*SEA)->Array = (ShortestEdgeType*)MyMalloc(sizeof(ShortestEdgeType) * (AMG->CurVertexNum));
(*SEA)->ArrayLen = 1;
(*SEA)->ArrayMaxLen = AMG->CurVertexNum;
VertexIndexType LowestEdgeVertexIndex = StartVertexIndex;
VertexIndexType i;
for(i = 0; i < AMG->CurVertexNum; i++)
{
(*SEA)->Array[i].VertexIndex = StartVertexIndex;
(*SEA)->Array[i].LowestWeight = AMG->ArcArray[StartVertexIndex][i];
if(AMG->ArcArray[StartVertexIndex][LowestEdgeVertexIndex] > AMG->ArcArray[StartVertexIndex][i])
{
LowestEdgeVertexIndex = i;
}
}
(*SEA)->Array[StartVertexIndex].LowestWeight = LOWEST_WEIGHT_VALUE;
PrintfShortestEdgeArray(*SEA);
Log("Init ShortestEdgeArray OK\n",Debug);
return LowestEdgeVertexIndex;
}初始化时需要放入起始结点的索引，返回最小边结束顶点的索引号。
| 参数名 | 描述 |
| SEA | 需要初始化的最短边数组。 |
| AMG | 邻接矩阵图。 |
| StartVertexIndex | 起始顶点索引号。 |
（2）UpdateShortestEdgeArray
VertexIndexType UpdateShortestEdgeArray(ShortestEdgeArray* SEA, AMGraph* AMG, VertexIndexType UpdateVertexIndex)
{
JudgeAllNullPointer(SEA);
JudgeAllNullPointer(AMG);
VertexIndexType LowestEdgeVertexIndex = LOWEST_EDGE_VERTEX_INIT_INDEX;
VertexIndexType i;
for(i = 0; i < SEA->ArrayMaxLen; i++)
{
if(SEA->Array[i].LowestWeight != LOWEST_WEIGHT_VALUE && i != UpdateVertexIndex)//权值不为0，表示没包含的点，可以操作，进入此判断。
{
if(SEA->Array[i].LowestWeight > AMG->ArcArray[UpdateVertexIndex][i])//最小边数组的权值小于邻接矩阵中的权值，这时需要更新，进入此判断。
{
SEA->Array[i].VertexIndex = UpdateVertexIndex;
SEA->Array[i].LowestWeight = AMG->ArcArray[UpdateVertexIndex][i];
}
LowestEdgeVertexIndex = i;
break;
}
}
for(i = LowestEdgeVertexIndex + 1; i < SEA->ArrayMaxLen; i++)
{
if(SEA->Array[i].LowestWeight != LOWEST_WEIGHT_VALUE && i != UpdateVertexIndex)//权值不为0，表示没包含的点，可以操作，进入此判断。
{
if(SEA->Array[i].LowestWeight > AMG->ArcArray[UpdateVertexIndex][i])//最小边数组的权值小于邻接矩阵中的权值，这时需要更新，进入此判断。
{
SEA->Array[i].VertexIndex = UpdateVertexIndex;
SEA->Array[i].LowestWeight = AMG->ArcArray[UpdateVertexIndex][i];
}
if(SEA->Array[i].LowestWeight < SEA->Array[LowestEdgeVertexIndex].LowestWeight)//找出最小权值的顶点索引号。
{
LowestEdgeVertexIndex = i;
}
}
}
SEA->Array[UpdateVertexIndex].LowestWeight = LOWEST_WEIGHT_VALUE;
SEA->ArrayLen++;
PrintfShortestEdgeArray(SEA);
return LowestEdgeVertexIndex;
}根据邻接矩阵AMG和需要更新的顶点索引UpdateVertexIndex，更新SEA最小边数组。
返回最小边结束顶点的索引号。
| 参数名 | 描述 |
| SEA | 最短边数组。 |
| AMG | 邻接矩阵图。 |
| UpdateVertexIndex | 需要更新的顶点索引号。 |
（3）DestroyShortestEdgeArray
Status DestroyShortestEdgeArray(ShortestEdgeArray** SEA)
{
JudgeAllNullPointer(SEA);
JudgeAllNullPointer(*SEA);
free((*SEA)->Array);
(*SEA)->Array = NULL;
(*SEA)->ArrayLen = 0;
(*SEA)->ArrayMaxLen = 0;
free(*SEA);
*SEA = NULL;
Log("Destroy ShortestEdgeArray OK\n",Debug);
return SuccessFlag;
}销毁SEA最短边数组。
| 参数名 | 描述 |
| SEA | 需要销毁的最短边数组。 |
（4）PrimMST
Status PrimMST(AMGraph* AMG, MstType* MST, VertexIndexType StartVertexIndex)
{
JudgeAllNullPointer(AMG);
JudgeAllNullPointer(MST);
ShortestEdgeArray* SEA = NULL;
VertexIndexType LowestEdgeVertexIndex = InitShortestEdgeArray(&SEA, AMG, StartVertexIndex);
PushMST(MST, SEA->Array[LowestEdgeVertexIndex].VertexIndex, LowestEdgeVertexIndex, SEA->Array[LowestEdgeVertexIndex].LowestWeight);
printf("LowestEdgeVertexIndex : %d\n",LowestEdgeVertexIndex);
while(MST->ArrayMaxLen > MST->ArrayLen)
{
LowestEdgeVertexIndex = UpdateShortestEdgeArray(SEA, AMG, LowestEdgeVertexIndex);
printf("LowestEdgeVertexIndex : %d\n",LowestEdgeVertexIndex);
PushMST(MST, SEA->Array[LowestEdgeVertexIndex].VertexIndex, LowestEdgeVertexIndex, SEA->Array[LowestEdgeVertexIndex].LowestWeight);
}
DestroyShortestEdgeArray(&SEA);
Log("Prim Create MST OK\n",Info);
return SuccessFlag;
}初始化时需要放入起始结点的索引，返回最小边结束顶点的索引号。
| 参数名 | 描述 |
| SEA | 需要初始化的最短边数组。 |
| MST | 最小代价生产树。 |
| StartVertexIndex | 起始顶点索引号。 |
（5）InitMST
Status InitMST(MstType** MST, VertexIndexType VertexNum)
{
JudgeAllNullPointer(MST);
*MST = (MstType*)MyMalloc(sizeof(MstType));
(*MST)->MstArray = (MinimumSpanningTree*)MyMalloc(sizeof(MinimumSpanningTree) * (VertexNum - 1));
(*MST)->ArrayLen = 0;
(*MST)->ArrayMaxLen = VertexNum - 1;
return SuccessFlag;
}初始化MST。
| 参数名 | 描述 |
| MST | 最小代价生产树。 |
| VertexNum | 图的顶点总个数。 |
（6）DestroyMST
Status DestroyMST(MstType** MST)
{
JudgeAllNullPointer(MST);
JudgeAllNullPointer(*MST);
free((*MST)->MstArray);
(*MST)->MstArray = NULL;
(*MST)->ArrayLen = 0;
(*MST)->ArrayMaxLen = 0;
free(*MST);
*MST = NULL;
return SuccessFlag;
}销毁MST。
| 参数名 | 描述 |
| MST | 最小代价生产树。 |
（7）PushMST
Status PushMST(MstType* MST, VertexIndexType StartIndex, VertexIndexType EndIndex, WeightType Weight)
{
JudgeAllNullPointer(MST);
if(MST->ArrayMaxLen == MST->ArrayLen)
{
Log("MST Array Is Full, Can't Push Data!",Error);
exit(ExceptionExitFlag);
}
MST->MstArray[MST->ArrayLen].StartIndex = StartIndex;
MST->MstArray[MST->ArrayLen].EndIndex = EndIndex;
MST->MstArray[MST->ArrayLen].Weight = Weight;
MST->ArrayLen++;
return SuccessFlag;
}压数据到MST中。
| 参数名 | 描述 |
| MST | 最小代价生产树。 |
| StartIndex | 边的顶点起始索引号。 |
| EndIndex | 边的顶点结束索引号。 |
| Weight | 边的权值。 |
4、实现思路
我们还是以之前的图为例，其实是偷个小懒。
由于Prim算法适用于稠密图，所以结合邻接矩阵图实现这个算法。对应邻接矩阵图如下：
[2023-6]--[ Debug ]--Printf AMGraph :
VertexArray : [A ,B ,C ,D ,E ]
ArcArray :
[32767 ,20 ,30 ,10 ,32767 ]
[20 ,32767 ,32767 ,32767 ,50 ]
[30 ,32767 ,32767 ,40 ,32767 ]
[10 ,32767 ,40 ,32767 ,60 ]
[32767 ,50 ,32767 ,60 ,32767 ]
CurVertexNum : 5
CurArcNum : 12我们还需要维护一个最短边数组，里面记录了各个点到各个点的最小权值。例如我们从A点出发，也就是索引号为0的点出发，初始化最短边数组。
[2023-6]--[ Debug ]--Printf ShortestEdgeArray
{(0,0),(0,20),(0,30),(0,10),(0,32767)}
ArrayLen : 1
ArrayMaxLen : 5（1）(0,0)第一个0表示起始节点的索引号，第二个0表示权值，如果为0则表示顶点已被访问。(0,0)在最短边数组的0号位，这个0为结束节点索引号，意思表示A点到A点，A点被访问。
（2）(0,20)第一个0表示起始节点的索引号，第二个20表示权值。(0,20)在最短边数组的1号位，这个1为结束节点索引号，意思表示A点到B点，权值为20。
（3）(0,30)第一个0表示起始节点的索引号，第二个30表示权值。(0,30)在最短边数组的2号位，这个2为结束节点索引号，意思表示A点到C点，权值为30。
（4）(0,10)第一个0表示起始节点的索引号，第二个10表示权值。(0,10)在最短边数组的3号位，这个3为结束节点索引号，意思表示A点到D点，权值为10。
（5）(0,32767)第一个0表示起始节点的索引号，第二个32767表示无穷大。(0,32767)在最短边数组的4号位，这个4为结束节点索引号，意思表示A点不能到达E点。
LowestEdgeVertexIndex : 3后四个权值进行比较发现(0,10)的权值最小，A节点已被访问不需要比较，它在最短边数组的3号位，表示D节点被使用。
我们进行更新最短边数组，这里和邻接矩阵的3号位的权值进行比较。
邻接矩阵3号位：
[10 ,32767 ,40 ,32767 ,60 ]（1）0号位的A节点已使用，不用对比。
（2）1号位的B节点，A->B权值为20，比3号位的D节点D->B权值为32767小，还是最短的，不更新。
（3）2号位的C节点，A->C权值为30，比3号位的D节点D->C权值为40小，还是最短的，不更新。
（4）3号位的D节点已使用，不用对比。
（5）4号位的E节点，A->E权值为32767，比3号位的D节点D->E权值为60大，更新。
变化后的最短边数组如下：
[2023-6]--[ Debug ]--Printf ShortestEdgeArray
{(0,0),(0,20),(0,30),(0,0),(3,60)}
ArrayLen : 2
ArrayMaxLen : 5(0,20),(0,30),(3,60)的权值进行比较，发现最小的是(0,20)，返回索引号。
LowestEdgeVertexIndex : 11号索引表示B节点已经被使用。
邻接矩阵1号位：
[20 ,32767 ,32767 ,32767 ,50 ]（1）0号位的A节点已使用，不用对比。
（2）1号位的B节点已使用，不用对比。
（3）2号位的C节点，A->C权值为30，比1号位的B节点B->C权值为32767小，还是最短的，不更新。
（4）3号位的D节点已使用，不用对比。
（5）4号位的E节点，D->E权值为60，比1号位的B节点B->E权值为50大，更新。
更新最短边数组：
[2023-6]--[ Debug ]--Printf ShortestEdgeArray
{(0,0),(0,0),(0,30),(0,0),(1,50)}
ArrayLen : 3
ArrayMaxLen : 5（0，30）为最小的权值，对应的索引号为2，表示C节点。
邻接矩阵2号位：
[30 ,32767 ,32767 ,40 ,32767 ]（1）0号位的A节点已使用，不用对比。
（2）1号位的B节点已使用，不用对比。
（3）2号位的C节点已使用，不用对比。
（4）3号位的D节点已使用，不用对比。
（5）4号位的E节点，B->E权值为50，比2号位的C节点C->E权值为32767小，不更新。
[2023-6]--[ Debug ]--Printf ShortestEdgeArray
{(0,0),(0,0),(0,0),(0,0),(1,50)}
ArrayLen : 4
ArrayMaxLen : 5一个有n个顶点的连通图的生成树有n-1条边。
五个顶点，我们已经拿到四条边，可以形成MST，退出程序。
六、Linux环境代码测试
[gbase@czg2 Graph]$ make
gcc -Wall -Wextra -O3 ../Log/Log.c ../PublicFunction/PublicFunction.c ../PublicFunction/SqQueue/SqQueue.c Graph.c MinimumSpanningTree.c main.c -o TestGraph -I ../Log/ -I ../PublicFunction/ -I ../Select/ -I ../PublicFunction/SqQueue/
[gbase@czg2 Graph]$ ./TestGraph
[2023-6]--[ Info ]--Create Net Data : OK
[2023-6]--[ Info ]--Create Undirection Net Use AMGraph : OK
[2023-6]--[ Debug ]--Printf AMGraph :
VertexArray : [A ,B ,C ,D ,E ]
ArcArray :
[32767 ,20 ,30 ,10 ,32767 ]
[20 ,32767 ,32767 ,32767 ,50 ]
[30 ,32767 ,32767 ,40 ,32767 ]
[10 ,32767 ,40 ,32767 ,60 ]
[32767 ,50 ,32767 ,60 ,32767 ]
CurVertexNum : 5
CurArcNum : 12
[2023-6]--[ Info ]--Create Undirection Net Use AGraph : OK
[2023-6]--[ Debug ]--Printf AGraph :
A : [(2, 30, 0x1ff28b0),(1, 20, 0x1ff2870),(3, 10, (nil))]
B : [(4, 50, 0x1ff28d0),(0, 20, (nil))]
C : [(3, 40, 0x1ff2910),(0, 30, (nil))]
D : [(4, 60, 0x1ff2950),(2, 40, 0x1ff2890),(0, 10, (nil))]
E : [(3, 60, 0x1ff2990),(1, 50, (nil))]
VertexNum : 5
ArcNum : 12
[2023-6]--[ Debug ]--Traverse Use AMGraph : [4 ,1 ,0 ,2 ,3 ]
[2023-6]--[ Debug ]--Traverse Use AGraph : [4 ,3 ,2 ,0 ,1 ]
[2023-6]--[ Debug ]--Init SqQueue Normal
[2023-6]--[ Debug ]--Enter SqQueue Normal
[2023-6]--[ Debug ]--Leave SqQueue Normal
[2023-6]--[ Debug ]--Enter SqQueue Normal
[2023-6]--[ Debug ]--Enter SqQueue Normal
[2023-6]--[ Debug ]--Leave SqQueue Normal
[2023-6]--[ Debug ]--Enter SqQueue Normal
[2023-6]--[ Debug ]--Leave SqQueue Normal
[2023-6]--[ Debug ]--Enter SqQueue Normal
[2023-6]--[ Debug ]--Destroy SqQueue Normal
[2023-6]--[ Debug ]--Breadth First Search Use AMGraph OK
[2023-6]--[ Debug ]--Traverse Use AMGraph : [4 ,1 ,3 ,0 ,2 ]
[2023-6]--[ Debug ]--Init SqQueue Normal
[2023-6]--[ Debug ]--Enter SqQueue Normal
[2023-6]--[ Debug ]--Leave SqQueue Normal
[2023-6]--[ Debug ]--Enter SqQueue Normal
[2023-6]--[ Debug ]--Enter SqQueue Normal
[2023-6]--[ Debug ]--Leave SqQueue Normal
[2023-6]--[ Debug ]--Enter SqQueue Normal
[2023-6]--[ Debug ]--Enter SqQueue Normal
[2023-6]--[ Debug ]--Destroy SqQueue Normal
[2023-6]--[ Debug ]--Breadth First Search Use AGraph OK
[2023-6]--[ Debug ]--Traverse Use AGraph : [4 ,3 ,1 ,2 ,0 ]
[2023-6]--[ Debug ]--Printf ShortestEdgeArray
{(0,0),(0,20),(0,30),(0,10),(0,32767)}
ArrayLen : 1
ArrayMaxLen : 5
[2023-6]--[ Debug ]--Init ShortestEdgeArray OK
LowestEdgeVertexIndex : 3
[2023-6]--[ Debug ]--Printf ShortestEdgeArray
{(0,0),(0,20),(0,30),(0,0),(3,60)}
ArrayLen : 2
ArrayMaxLen : 5
LowestEdgeVertexIndex : 1
[2023-6]--[ Debug ]--Printf ShortestEdgeArray
{(0,0),(0,0),(0,30),(0,0),(1,50)}
ArrayLen : 3
ArrayMaxLen : 5
LowestEdgeVertexIndex : 2
[2023-6]--[ Debug ]--Printf ShortestEdgeArray
{(0,0),(0,0),(0,0),(0,0),(1,50)}
ArrayLen : 4
ArrayMaxLen : 5
LowestEdgeVertexIndex : 4
[2023-6]--[ Debug ]--Destroy ShortestEdgeArray OK
[2023-6]--[ Info ]--Prim Create MST OK
[2023-6]--[ Debug ]--Printf MST
{ (0,3,10),(0,1,20),(0,2,30),(1,4,50)}
[2023-6]--[ Info ]--Destroy Net Data : OK
[2023-6]--[ Info ]--Destroy Undirection Net Use AMGraph: OK
[2023-6]--[ Info ]--Destroy Undirection Net Use AGraph : OK