C语言Prim算法和Prim-Alternat找最小生成树

2024-06-03 15:28

本文主要是介绍C语言Prim算法和Prim-Alternat找最小生成树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

    • 1、用prim算法求最小生成树
      • C语言Prim算法实现
    • 2、用Prim-Alternate算法求最小生成树
      • 3、C语言Prim-Alternate算法实现

1、用prim算法求最小生成树

绿色线会标记选过的边

在这里插入图片描述

从v1当作起始点开始,可选择:
(v1,v2)权值为6
(v1,v3)权值为3
(v1,v4)权值为1
从中选择边(v1,v4),最小权值为1
在这里插入图片描述

从v1和v4中选连接边,可选择的边有:
(v1,v2)权值为6
(v1,v3)权值为3
(v4,v3)权值为2
(v4,v5)权值为10
从中选择权值最小为2的边,(v4,v3)
在这里插入图片描述

v1,v4,v3已经被标记不能相互连接,避免产生回路,从v1、v4、v3中可选择的边有:
(v1,v2)权值为6
(v4,v5)权值为10
(v3,v2)权值为2
从中选择权值最小为2的边,(v3,v2)
在这里插入图片描述

从v1,v4,v3,v2中可选择的边有:
(v2,v9)权值为1
(v4,v5)权值为10
从中选择权值最小1的边,(v2,v9)
在这里插入图片描述

从v1,v4,v3,v2,v9中可选边有:
(v4,v5)权值为10
(v9,v5)权值为 6
(v9,v6)权值为 4
(v9,v7)权值为 3
(v9,v8)权值为 2
从中选择权值最小2的边,(v9,v8)
在这里插入图片描述

从v1,v4,v3,v2,v9,v8中可选边有:
(v4,v5)权值为10
(v9,v5)权值为 6
(v9,v6)权值为 4
(v9,v7)权值为 3
(v8,v7)权值为 3
从中有两条权值为3的边,任选一条(v8,v7)
在这里插入图片描述

从v1,v4,v3,v2,v9,v8,v7中可选边有:
(v4,v5)权值为10
(v9,v5)权值为 6
(v9,v6)权值为 4
(v7,v6)权值为 4
从两条权值为4的边,任选一条(v7,v6)
在这里插入图片描述

从v1,v4,v3,v2,v9,v8,v7,v6中可选边有:
(v4,v5)权值为10
(v9,v5)权值为 6
(v6,v5)权值为 2
选择最小权值为2的边(v6,v5)
在这里插入图片描述

v1,v4,v3,v2,v9,v8,v7,v6,v5所有点被标记
最小生成树找到,总权值为17
在这里插入图片描述

C语言Prim算法实现

#include<stdio.h>
#define M 1000//M表示无穷用1000代替
//判断标记点的函数,避免产生回路
int Is(int arr[9], int flag)
{int i = 0;for (i = 0; i < 9; i++){if (arr[i] == flag)return 0;}return 1;
}
int main()
{//把上图权值对应值写成邻接阵int map[9][9] ={{M,6,3,1,M,M,M,M,M},{6,M,2,M,M,M,M,M,1},{3,2,M,2,M,M,M,M,M},{1,M,2,M,10,M,M,M,M},{M,M,M,10,M,2,M,M,6},{M,M,M,M,2,M,4,M,4},{M,M,M,M,M,4,M,3,3},{M,M,M,M,M,M,3,M,2},{M,1,M,M,6,4,3,2,M}};//存放被标记的点int arr[9] = { 1 };//设置初始点为V1,只有V1被标记//记录标记个数int count = 1;//存放权值总和int s = 0;//循环变量int i = 0;//记录最小权下标int index = 0;//记录最小权int min = M;//记录点int doc = 1;//循环部分:while (1){min = M;for (i = 0; i < count; i++){int j = 0;int c = arr[i] - 1;for (j = 0; j < 9; j++){if (map[c][j] <= min && Is(arr, j + 1)){doc = c + 1;min = map[c][j];index = j;}}}s += min;arr[count++] = index + 1;//打印printf("V%d --> V%d ", doc, index + 1);//所有点被标记,跳出循环if (count == 9)break;}printf("\n总权值为:%d\n", s);return 0;
}

运行结果:

在这里插入图片描述

2、用Prim-Alternate算法求最小生成树

Prim-Alternate算法是Prim算法的优化
Prim-Alternate算法是只找当前标记点和上一个标记点的邻边
被标记的点不能互相相连

3、C语言Prim-Alternate算法实现

//Prim-Alternate算法
#include<stdio.h>
#define M 1000//M表示无穷用1000代替
//判断标记点的函数,避免产生回路
int Is(int arr[9], int flag)
{int i = 0;for (i = 0; i < 9; i++){if (arr[i] == flag)return 0;}return 1;
}
int main()
{//把上图权值对应值写成邻接阵int map[9][9] ={{M,6,3,1,M,M,M,M,M},{6,M,2,M,M,M,M,M,1},{3,2,M,2,M,M,M,M,M},{1,M,2,M,10,M,M,M,M},{M,M,M,10,M,2,M,M,6},{M,M,M,M,2,M,4,M,4},{M,M,M,M,M,4,M,3,3},{M,M,M,M,M,M,3,M,2},{M,1,M,M,6,4,3,2,M}};//存放被标记的点int arr[9] = { 1 };//设置初始点为V1,V1被标记//记录标记个数int count = 1;//存放权值总和int s = 0;//循环变量int i = 0;//记录最小权下标int index = 0;//记录最小权int min = M;//记录点int doc = 1;int c = 0;//循环部分:while(1){min = M;
//每次循环只找两个标记点相邻的边for(i=count-2;i< count ;i++){ int j = 0;if (count == 1)c = arr[0] - 1;elsec = arr[i] - 1;for (j = 0; j < 9; j++){if (map[c][j] <= min && Is(arr, j + 1)){doc = c+1;min = map[c][j];index = j;}}}s += min;arr[count++] = index + 1;//打印printf("V%d --> V%d ",doc , index + 1);//所有点被标记,跳出循环if (count == 9)break;		}printf("\n总权值为:%d\n", s);return 0;
}

运行结果:

在这里插入图片描述

这篇关于C语言Prim算法和Prim-Alternat找最小生成树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1027370

相关文章

java中使用POI生成Excel并导出过程

《java中使用POI生成Excel并导出过程》:本文主要介绍java中使用POI生成Excel并导出过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录需求说明及实现方式需求完成通用代码版本1版本2结果展示type参数为atype参数为b总结注:本文章中代码均为

在java中如何将inputStream对象转换为File对象(不生成本地文件)

《在java中如何将inputStream对象转换为File对象(不生成本地文件)》:本文主要介绍在java中如何将inputStream对象转换为File对象(不生成本地文件),具有很好的参考价... 目录需求说明问题解决总结需求说明在后端中通过POI生成Excel文件流,将输出流(outputStre

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C语言中的数据类型强制转换

《C语言中的数据类型强制转换》:本文主要介绍C语言中的数据类型强制转换方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C语言数据类型强制转换自动转换强制转换类型总结C语言数据类型强制转换强制类型转换:是通过类型转换运算来实现的,主要的数据类型转换分为自动转换

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

C语言实现两个变量值交换的三种方式

《C语言实现两个变量值交换的三种方式》两个变量值的交换是编程中最常见的问题之一,以下将介绍三种变量的交换方式,其中第一种方式是最常用也是最实用的,后两种方式一般只在特殊限制下使用,需要的朋友可以参考下... 目录1.使用临时变量(推荐)2.相加和相减的方式(值较大时可能丢失数据)3.按位异或运算1.使用临时

使用C语言实现交换整数的奇数位和偶数位

《使用C语言实现交换整数的奇数位和偶数位》在C语言中,要交换一个整数的二进制位中的奇数位和偶数位,重点需要理解位操作,当我们谈论二进制位的奇数位和偶数位时,我们是指从右到左数的位置,本文给大家介绍了使... 目录一、问题描述二、解决思路三、函数实现四、宏实现五、总结一、问题描述使用C语言代码实现:将一个整

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Go语言中最便捷的http请求包resty的使用详解

《Go语言中最便捷的http请求包resty的使用详解》go语言虽然自身就有net/http包,但是说实话用起来没那么好用,resty包是go语言中一个非常受欢迎的http请求处理包,下面我们一起来学... 目录安装一、一个简单的get二、带查询参数三、设置请求头、body四、设置表单数据五、处理响应六、超