草庐IT

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

红心火柴 2023-12-01 原文

文章目录

一、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;
			}
		}
	}
}
详解Primspanclasstoken算法c语言图论

有关图之最小生成树Prim算法详解(C语言版)的更多相关文章

  1. ruby - 如何将脚本文件的末尾读取为数据文件(Perl 或任何其他语言) - 2

    我正在寻找执行以下操作的正确语法(在Perl、Shell或Ruby中):#variabletoaccessthedatalinesappendedasafileEND_OF_SCRIPT_MARKERrawdatastartshereanditcontinues. 最佳答案 Perl用__DATA__做这个:#!/usr/bin/perlusestrict;usewarnings;while(){print;}__DATA__Texttoprintgoeshere 关于ruby-如何将脚

  2. ruby - 寻找通过阅读代码确定编程语言的ruby gem？ - 2

    几个月前，我读了一篇关于ruby​​gem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？ 最佳答案 是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：

  3. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  4. Unity 热更新技术 | （三） Lua语言基本介绍及下载安装 - 2

    ?博客主页：https://xiaoy.blog.csdn.net?本文由呆呆敲代码的小Y原创，首发于CSDN??学习专栏推荐：Unity系统学习专栏?游戏制作专栏推荐：游戏制作?Unity实战100例专栏推荐：Unity实战100例教程?欢迎点赞?收藏⭐留言?如有错误敬请指正！?未来很长，值得我们全力奔赴更美好的生活✨------------------❤️分割线❤️-------------------------

  5. 7个大一C语言必学的程序 / C语言经典代码大全 - 2

    嗨~大家好，这里是可莉！今天给大家带来的是7个C语言的经典基础代码~那一起往下看下去把【程序一】打印100到200之间的素数#includeintmain(){ inti; for(i=100;i 【程序二】输出乘法口诀表#includeintmain(){inti;for(i=1;i 【程序三】判断1000年---2000年之间的闰年#includeintmain(){intyear;for(year=1000;year 【程序四】给定两个整形变量的值，将两个值的内容进行交换。这里提供两种方法来进行交换，第一种为创建临时变量来进行交换，第二种是不创建临时变量而直接进行交换。1.创建临时变量来

  6. ruby - 获取数组中的值并最小化某个类属性的最优雅的方法是什么？ - 2

    假设我有以下类(class):classPersondefinitialize(name,age)@name=name@age=ageenddefget_agereturn@ageendend我有一组Person对象。是否有一种简洁的、类似于Ruby的方法来获取最小(或最大)年龄的人？如何根据它对它们进行排序？ 最佳答案 这样做会:people_array.min_by(&:get_age)people_array.max_by(&:get_age)people_array.sort_by(&:get_age)

  7. ruby - 如何保持我不常用的编程语言技能 - 2

    关闭。这个问题是off-topic.它目前不接受答案。想改进这个问题吗？Updatethequestion所以它是on-topic用于堆栈溢出。关闭11年前。Improvethisquestion我不经常使用ruby​​-通常它加起来相当于每两个月或更长时间编写一次脚本。我的大部分编程都是使用C++进行的，这与ruby​​有很大不同。由于我与ruby​​之间的差距如此之大，我总是忘记语言的基本方面(比如解析文本文件和其他简单的东西)。我想每天练习一些基本的东西，我想知道是否有一些我可以订阅的网站，并且会向我发送当天的Ruby问题或类似的东西。有人知道这样的站点/Internet服务吗？

  8. ruby-on-rails - 如果特定语言环境中缺少翻译，如何配置 i18n 以使用 en 语言环境？ - 2

    如果特定语言环境中缺少翻译，如何配置i18n以使用en语言环境翻译？当前已插入翻译缺失消息。我正在使用RoR3.1。 最佳答案 找到相似的question这里是答案:#application.rb#railswillfallbacktoconfig.i18n.default_localetranslationconfig.i18n.fallbacks=true#railswillfallbacktoen,nomatterwhatissetasconfig.i18n.default_localeconfig.i18n.fallback

  9. ruby-on-rails - 如何通过 URL 更改语言环境？ - 2

    在我的双语Rails4应用程序中，我有一个像这样的LocalesController:classLocalesController用户可以通过此表单更改其语言环境:deflocale_switcherform_tagurl_for(:controller=>'locales',:action=>'change_locale'),:method=>'get',:id=>'locale_switcher'doselect_tag'set_locale',options_for_select(LANGUAGES,I18n.locale.to_s)end这有效。但是，目前用户无法通过URL更改

  10. ruby - 一种语言如何被自身解释(如 Rubinius)？ - 2

    我使用Ruby编程已经有一段时间了，现在只使用Ruby的标准MRI实现，但我一直对我经常听到的其他实现感到好奇。前几天我在读有关Rubinius的文章，这是一个用Ruby编写的Ruby解释器。我试着在不同的地方查找它，但我很难弄清楚这样的东西到底是如何工作的。我在编译器或语言编写方面从来没有太多经验，但我真的很想弄明白。一门语言究竟如何才能被自己解释？编译中是否有一个我不明白这有意义的基本步骤？有人可以像我是个白痴一样向我解释这个吗(因为无论如何这都不会太离谱) 最佳答案 它比你想象的要简单。Rubinius并非100%用Ruby编

随机推荐