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

相关文章

IDEA自动生成注释模板的配置教程

《IDEA自动生成注释模板的配置教程》本文介绍了如何在IntelliJIDEA中配置类和方法的注释模板,包括自动生成项目名称、包名、日期和时间等内容,以及如何定制参数和返回值的注释格式,需要的朋友可以... 目录项目场景配置方法类注释模板定义类开头的注释步骤类注释效果方法注释模板定义方法开头的注释步骤方法注

Python如何自动生成环境依赖包requirements

《Python如何自动生成环境依赖包requirements》:本文主要介绍Python如何自动生成环境依赖包requirements问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录生成当前 python 环境 安装的所有依赖包1、命令2、常见问题只生成当前 项目 的所有依赖包1、

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL

Go 语言中的select语句详解及工作原理

《Go语言中的select语句详解及工作原理》在Go语言中,select语句是用于处理多个通道(channel)操作的一种控制结构,它类似于switch语句,本文给大家介绍Go语言中的select语... 目录Go 语言中的 select 是做什么的基本功能语法工作原理示例示例 1:监听多个通道示例 2:带

C语言函数递归实际应用举例详解

《C语言函数递归实际应用举例详解》程序调用自身的编程技巧称为递归,递归做为一种算法在程序设计语言中广泛应用,:本文主要介绍C语言函数递归实际应用举例的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录前言一、递归的概念与思想二、递归的限制条件 三、递归的实际应用举例(一)求 n 的阶乘(二)顺序打印

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

Java利用docx4j+Freemarker生成word文档

《Java利用docx4j+Freemarker生成word文档》这篇文章主要为大家详细介绍了Java如何利用docx4j+Freemarker生成word文档,文中的示例代码讲解详细,感兴趣的小伙伴... 目录技术方案maven依赖创建模板文件实现代码技术方案Java 1.8 + docx4j + Fr

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类(常规内部类)局部内部类(方法内部类)匿名内部类二、

使用Jackson进行JSON生成与解析的新手指南

《使用Jackson进行JSON生成与解析的新手指南》这篇文章主要为大家详细介绍了如何使用Jackson进行JSON生成与解析处理,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. 核心依赖2. 基础用法2.1 对象转 jsON(序列化)2.2 JSON 转对象(反序列化)3.