图之最小生成树Prim算法详解(C语言版)

这篇具有很好参考价值的文章主要介绍了图之最小生成树Prim算法详解(C语言版)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


一、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,使用普里姆算法查找最小生成树,需经历以下过程:
prim算法c语言,数据结构与算法,算法,c语言,图论
设置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
prim算法c语言,数据结构与算法,算法,c语言,图论

此时,因为顶点 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
prim算法c语言,数据结构与算法,算法,c语言,图论

此时,因为顶点 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
prim算法c语言,数据结构与算法,算法,c语言,图论

此时,因为顶点 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
prim算法c语言,数据结构与算法,算法,c语言,图论
此时,因为顶点 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构建成功,如下图所示:
prim算法c语言,数据结构与算法,算法,c语言,图论

二、数据结构

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;

prim算法c语言,数据结构与算法,算法,c语言,图论

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');
}

运行结果
prim算法c语言,数据结构与算法,算法,c语言,图论

测试的图结构
prim算法c语言,数据结构与算法,算法,c语言,图论

获取的最小生成树
prim算法c语言,数据结构与算法,算法,c语言,图论

附录

测试代码

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文章来源地址https://www.toymoban.com/news/detail-779197.html

#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;
			}
		}
	}
}

到了这里,关于图之最小生成树Prim算法详解(C语言版)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C语言实现最小生成树算法:Prim和Kruskal

    以下是使用C语言实现Prim算法生成最小生成树的代码: 注释如下: #include stdio.h 和 `#include #define V 5 定义了图中顶点的个数为5。 int minDistance(int dist[], int visited[]) 函数用于找到顶点集合中未访问的顶点中距离最小的顶点。输入参数 dist 用于存储顶点到最小生成树的距离,输入

    2024年02月03日
    浏览(43)
  • 【数据结构与算法】最小生成树之普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法

      🌱博客主页:大寄一场. 🌱系列专栏:数据结构与算法 😘博客制作不易欢迎各位👍点赞+⭐收藏+➕关注 目录 前言 一、最小生成树的概念 二、最小生成树的求解方法 三、练习题 四、最小生成树在实际应用中的例子 最近非科班的同学学到了最小生成树并询问我,于是想趁

    2024年02月07日
    浏览(42)
  • 【数据结构】最小生成树(Prim算法,普里姆算法,普利姆)、最短路径(Dijkstra算法,迪杰斯特拉算法,单源最短路径)

    问题解答 (1)最小生成树(Minimal Spanning Tree)的定义 生成树的代价 :设 G ( V , E ) G(V,E) G ( V , E ) 是一个无向连通网图,生成树上 各边的权值之和 称为 生成树的代价 。 最小生成树 :在图 G G G 所有生成树中, 代价最小的生成树 为 最小生成树 。 (2)最小生成树(MST)的性

    2024年02月11日
    浏览(39)
  • 考研算法复试刷题19天:Prim算法求最小生成树 【prim,最小生成树】

    参考博客:图解:什么是最小生成树? - 知乎 (zhihu.com)  总结下来的过程就是,一张图,我们将他化为树的形式,也就是生成树。那么最小生成树有是啥呢? 所谓一个 带权图 的最小生成树,就是原图中边的权值最小的生成树 ,所谓最小是指边的权值之和小于或者等于其它

    2024年02月07日
    浏览(64)
  • 最小生成树—Prim算法

    我们要讨论的问题是如何在一个 无向图 中找到它的最小生成树,虽然这个问题对有向图也有意义,但是处理起来更麻烦。 一个无向图 G 的最小生成树就是连接 G 上所有顶点的边构成的树,且这些边的总权值最低。当且仅当图是 连通的 才有最小生成树。 在无向图的最小生成

    2024年02月09日
    浏览(49)
  • 贪心算法:最小生成树Prim算法

    👨‍🎓作者简介:一位喜欢写作,计科专业大二菜鸟 🏡个人主页:starry陆离 🕒首发日期:2022年5月31日星期二 🌌上期文章:动态规划:多重背包问题 📚订阅专栏:算法分析与设计 如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦 这是大一暑假的c笔记,再一次写pri

    2024年02月01日
    浏览(52)
  • Prim算法求最小生成树

    给定一张边带无权的无向图G = (V, E), n = |V|, m = |E|。由V中全部n个顶点和E中n - 1条边构成的无向连通子图被称为G的一课生成树。边的权值之和最小的生成树被称为无向图的最小生成树。 Prim算法总是维护最小生成树的一部分。最初,Prim算法仅确定1号节点属于最小生成树

    2024年02月12日
    浏览(44)
  • 最小生成树——prim算法实现

    N个城市之间需要铺设一张交通网,使任意两个城市间都有交通路线直达,现已知各个城市之间铺设道路的经济成本,问该如何求算铺网的最低经济成本?为求算最低经济成本,可以假设N个城市就是连通网G的N个顶点,而求算最低成本问题可以转化为在N个城市间找到N-1条边,

    2024年02月08日
    浏览(38)
  • Prim算法实现最小生成树

    例如:要在n个城市之间铺设光缆,主要目标是要使这n个城市的任意两个之间都可以通信,但铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。 将图中所有顶点分为两类:树顶点(已

    2024年02月11日
    浏览(43)
  • 最小生成树(Prim算法,Kruskal算法)

    (1)生成树: 如果在一个无向连通图不包含回路(连通图中不存在环),则为一个树 (2)最小生成树(minimal spanning tree): 在一个图所有生成树中,代价最小的生成树称为最小生成树 (3)生成树的代价: 在一个无向连通网中,生成树各边的权值之和称为该生成树的代价

    2024年02月08日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包