文章目录

一、Prim算法思想

普里姆算法采用贪心算法的思想来查找最小生成树。对于包含 N 个顶点的连通网，普里姆算法每次从连通网中找出一个权值最小的边，这样的操作重复 N-1次，由N-1条权值最小的边组成的生成树就是最小生成树MST（Minimum Spanning Tree，最小生成树）。

那么，如何找出N-1条权值最小的边呢？普里姆算法的实现思路是：

  1. 将连通网中的所有顶点分为两类（假设为 A 类和 B 类）。初始状态下，所有顶点位于 B 类；
  2. 选择任意一个顶点，将其从 B 类移动到 A 类；
  3. 从 B 类的所有顶点出发，找出一条连接着 A 类中的某个顶点且权值最小的边，将此边连接着的 A 类中的顶点移动到 B 类；
  4. 重复执行第 3 步，直至 B 类中的所有顶点全部移动到 A 类，恰好可以找到 N-1 条边。

举个例子，下图是一个连通网有A、B、C、D、E、F六个顶点，它们的编号依次是0、1、2、3、4、5，使用普里姆算法查找最小生成树，需经历以下过程：
在这里插入图片描述
设置2个数据结构：
lowcost[i]:表示以 i 为终点的边的最小权值,当lowcost[i]=0说明以i为终点的边的最小权值等于0,也就是表示 i 点加入了MST
mst[i]:表示对应lowcost[i]的起点，即说明边<mst[i],i>是MST的一条边(即<起点,终点>)，当mst[i]=-1表示起点 i 加入MST

我们假设顶点 A 是起始点，进行初始化（*代表无限大，即无通路）：

以i为终点的边的最小权值
lowcost[0]=0
lowcost[1]=6
lowcost[2]=1
lowcost[3]=5
lowcost[4]=*
lowcost[5]=*

对应lowcost[i]的起点(所有点默认起点是A)
mst[0]=-1
mst[1]=0
mst[2]=0
mst[3]=0
mst[4]=0
mst[5]=0

明显看出，以顶点 C 为终点的边的权值最小等于1，所以边<mst[2],2>=1加入MST（即lowcost[2]=0,mst[2]=-1）
在这里插入图片描述

此时，因为顶点 C 的加入，就能够获取到以顶点 C 为起点的边信息以及边相应终点的信息，需要更新lowcost数组和mst数组：

lowcost[0]=0
lowcost[1]=5
lowcost[2]=0
lowcost[3]=5
lowcost[4]=6
lowcost[5]=4
mst[0]=-1
mst[1]=2
mst[2]=-1
mst[3]=0
mst[4]=2
mst[5]=2

明显看出，以顶点 F 为终点的边的权值最小等于4，所以边<mst[5],5>=4加入MST（即lowcost[5]=0,mst[5]=-1）
在这里插入图片描述

此时，因为顶点 F 的加入，就能够获取到以顶点 F 为起点的边信息以及边相应终点的信息，需要更新lowcost数组和mst数组：

lowcost[0]=0
lowcost[1]=5
lowcost[2]=0
lowcost[3]=2
lowcost[4]=6
lowcost[5]=0
mst[0]=-1
mst[1]=2
mst[2]=-1
mst[3]=5
mst[4]=2
mst[5]=-1

明显看出，以顶点 D 为终点的边的权值最小等于2，所以边<mst[3],3>=2加入MST（即lowcost[3]=0,mst[3]=-1）
在这里插入图片描述

此时，因为顶点 D 的加入，就能够获取到以顶点 D 为起点的边信息以及边相应终点的信息，需要更新lowcost数组和mst数组：

lowcost[0]=0
lowcost[1]=5
lowcost[2]=0
lowcost[3]=0
lowcost[4]=6
lowcost[5]=0
mst[0]=-1
mst[1]=2
mst[2]=-1
mst[3]=-1
mst[4]=2
mst[5]=-1

明显看出，以顶点 B 为终点的边的权值最小等于5，所以边<mst[1],1>=5加入MST（即lowcost[1]=0,mst[1]=-1）
在这里插入图片描述
此时，因为顶点 B 的加入，就能够获取到以顶点 B 为起点的边信息以及边相应终点的信息，需要更新lowcost数组和mst数组：

lowcost[0]=0
lowcost[1]=0
lowcost[2]=0
lowcost[3]=0
lowcost[4]=3
lowcost[5]=0
mst[0]=-1
mst[1]=-1
mst[2]=-1
mst[3]=-1
mst[4]=1
mst[5]=-1

很明显，以顶点 E 为终点的边的权值最小等于3，所以边<mst[4],4>=3加入MST（即lowcost[4]=0,mst[4]=-1）

lowcost[0]=0
lowcost[1]=0
lowcost[2]=0
lowcost[3]=0
lowcost[4]=0
lowcost[5]=0
mst[0]=-1
mst[1]=-1
mst[2]=-1
mst[3]=-1
mst[4]=-1
mst[5]=-1

至此，MST构建成功,如下图所示：
在这里插入图片描述

二、数据结构

1、使用邻接矩阵存放图结构
对于邻接矩阵不是很了解的可以查看文章：图之邻接矩阵详解（C语言版）

//设置默认的顶点个数
#define Default_Vertex_Size  10
//数据类型
#define T char
#define E int
#define MAX_COST  0x7FFFFFFF //代表无穷大

//邻接矩阵图结构
typedef struct GraphMtx
{
	int MaxVertices; //最大顶点数
	int NumVertices; //真实的顶点数
	int NumEdges;  //边数

	T   *VerticesList; //顶点列表
	int **Edge; //边信息矩阵
}GraphMtx;

在这里插入图片描述

2、使用lowcost数组和mst数组辅助完成Prim算法

  • lowcost[i]:表示以 i 为终点的边的最小权值,当lowcost[i]=0说明以i为终点的边的最小权值等于0,也就是表示 i 点加入了MST
  • mst[i]:表示对应lowcost[i]的起点，即说明边<mst[i],i>是MST的一条边(即<起点,终点>)，当mst[i]=0表示起点 i 加入MST，当mst[i]=-1表示起点 i 加入MST
int n = g->NumVertices; //获取图的顶点个数
//lowcost[i]:表示以i为终点的边的最小权值,当lowcost[i]=0说明以i为终点的边的最小权值=0,也就是表示i点加入了MST
E *lowcost = (E*)malloc(sizeof(E)*n); //lowcost[n] 
//mst[i]:表示对应lowcost[i]的起点，即说明边<mst[i],i>是MST的一条边
int *mst = (int *)malloc(sizeof(int)*n);//mst[n]

三、代码实现

1、邻接矩阵实现

图初始化

//图的初始化
void InitGraph(GraphMtx *g)
{
	g->MaxVertices = Default_Vertex_Size;//最大顶点数初始化
	g->NumVertices = g->NumEdges = 0; //实际顶点数初始化

	//分配顶点存储列表的空间
	g->VerticesList = (T*)malloc(sizeof(T)*(g->MaxVertices));
	assert(g->VerticesList != NULL);

	//开辟边信息存储矩阵的空间（二维数组的动态开辟）
	g->Edge = (int**)malloc(sizeof(int*) * g->MaxVertices); //总行数的开辟
	assert(g->Edge != NULL);
	for(int i=0; i<g->MaxVertices; ++i) //每一行内具体的空间开辟
	{
		g->Edge[i] = (int*)malloc(sizeof(int) * g->MaxVertices);
	}
	for(i=0; i<g->MaxVertices; ++i)  //初始化
	{
		for(int j=0; j<g->MaxVertices; ++j)
		{
			if(i == j)
			{
				g->Edge[i][j] = 0;
			}
			else
			{
				g->Edge[i][j] = MAX_COST;
			}
		}
	}
}

获取顶点的位置

//获取顶点的位置
int  GetVertexPos(GraphMtx *g, T v)
{
	for(int i=0; i<g->NumVertices; ++i) //对所有顶点进行遍历
	{
		//判断是否找到顶点v所在位置
		if(g->VerticesList[i] == v)
			return i;
	}
	return -1;
}

打印图信息

//打印图信息
void ShowGraph(GraphMtx *g)
{
	printf("  ");
	for(int i=0; i<g->NumVertices; ++i) //获取顶点，并打印
	{
		printf("%c  ",g->VerticesList[i]);
	}
	printf("\n");
	for(i=0; i<g->NumVertices; ++i) //打印顶点间边的信息
	{
		printf("%c ",g->VerticesList[i]);
		for(int j=0; j<g->NumVertices; ++j)
		{
			if(g->Edge[i][j] == MAX_COST)
			{
				printf("%c  ",'@');
			}
			else
			{
				printf("%d  ",g->Edge[i][j]);
			}
		}
		printf("\n");
	}
	printf("\n");
}

插入顶点

//插入顶点
void InsertVertex(GraphMtx *g, T v)
{
	if(g->NumVertices >= g->MaxVertices) //判断顶点空间是否已满
		return;
	g->VerticesList[g->NumVertices++] = v; //还有空间，放入顶点
}

插入边：在v1和v2顶点间插入边

//插入边：在v1和v2顶点间插入边
void InsertEdge(GraphMtx *g, T v1, T v2, E cost)
{
	int p1 = GetVertexPos(g,v1);  //获取v1顶点位置
	int p2 =  GetVertexPos(g,v2);  //获取v2顶点位置
	if(p1==-1 || p2==-1)
		return;

	//无向图存储 需要双向的
	g->Edge[p1][p2] = g->Edge[p2][p1] = cost;
	g->NumEdges++; //记录实际边数
}

删除边：删除v1和v2顶点间的边

//删除边：删除v1和v2顶点间的边
void RemoveEdge(GraphMtx *g, T v1, T v2)
{
	//求出两个顶点的下标位置
	int p1 = GetVertexPos(g,v1);
	int p2 =  GetVertexPos(g,v2);
	if(p1==-1 || p2==-1)
		return;

	if(g->Edge[p1][p2] == 0)
		return;

	//将边清空
	g->Edge[p1][p2] = g->Edge[p2][1] = 0;
	g->NumEdges--; //更新边数
}

删除顶点

//删除顶点
void RemoveVertex(GraphMtx *g, T v)
{
	//获取顶点的位置
	int p = GetVertexPos(g,v);
	if(p == -1)
		return;

	
	//释放顶点
	int numedges = 0;

	for(int i=p; i<g->NumVertices-1; ++i)
	{
		//将要释放顶点之后的顶点逐一前移
		g->VerticesList[i] = g->VerticesList[i+1];
	}

	//统计与要删除顶点相连的边条数
	for(i=0; i<g->NumVertices; ++i)
	{
		if(g->Edge[p][i] != 0)
		{
			numedges++;
		}
	}

	//删除与释放顶点相连的边（更改存放边信息的矩阵）
	for(i=p; i<g->NumVertices-1; ++i)
	{
		//将要删除行之后的行逐一向前移动一行
		for(int j=0; j<g->NumVertices; ++j)
		{
			g->Edge[i][j] = g->Edge[i+1][j];
		}
	}

	for(i=p; i<g->NumVertices; ++i)//删除列
	{
		//将要删除列之后的列逐一向前移动一列
		for(int j=0; j<g->NumVertices; ++j)
		{
			g->Edge[j][i] = g->Edge[j][i+1];
		}
	}
	g->NumVertices--;
	g->NumEdges -= numedges;
}

销毁图

//销毁图
void DestroyGraph(GraphMtx *g)
{
	//释放顶点
	free(g->VerticesList);
	g->VerticesList = NULL;
	//释放边存储结构的列
	for(int i=0; i<g->NumVertices; ++i)
	{
		free(g->Edge[i]);
	}
	free(g->Edge);//释放存放行指针的空间
	g->Edge = NULL;
	g->MaxVertices = g->NumEdges = g->NumVertices = 0;
}

获取v第一个邻接顶点

//获取v第一个邻接顶点
int  GetFirstNeighbor(GraphMtx *g, T v)
{
	//获取顶点v所在位置
	int p = GetVertexPos(g,v);
	if(p == -1)
		return -1;

	//对顶点进行搜索，看那个顶点与v相连
	for(int i=0; i<g->NumVertices; ++i)
	{
		//判断是否，找到
		if(g->Edge[p][i] == 1)
			return i; //找到即返回
	}
	return -1;
}

获取下一个邻接顶点：获取顶点v的邻接顶点（该邻接点的顺序在邻接点w之后）

//获取下一个邻接顶点：获取顶点v的邻接顶点（该邻接点的顺序在邻接点w之后）
int  GetNextNeighbor(GraphMtx *g, T v, T w)
{
	//获取v和w所在位置
	int pv = GetVertexPos(g,v);
	int pw = GetVertexPos(g,w);
	if(pv==-1 || pw==-1)
		return -1;

	//从v的邻接顶点w的位置向后搜索，找到第一个与v相邻的顶点，即所求
	for(int i=pw+1; i<g->NumVertices; ++i)
	{
		
		if(g->Edge[pv][i] == 1)
			return i; 
	}
	return -1;
}

获取边的权重

//获取边的权重
E    GetWeight(GraphMtx *g, int v1, int v2)
{
	if(v1==-1 || v2==-1)
		return MAX_COST;
	return g->Edge[v1][v2];
}

2、Prim算法实现

//通过Prim算法获取最小生成树，其中g为邻接矩阵表示的图，vertex为生成树的起点
void MinSpanTree_Prim(GraphMtx *g, T vertex)
{
	int n = g->NumVertices; //获取图的顶点个数
	//lowcost[i]:表示以i为终点的边的最小权值,当lowcost[i]=0说明以i为终点的边的最小权值=0,也就是表示i点加入了MST
	E *lowcost = (E*)malloc(sizeof(E)*n); //lowcost[n] 
	//mst[i]:表示对应lowcost[i]的起点，即说明边<mst[i],i>是MST的一条边，当mst[i]=-1表示起点 i 加入MST
	int *mst = (int *)malloc(sizeof(int)*n);//mst[n]
	assert(lowcost!=NULL && mst!=NULL);

	//初始化lowcost和mst
	int k = GetVertexPos(g,vertex);//获取顶点的位置
	for(int i=0; i<n; ++i)
	{
		if(i != k)
		{
			
			lowcost[i] = GetWeight(g,k,i); //保存边值	
			mst[i] = k; //保存顶点
		}
		else
		{
			lowcost[i] = 0; //保存边值,表示i点加入了MST
			mst[i] = -1; //保存顶点,表示i点加入了MST
		}
	}

	int min,min_index;
	int begin,end;
	E cost;

	for(i=0; i<n-1; ++i)
	{
		min = MAX_COST;
		min_index = -1;
		//寻找最小的花费代价，并且记录对应的终止顶点
		for(int j=0; j<n; ++j)
		{
			
			if(lowcost[j]!=0 && lowcost[j]<min)
			{//顶点未加入到数组中且边的权值小于最小值			
				min = lowcost[j];
				min_index = j;
			}
		}
		//获取查找到的权值最小边的起始位置和终止位置
		begin = mst[min_index]; //起始顶点位置
		end = min_index; //终止顶点位置
		printf("%c-->%c : %d\n",g->VerticesList[begin],g->VerticesList[end],min);//最小生成树的顶点和边
		//将找到权值最小边的终止顶点标记为已经处理
		lowcost[min_index] = 0;
		mst[min_index] = -1;

		//查询与新加入的顶点相连接的边是否有存在更短的，有的话就需要进行记录
		for(j=0; j<n; ++j)
		{
			cost = GetWeight(g,min_index,j);
			if(cost < lowcost[j])
			{
				lowcost[j] = cost;
				mst[j] = min_index;
			}
		}
	}
}

3、运行结果

#include"GraphMtx.h"

void main()
{
	//使用邻接矩阵来存放图结构
	GraphMtx gm;
	InitGraph(&gm);
	//插入图结点
	InsertVertex(&gm,'A');
	InsertVertex(&gm,'B');
	InsertVertex(&gm,'C');
	InsertVertex(&gm,'D');
	InsertVertex(&gm,'E');
	InsertVertex(&gm,'F');
	//插入边
	InsertEdge(&gm,'A','B',6);
	InsertEdge(&gm,'A','C',1);
	InsertEdge(&gm,'A','D',5);
	InsertEdge(&gm,'B','C',5);
	InsertEdge(&gm,'B','E',3);
	InsertEdge(&gm,'C','D',5);
	InsertEdge(&gm,'C','E',6);
	InsertEdge(&gm,'C','F',4);
	InsertEdge(&gm,'D','F',2);
	InsertEdge(&gm,'E','F',6);
	ShowGraph(&gm);
	//获取以'E'为起点的最小生成树
	MinSpanTree_Prim(&gm,'E');
}

运行结果
在这里插入图片描述

测试的图结构
在这里插入图片描述

获取的最小生成树
在这里插入图片描述

附录

测试代码

Main.cpp

#include"GraphMtx.h"

void main()
{
	//使用邻接矩阵来存放图结构
	GraphMtx gm;
	InitGraph(&gm);
	//插入图结点
	InsertVertex(&gm,'A');
	InsertVertex(&gm,'B');
	InsertVertex(&gm,'C');
	InsertVertex(&gm,'D');
	InsertVertex(&gm,'E');
	InsertVertex(&gm,'F');
	//插入边
	InsertEdge(&gm,'A','B',6);
	InsertEdge(&gm,'A','C',1);
	InsertEdge(&gm,'A','D',5);
	InsertEdge(&gm,'B','C',5);
	InsertEdge(&gm,'B','E',3);
	InsertEdge(&gm,'C','D',5);
	InsertEdge(&gm,'C','E',6);
	InsertEdge(&gm,'C','F',4);
	InsertEdge(&gm,'D','F',2);
	InsertEdge(&gm,'E','F',6);
	ShowGraph(&gm);
	//获取以'E'为起点的最小生成树
	MinSpanTree_Prim(&gm,'E');
}

GraphMtx.h

#pragma once
#include<stdio.h>
#include<malloc.h>
#include<assert.h>

//设置默认的顶点个数
#define Default_Vertex_Size  10
//数据类型
#define T char
#define E int
#define MAX_COST  0x7FFFFFFF //代表无穷大

//邻接矩阵图结构
typedef struct GraphMtx
{
	int MaxVertices; //最大顶点数
	int NumVertices; //真实的顶点数
	int NumEdges;  //边数

	T   *VerticesList; //顶点列表
	int **Edge; //边信息矩阵
}GraphMtx;

void InitGraph(GraphMtx *g);
int  GetVertexPos(GraphMtx *g, T v);
void ShowGraph(GraphMtx *g);
void InsertVertex(GraphMtx *g, T v);
void InsertEdge(GraphMtx *g, T v1, T v2, E cost);
void RemoveVertex(GraphMtx *g, T v);
void RemoveEdge(GraphMtx *g, T v1, T v2);
void DestroyGraph(GraphMtx *g);
int  GetFirstNeighbor(GraphMtx *g, T v);
int  GetNextNeighbor(GraphMtx *g, T v, T w);

E    GetWeight(GraphMtx *g, int v1, int v2);
void MinSpanTree_Prim(GraphMtx *g, T vertex);

GraphMtx.cpp

#include"GraphMtx.h"

//图的初始化
void InitGraph(GraphMtx *g)
{
	g->MaxVertices = Default_Vertex_Size;//最大顶点数初始化
	g->NumVertices = g->NumEdges = 0; //实际顶点数初始化

	//分配顶点存储列表的空间
	g->VerticesList = (T*)malloc(sizeof(T)*(g->MaxVertices));
	assert(g->VerticesList != NULL);

	//开辟边信息存储矩阵的空间（二维数组的动态开辟）
	g->Edge = (int**)malloc(sizeof(int*) * g->MaxVertices); //总行数的开辟
	assert(g->Edge != NULL);
	for(int i=0; i<g->MaxVertices; ++i) //每一行内具体的空间开辟
	{
		g->Edge[i] = (int*)malloc(sizeof(int) * g->MaxVertices);
	}
	for(i=0; i<g->MaxVertices; ++i)  //初始化
	{
		for(int j=0; j<g->MaxVertices; ++j)
		{
			if(i == j)
			{
				g->Edge[i][j] = 0;
			}
			else
			{
				g->Edge[i][j] = MAX_COST;
			}
		}
	}
}

//获取顶点的位置
int  GetVertexPos(GraphMtx *g, T v)
{
	for(int i=0; i<g->NumVertices; ++i) //对所有顶点进行遍历
	{
		//判断是否找到顶点v所在位置
		if(g->VerticesList[i] == v)
			return i;
	}
	return -1;
}

//打印图信息
void ShowGraph(GraphMtx *g)
{
	printf("  ");
	for(int i=0; i<g->NumVertices; ++i) //获取顶点，并打印
	{
		printf("%c  ",g->VerticesList[i]);
	}
	printf("\n");
	for(i=0; i<g->NumVertices; ++i) //打印顶点间边的信息
	{
		printf("%c ",g->VerticesList[i]);
		for(int j=0; j<g->NumVertices; ++j)
		{
			if(g->Edge[i][j] == MAX_COST)
			{
				printf("%c  ",'@');
			}
			else
			{
				printf("%d  ",g->Edge[i][j]);
			}
		}
		printf("\n");
	}
	printf("\n");
}

//插入顶点
void InsertVertex(GraphMtx *g, T v)
{
	if(g->NumVertices >= g->MaxVertices) //判断顶点空间是否已满
		return;
	g->VerticesList[g->NumVertices++] = v; //还有空间，放入顶点
}

//插入边：在v1和v2顶点间插入边
void InsertEdge(GraphMtx *g, T v1, T v2, E cost)
{
	int p1 = GetVertexPos(g,v1);  //获取v1顶点位置
	int p2 =  GetVertexPos(g,v2);  //获取v2顶点位置
	if(p1==-1 || p2==-1)
		return;

	//无向图存储 需要双向的
	g->Edge[p1][p2] = g->Edge[p2][p1] = cost;
	g->NumEdges++; //记录实际边数
}

//删除边：删除v1和v2顶点间的边
void RemoveEdge(GraphMtx *g, T v1, T v2)
{
	//求出两个顶点的下标位置
	int p1 = GetVertexPos(g,v1);
	int p2 =  GetVertexPos(g,v2);
	if(p1==-1 || p2==-1)
		return;

	if(g->Edge[p1][p2] == 0)
		return;

	//将边清空
	g->Edge[p1][p2] = g->Edge[p2][1] = 0;
	g->NumEdges--; //更新边数
}

//删除顶点
void RemoveVertex(GraphMtx *g, T v)
{
	//获取顶点的位置
	int p = GetVertexPos(g,v);
	if(p == -1)
		return;

	
	//释放顶点
	int numedges = 0;

	for(int i=p; i<g->NumVertices-1; ++i)
	{
		//将要释放顶点之后的顶点逐一前移
		g->VerticesList[i] = g->VerticesList[i+1];
	}

	//统计与要删除顶点相连的边条数
	for(i=0; i<g->NumVertices; ++i)
	{
		if(g->Edge[p][i] != 0)
		{
			numedges++;
		}
	}

	//删除与释放顶点相连的边（更改存放边信息的矩阵）
	for(i=p; i<g->NumVertices-1; ++i)
	{
		//将要删除行之后的行逐一向前移动一行
		for(int j=0; j<g->NumVertices; ++j)
		{
			g->Edge[i][j] = g->Edge[i+1][j];
		}
	}

	for(i=p; i<g->NumVertices; ++i)//删除列
	{
		//将要删除列之后的列逐一向前移动一列
		for(int j=0; j<g->NumVertices; ++j)
		{
			g->Edge[j][i] = g->Edge[j][i+1];
		}
	}
	g->NumVertices--;
	g->NumEdges -= numedges;
}

//销毁图
void DestroyGraph(GraphMtx *g)
{
	//释放顶点
	free(g->VerticesList);
	g->VerticesList = NULL;
	//释放边存储结构的列
	for(int i=0; i<g->NumVertices; ++i)
	{
		free(g->Edge[i]);
	}
	free(g->Edge);//释放存放行指针的空间
	g->Edge = NULL;
	g->MaxVertices = g->NumEdges = g->NumVertices = 0;
}

//获取v第一个邻接顶点
int  GetFirstNeighbor(GraphMtx *g, T v)
{
	//获取顶点v所在位置
	int p = GetVertexPos(g,v);
	if(p == -1)
		return -1;

	//对顶点进行搜索，看那个顶点与v相连
	for(int i=0; i<g->NumVertices; ++i)
	{
		//判断是否，找到
		if(g->Edge[p][i] == 1)
			return i; //找到即返回
	}
	return -1;
}

//获取下一个邻接顶点：获取顶点v的邻接顶点（该邻接点的顺序在邻接点w之后）
int  GetNextNeighbor(GraphMtx *g, T v, T w)
{
	//获取v和w所在位置
	int pv = GetVertexPos(g,v);
	int pw = GetVertexPos(g,w);
	if(pv==-1 || pw==-1)
		return -1;

	//从v的邻接顶点w的位置向后搜索，找到第一个与v相邻的顶点，即所求
	for(int i=pw+1; i<g->NumVertices; ++i)
	{
		
		if(g->Edge[pv][i] == 1)
			return i; 
	}
	return -1;
}

//获取边的权重
E    GetWeight(GraphMtx *g, int v1, int v2)
{
	if(v1==-1 || v2==-1)
		return MAX_COST;
	return g->Edge[v1][v2];
}

//通过Prim算法获取最小生成树，其中g为邻接矩阵表示的图，vertex为生成树的起点
void MinSpanTree_Prim(GraphMtx *g, T vertex)
{
	int n = g->NumVertices; //获取图的顶点个数
	//lowcost[i]:表示以i为终点的边的最小权值,当lowcost[i]=0说明以i为终点的边的最小权值=0,也就是表示i点加入了MST
	E *lowcost = (E*)malloc(sizeof(E)*n); //lowcost[n] 
	//mst[i]:表示对应lowcost[i]的起点，即说明边<mst[i],i>是MST的一条边，当mst[i]=-1表示起点 i 加入MST
	int *mst = (int *)malloc(sizeof(int)*n);//mst[n]
	assert(lowcost!=NULL && mst!=NULL);

	//初始化lowcost和mst
	int k = GetVertexPos(g,vertex);//获取顶点的位置
	for(int i=0; i<n; ++i)
	{
		if(i != k)
		{
			
			lowcost[i] = GetWeight(g,k,i); //保存边值	
			mst[i] = k; //保存顶点
		}
		else
		{
			lowcost[i] = 0; //保存边值,表示i点加入了MST
			mst[i] = -1; //保存顶点,表示i点加入了MST
		}
	}

	int min,min_index;
	int begin,end;
	E cost;

	for(i=0; i<n-1; ++i)
	{
		min = MAX_COST;
		min_index = -1;
		//寻找最小的花费代价，并且记录对应的终止顶点
		for(int j=0; j<n; ++j)
		{
			
			if(lowcost[j]!=0 && lowcost[j]<min)
			{//顶点未加入到数组中且边的权值小于最小值			
				min = lowcost[j];
				min_index = j;
			}
		}
		//获取查找到的权值最小边的起始位置和终止位置
		begin = mst[min_index]; //起始顶点位置
		end = min_index; //终止顶点位置
		printf("%c-->%c : %d\n",g->VerticesList[begin],g->VerticesList[end],min);//最小生成树的顶点和边
		//将找到权值最小边的终止顶点标记为已经处理
		lowcost[min_index] = 0;
		mst[min_index] = -1;

		//查询与新加入的顶点相连接的边是否有存在更短的，有的话就需要进行记录
		for(j=0; j<n; ++j)
		{
			cost = GetWeight(g,min_index,j);
			if(cost < lowcost[j])
			{
				lowcost[j] = cost;
				mst[j] = min_index;
			}
		}
	}
}
# 算法 # c语言 # 图论
Logo
GitCode 开源社区

旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。

更多推荐

cover

GitTalk | DevUI Admin 前端项目构建

avatar GitCode 开源社区
cover

GitTalk | 使用面向业务的狮偶编程语言提升开发效率

avatar GitCode 开源社区
cover

GitTalk | DevUI Suits 场景解决方案

avatar GitCode 开源社区