当前位置： 首页 > article >正文

C语言-数据结构 无向图普里姆Prim算法（邻接矩阵存储）

article 2024/11/16 3:32:57

        Prim算法使用了贪心的思想，在算法中使用了两个数组，这两个数组会非常巧妙的操作整个算法的灵魂过程

lowcost的功能：

1.帮助算法寻找到当前距离已完成的最小生成树集合的最小的边长（找到新边）

2.在整个过程中记录新结点加入的时候，更新整个已完成的生成树中所有结点集合到剩余各个结点的最小值（更新当前已加入最小生成树结点集合状态下距离其他结点最短边值）

adjvex的功能：

1.存储每个新节点加入已完成最小生成树结点时，通过它找到当前新加入生成树结点集合中的前驱结点是谁，从而输出对应的边

2.更新前驱结点，帮助在下一次寻找到新结点保存对应的前驱结点（例如A->B这条边中A结点叫前驱）

        整个算法的过程时非常巧妙的，lowcost数组类似于水母的触手一开始就只有一条触手，通过触手找到当前最短的边，并把它捕获到已经完成的生成树结点中，理解为生成新的一条触手，触手数量+1，整个代码中大for循环中包含两个小循环，大for循环进行节点数-1轮，每一次从图中找到一个新结点，也就是找到最小生成树的一条边，里面第一个while循环找到当前距离水面触手最短的结点，也就是即将加入的最小生成树的边，找到后并把边对应的结点设置为0标记已经找到的边，下面的小循环for是为了更新当新的触手（新的边）加入的时候，整个水母触手（已完成的最小生成树）距离剩下的各结点之间最短的边长进行更新。并存入下一个即将加入水母触手伙伴的前驱结点，以便绘制打印出对应的边。

我们将创建下面的无向权值图：

  最小生成树示意图：

        邻接矩阵的绘制还是手动赋值上三角，并通过矩阵对称性生成整个邻接矩阵，其中最小生成树中需要用到权值，对应原本有边的地方之前我是用1表示，现在改成边对应的权值，之前的0表示没有边，现在改成99表示为无穷，其实应该换成更大的值以确保树的边权值都小于这个最大值，但为了方便对齐显示看邻接矩阵，就使用了比本图中各边长较大的99来表示最大值。

        Prim算法代码：

/* Prim算法生成最小生成树  */
void MiniSpanTree_Prim(MGraph G)
{
	int min, i, j, k;
	int adjvex[MAXVEX];		/* 保存相关顶点下标 */
	int lowcost[MAXVEX];	/* 保存相关顶点间边的权值 */
	lowcost[0] = 0;/* 初始化第一个权值为0，即v0加入生成树 */
	/* lowcost的值为0，在这里就是此下标的顶点已经加入生成树 */
	adjvex[0] = 0;			/* 初始化第一个顶点下标为0 */
	for (i = 1; i < G.numNodes; i++)	/* 循环除下标为0外的全部顶点 */
	{
		lowcost[i] = G.arc[0][i];	/* 将v0顶点与之有边的权值存入数组 */
		adjvex[i] = 0;					/* 初始化都为v0的下标 */
	}
	printf("\n最小生成树的边按顺序生成：\n");
	for (i = 1; i < G.numNodes; i++)
	{
		min = GRAPH_INFINITY;	/* 初始化最小权值为∞， */
		/* 通常设置为不可能的大数字如32767、65535等 */
		j = 0; k = 0;
		while (j < G.numNodes)	/* 循环全部顶点 */
		{
			if (lowcost[j] != 0 && lowcost[j] < min)/* 如果权值不为0且权值小于min */
			{
				min = lowcost[j];	/* 则让当前权值成为最小值 */
				k = j;			/* 将当前最小值的下标存入k */
			}
			j++;
		}
		printf("(%d, %d)\n", adjvex[k], k);/* 打印当前顶点边中权值最小的边 */
		lowcost[k] = 0;/* 将当前顶点的权值设置为0,表示此顶点已经完成任务 */
		for (j = 0; j < G.numNodes; j++)	/* 循环所有顶点 */
		{
			if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j])
			{/* 如果下标为k顶点各边权值小于此前这些顶点未被加入生成树权值 */
				lowcost[j] = G.arc[k][j];/* 将较小的权值存入lowcost相应位置 */
				adjvex[j] = k;				/* 将下标为k的顶点存入adjvex */
			}
		}
	}
}

完整代码（包含邻接矩阵的创建，Prim算法）

#include "stdio.h"    
#include "stdlib.h"   
#include "math.h"  
#include "time.h"

// 禁用特定的警告
#pragma warning(disable:4996)

// 定义一些常量和数据类型
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXVEX 8 /* 最大顶点数，用户定义 */
#define GRAPH_INFINITY 99 /* 用0表示∞，表示不存在边 */

/* 定义状态、顶点和边的类型 */
typedef int Status;  /* Status是函数的返回类型，如OK表示成功 */
typedef char VertexType; /* 顶点的类型，用字符表示 */
typedef int EdgeType; /* 边上的权值类型，用整数表示 */
typedef int Boolean; /* 布尔类型 */

/* 访问标记数组 */
Boolean visited[MAXVEX];

/* 图的邻接矩阵结构体 */
typedef struct
{
	VertexType vexs[MAXVEX]; /* 顶点表 */
	EdgeType arc[MAXVEX][MAXVEX]; /* 邻接矩阵，表示边的权值 */
	int numNodes, numEdges; /* 图中当前的顶点数和边数 */
} MGraph;

/* 创建一个无向网图的邻接矩阵表示 */
void CreateMGraph(MGraph* G)
{
	int i, j, k, w;

	// 初始化图的顶点数和边数
	G->numNodes = 8;
	G->numEdges = 12;

	// 定义顶点标签
	char Array[] = "ABCDEFGHI";

	// 初始化邻接矩阵和顶点表
	for (i = 0; i < G->numNodes; i++) {
		for (j = 0; j < G->numNodes; j++) {
			G->arc[i][j] = GRAPH_INFINITY; /* 初始化邻接矩阵为∞ */
		}
		G->vexs[i] = Array[i]; /* 初始化顶点表 */
	}

	G->arc[0][0] = GRAPH_INFINITY;
	G->arc[0][1] = 10;
	G->arc[0][2] = GRAPH_INFINITY;
	G->arc[0][3] = GRAPH_INFINITY;
	G->arc[0][4] = GRAPH_INFINITY;
	G->arc[0][5] = 11;
	G->arc[0][6] = GRAPH_INFINITY;
	G->arc[0][7] = GRAPH_INFINITY;

	G->arc[1][0] = GRAPH_INFINITY;
	G->arc[1][1] = GRAPH_INFINITY;
	G->arc[1][2] = 23;
	G->arc[1][3] = GRAPH_INFINITY;
	G->arc[1][4] = GRAPH_INFINITY;
	G->arc[1][5] = GRAPH_INFINITY;
	G->arc[1][6] = 12;
	G->arc[1][7] = GRAPH_INFINITY;

	G->arc[2][0] = GRAPH_INFINITY;
	G->arc[2][1] = GRAPH_INFINITY;
	G->arc[2][2] = GRAPH_INFINITY;
	G->arc[2][3] = 21;
	G->arc[2][4] = GRAPH_INFINITY;
	G->arc[2][5] = GRAPH_INFINITY;
	G->arc[2][6] = GRAPH_INFINITY;
	G->arc[2][7] = GRAPH_INFINITY;

	G->arc[3][0] = GRAPH_INFINITY;
	G->arc[3][1] = GRAPH_INFINITY;
	G->arc[3][2] = GRAPH_INFINITY;
	G->arc[3][3] = GRAPH_INFINITY;
	G->arc[3][4] = GRAPH_INFINITY;
	G->arc[3][5] = GRAPH_INFINITY;
	G->arc[3][6] = GRAPH_INFINITY;
	G->arc[3][7] = 11;

	G->arc[4][0] = GRAPH_INFINITY;
	G->arc[4][1] = GRAPH_INFINITY;
	G->arc[4][2] = GRAPH_INFINITY;
	G->arc[4][3] = GRAPH_INFINITY;
	G->arc[4][4] = GRAPH_INFINITY;
	G->arc[4][5] = 47;
	G->arc[4][6] = GRAPH_INFINITY;
	G->arc[4][7] = 80;

	G->arc[5][0] = GRAPH_INFINITY;
	G->arc[5][1] = GRAPH_INFINITY;
	G->arc[5][2] = GRAPH_INFINITY;
	G->arc[5][3] = GRAPH_INFINITY;
	G->arc[5][4] = GRAPH_INFINITY;
	G->arc[5][5] = GRAPH_INFINITY;
	G->arc[5][6] = 6;
	G->arc[5][7] = GRAPH_INFINITY;

	G->arc[6][0] = GRAPH_INFINITY;
	G->arc[6][1] = GRAPH_INFINITY;
	G->arc[6][2] = GRAPH_INFINITY;
	G->arc[6][3] = GRAPH_INFINITY;
	G->arc[6][4] = GRAPH_INFINITY;
	G->arc[6][5] = GRAPH_INFINITY;
	G->arc[6][6] = GRAPH_INFINITY;
	G->arc[6][7] = 8;

	G->arc[7][0] = GRAPH_INFINITY;
	G->arc[7][1] = GRAPH_INFINITY;
	G->arc[7][2] = GRAPH_INFINITY;
	G->arc[7][3] = GRAPH_INFINITY;
	G->arc[7][4] = GRAPH_INFINITY;
	G->arc[7][5] = GRAPH_INFINITY;
	G->arc[7][6] = GRAPH_INFINITY;
	G->arc[7][7] = GRAPH_INFINITY;

	// 由于是无向图，邻接矩阵是对称的，需要将其对称
	for (int i = 0; i < G->numNodes; i++) {
		for (int j = 0; j < G->numNodes; j++) {
			G->arc[j][i] = G->arc[i][j];
		}
	}

	// 打印邻接矩阵
	printf("邻接矩阵为：\n");
	printf("     ");
	for (int i = 0; i < G->numNodes; i++) {
		printf("%2d ", i); /* 打印列索引 */
	}
	printf("\n     ");
	for (int i = 0; i < G->numNodes; i++) {
		printf("%2c ", G->vexs[i]); /* 打印顶点标签 */
	}
	printf("\n");
	for (int i = 0; i < G->numNodes; i++) {
		printf("%2d", i); /* 打印行索引 */
		printf("%2c ", G->vexs[i]); /* 打印顶点标签 */
		for (int j = 0; j < G->numNodes; j++) {
			if (G->arc[i][j] != 99) {
				printf("\033[31m%02d \033[0m", G->arc[i][j]); /* 打印邻接矩阵中的权值 */
			}
			else {
				printf("%02d ", G->arc[i][j]); /* 打印邻接矩阵中的权值 */
			}
		}
		printf("\n");
	}
}

/* Prim算法生成最小生成树  */
void MiniSpanTree_Prim(MGraph G)
{
	int min, i, j, k;
	int adjvex[MAXVEX];		/* 保存相关顶点下标 */
	int lowcost[MAXVEX];	/* 保存相关顶点间边的权值 */
	lowcost[0] = 0;/* 初始化第一个权值为0，即v0加入生成树 */
	/* lowcost的值为0，在这里就是此下标的顶点已经加入生成树 */
	adjvex[0] = 0;			/* 初始化第一个顶点下标为0 */
	for (i = 1; i < G.numNodes; i++)	/* 循环除下标为0外的全部顶点 */
	{
		lowcost[i] = G.arc[0][i];	/* 将v0顶点与之有边的权值存入数组 */
		adjvex[i] = 0;					/* 初始化都为v0的下标 */
	}
	printf("\n最小生成树的边按顺序生成：\n");
	for (i = 1; i < G.numNodes; i++)
	{
		min = GRAPH_INFINITY;	/* 初始化最小权值为∞， */
		/* 通常设置为不可能的大数字如32767、65535等 */
		j = 0; k = 0;
		while (j < G.numNodes)	/* 循环全部顶点 */
		{
			if (lowcost[j] != 0 && lowcost[j] < min)/* 如果权值不为0且权值小于min */
			{
				min = lowcost[j];	/* 则让当前权值成为最小值 */
				k = j;			/* 将当前最小值的下标存入k */
			}
			j++;
		}
		printf("(%d, %d)\n", adjvex[k], k);/* 打印当前顶点边中权值最小的边 */
		lowcost[k] = 0;/* 将当前顶点的权值设置为0,表示此顶点已经完成任务 */
		for (j = 0; j < G.numNodes; j++)	/* 循环所有顶点 */
		{
			if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j])
			{/* 如果下标为k顶点各边权值小于此前这些顶点未被加入生成树权值 */
				lowcost[j] = G.arc[k][j];/* 将较小的权值存入lowcost相应位置 */
				adjvex[j] = k;				/* 将下标为k的顶点存入adjvex */
			}
		}
	}
}

int main(void)
{
	MGraph G;
	/* 创建图 */
	CreateMGraph(&G);
	//Prim算法
	MiniSpanTree_Prim(G);
	return 0;
}

最小生成树示意图：

运行结果，边是按下标输出的，下标所对应的字母按ABCDEFGH顺序来表示：


http://www.kler.cn/a/292511.html

相关文章：

  • SkyWalking-安装
  • Android 单元测试环境配置问题 Execution failed for task ‘:mergeDebugJavaResource‘.
  • 离线 快速搭建 docker docker-compose k8s 环境
  • 第四十五章 Vue之Vuex模块化创建（module）
  • ⾃动化运维利器Ansible-基础
  • RabbitMQ高效的消息队列中间件原理及实践
  • selenium连接远程chrome浏览器
  • MIT线性代数
  • 【java】将Map的value类型定义为Object
  • 第十五题：三数之和
  • rancher搭建k8s及jenkins自动化部署
  • 骨传导耳机哪款好？精选五款热门骨传导耳机分享让你避免踩雷
  • 对HashMap的理解
  • 使用本地预训练模型可视化卷积每一部分
  • 基于自适应多变量超扭转的 Lyapunov 重新设计 RLV 姿态控制
  • Facebook与区块链：构建更安全的社交网络生态
  • MFC dll无法显示tooltip问题
  • Java-数据结构-链表-习题（三）(๑´ㅂ`๑)
  • java开发简历详解
  • Dubbo缓存
  • HTML 基础知识详解与代码示例
  • C++笔记16•数据结构:关联式容器map和set•
  • Java健康养老智慧相伴养老护理小程序系统源码代办陪诊陪护更安心
  • 阿里云身份证二要素详细使用
  • 第T2周：彩色图片分类
  • 828华为云征文｜基于华为云Flexus云服务器X搭建jumpserver堡垒机软件