C语言-数据结构 无向图克鲁斯卡尔算法(Kruskal)邻接矩阵存储

        相比普里姆算法来说，克鲁斯卡尔的想法是从边出发，不管是理解上还是实现上都更简单，实现思路：我们先把找到所有边存到一个边集数组里面，并进行升序排序，然后依次从里面取出每一条边，如果不存在回路，就说明可以取，否则就跳过去看下一条边。其中看是否是回路这个操作利用到了并查集，就是判断新加入的这条边的两个顶点是否在同一个集合中，如果在就说明产生回路，如果没在同一个集合那么说明没有回路可以加入，这里只需要理解并查集中的查找、更新操作就行。并查集在上一篇博文里介绍过了，有需要的可以翻看，这里就不再具体介绍。

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

84ef03cba4ba478383b338ae5884012a.png

  最小生成树示意图：

a60130ea5837483ba260f2b8a0ffa856.png

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

9eefaa5c866742cbb239f5f9de2aff7d.png

边集数组使用上三角矩阵生成，因为是无向图只需要取上三角或下三角就可以得到全部的边：

e5b3d526855e411bba85ad9d534ae6ca.png

获取边集数组代码：

// 从图的邻接矩阵中提取边，并按权重排序
Edge* GetEdges(MGraph G) {// 动态分配内存存储边Edge* Edges = (Edge*)malloc(sizeof(Edge) * G.numEdges);if (Edges == NULL) {printf("内存分配失败\n");exit(1);}int edgeIndex = 0;// 遍历邻接矩阵提取边for (int i = 0; i < G.numNodes; i++) {for (int j = i + 1; j < G.numNodes; j++) { // 从 i + 1 开始，避免重复的边if (G.arc[i][j] != 99) { // 99 表示没有边Edges[edgeIndex].begin = i;Edges[edgeIndex].end = j;Edges[edgeIndex].weight = G.arc[i][j];edgeIndex++;}}}// 按边的权重排序（冒泡排序）for (int i = 0; i < G.numEdges - 1; i++) {for (int j = 0; j < G.numEdges - i - 1; j++) {if (Edges[j].weight > Edges[j + 1].weight) {// 交换边Edge tmpEdge = Edges[j];Edges[j] = Edges[j + 1];Edges[j + 1] = tmpEdge;}}}return Edges;
}

        Kruskal算法代码：

// 查找节点所在集合的根
int Find(int parent[], int f) {while (parent[f] > 0) {f = parent[f];}return f;
}// 使用 Kruskal 算法生成最小生成树
void MiniSpanTree_Kruskal(MGraph G, Edge Edges[]) {int i, n, m;Edge edges[MAXEDGE]; // 声明边数组（可能用于存储生成树的边）int parent[MAXVEX]; // 记录每个节点的父节点// 初始化每个节点的父节点为 0for (i = 0; i < G.numNodes; i++) {parent[i] = 0;}printf("\n");// 遍历每条边for (i = 0; i < G.numEdges; i++) {n = Find(parent, Edges[i].begin);m = Find(parent, Edges[i].end);if (n != m) {// 如果两个端点不在同一集合中，则将边加入最小生成树parent[n] = m;printf("第%d条边为:(%c,%c) %d\n", i + 1, Array[Edges[i].begin], Array[Edges[i].end], Edges[i].weight);}// 打印当前边处理后的 parent 数组printf("循环第%d条边后parent的值为：", i + 1);for (int j = 0; j < MAXVEX; j++) {printf("%d-", parent[j]);}printf("\n\n");}
}

完整代码（包含邻接矩阵的创建，边集的创建,Kruskal算法）

#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 MAXEDGE 10 /* 最大边数，用户定义 */
#define GRAPH_INFINITY 99 /* 用0表示∞，表示不存在边 *//* 定义状态、顶点和边的类型 */
typedef int Status;  /* Status是函数的返回类型，如OK表示成功 */
typedef char VertexType; /* 顶点的类型，用字符表示 */
typedef int EdgeType; /* 边上的权值类型，用整数表示 */
typedef int Boolean; /* 布尔类型 */
// 定义顶点标签
char Array[] = "ABCDEFGHI";
/* 访问标记数组 */
Boolean visited[MAXVEX];/* 图的邻接矩阵结构体 */
typedef struct
{VertexType vexs[MAXVEX]; /* 顶点表 */EdgeType arc[MAXVEX][MAXVEX]; /* 邻接矩阵，表示边的权值 */int numNodes, numEdges; /* 图中当前的顶点数和边数 */
} MGraph;/* 边集数组结构体,用于辅助克鲁斯卡尔算法 */
typedef struct {int begin;  // 边的起始顶点int end;    // 边的终止顶点int weight; // 边的权重
} Edge;/* 创建一个无向网图的邻接矩阵表示 */
void CreateMGraph(MGraph* G)
{int i, j, k, w;// 初始化图的顶点数和边数G->numNodes = 8;G->numEdges = 10;// 初始化邻接矩阵和顶点表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");}
}// 从图的邻接矩阵中提取边，并按权重排序
Edge* GetEdges(MGraph G) {// 动态分配内存存储边Edge* Edges = (Edge*)malloc(sizeof(Edge) * G.numEdges);if (Edges == NULL) {printf("内存分配失败\n");exit(1);}int edgeIndex = 0;// 遍历邻接矩阵提取边for (int i = 0; i < G.numNodes; i++) {for (int j = i + 1; j < G.numNodes; j++) { // 从 i + 1 开始，避免重复的边if (G.arc[i][j] != 99) { // 99 表示没有边Edges[edgeIndex].begin = i;Edges[edgeIndex].end = j;Edges[edgeIndex].weight = G.arc[i][j];edgeIndex++;}}}// 按边的权重排序（冒泡排序）for (int i = 0; i < G.numEdges - 1; i++) {for (int j = 0; j < G.numEdges - i - 1; j++) {if (Edges[j].weight > Edges[j + 1].weight) {// 交换边Edge tmpEdge = Edges[j];Edges[j] = Edges[j + 1];Edges[j + 1] = tmpEdge;}}}return Edges;
}// 打印边集数组
void EdgesPrint(Edge Edges[], int EdgeNumber) {// 打印标题行printf("\n\t边集数组\n");printf("\t  %-5s  %-5s %-7s\n", "begin", "end", "weight");// 打印每条边的详细信息for (int i = 0; i < EdgeNumber; i++) {printf("Edge[%d]   (%c)%-5d (%c)%-5d %-7d\n", i, Array[Edges[i].begin], Edges[i].begin, Array[Edges[i].end], Edges[i].end, Edges[i].weight);}
}// 查找节点所在集合的根
int Find(int parent[], int f) {while (parent[f] > 0) {f = parent[f];}return f;
}// 使用 Kruskal 算法生成最小生成树
void MiniSpanTree_Kruskal(MGraph G, Edge Edges[]) {int i, n, m;Edge edges[MAXEDGE]; // 声明边数组（可能用于存储生成树的边）int parent[MAXVEX]; // 记录每个节点的父节点// 初始化每个节点的父节点为 0for (i = 0; i < G.numNodes; i++) {parent[i] = 0;}printf("\n");// 遍历每条边for (i = 0; i < G.numEdges; i++) {n = Find(parent, Edges[i].begin);m = Find(parent, Edges[i].end);if (n != m) {// 如果两个端点不在同一集合中，则将边加入最小生成树parent[n] = m;printf("第%d条边为:(%c,%c) %d\n", i + 1, Array[Edges[i].begin], Array[Edges[i].end], Edges[i].weight);}// 打印当前边处理后的 parent 数组printf("循环第%d条边后parent的值为：", i + 1);for (int j = 0; j < MAXVEX; j++) {printf("%d-", parent[j]);}printf("\n\n");}
}int main(void)
{MGraph G;/* 创建图 */CreateMGraph(&G);//获取边集数组Edge * Edges =GetEdges(G);//打印边集数组EdgesPrint(Edges,G.numEdges);//使用克鲁斯卡尔算法MiniSpanTree_Kruskal(G, Edges);return 0;
}

运行结果（标黄色的就是没有加入最小生成树的边，即产生了回路）：

最小生成树示意图

a60130ea5837483ba260f2b8a0ffa856.png

8cdc61d98e2847d2b2f79ac6a7cfb6cb.png

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/421575.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

99.游戏安全项目-可见数据的搜索与技巧

99.游戏安全项目-可见数据的搜索与技巧

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 内容参考于&#xff1a;易道云信息技术研究院 上一个内容&#xff1a;98.游戏的启动与多开-分析与实现多开器 下图中红框位置显示的数据&#xff0c;只有下图…
阅读更多...
横版闯关手游【全明星时空阿拉德】Linux手工服务端+运营后台+双app端

横版闯关手游【全明星时空阿拉德】Linux手工服务端+运营后台+双app端

横版闯关手游【时空阿拉德】&#xff08;【全明星阿拉德】&#xff09;阿拉德系列2022整理Linux手工服务端余额充值后台安卓苹果双端。 运营后台看目录结构是thinkphp开发的。 代码免费下载&#xff1a;百度网盘
阅读更多...
再识Clip

再识Clip

来源 CLIP损失函数的理解-CSDN博客 Simple Implementation of OpenAI CLIP model: A Tutorial | Towards Data Science 【小白】一文读懂CLIP图文多模态模型_clip模型-CSDN博客 从 CLIP 聊聊多模态自监督学习新范式 - 知乎 (zhihu.com) CLIP 论文逐段精读【论文精读】_哔哩…
阅读更多...
BC173 牛牛逆序输出（c 语言）

BC173 牛牛逆序输出（c 语言）

1.// 描述 //牛牛在尝试把一个整数逆序地输出。 //输入描述&#xff1a; //输入一个正整数 n。保证个位数不是 0 //输出描述&#xff1a; //逆序输出这个正整数。 //2345 //5432 2.我们先输入n,然后我们进行取余&#xff0c;然后将余数存储起来在arr中&#xff0c;然后除10。…
阅读更多...
串口接收不到数据之电阻虚焊bug分析思路

串口接收不到数据之电阻虚焊bug分析思路

单片机和EC移远通信模块进行通信&#xff0c;相同的代码运行在相同的硬件上&#xff0c;但是一个能联网&#xff0c;一个因为没有EC的应答连不上网。 开始分析&#xff0c;排除软件问题&#xff0c;给EC模块发为什么没应答&#xff1f; 1.发送失败 2.接收失败 排除情况2&#x…
阅读更多...
redis底层—网络模型

redis底层—网络模型

1.用户空间和内核空间 2.阻塞IO 3.非阻塞IO 4.IO多路复用 select模式的三个问题&#xff1a; 能监听的FD最大不超过1024 每次select都需要把所有要监听的FD都拷贝到内核空间 每次都要遍历所有FD来判断就绪状态 poll模式的问题&#xff1a; poll利用链表解决了select中监听FD上限…
阅读更多...
基于RFID技术的光交箱哑资源智能化管理方案

基于RFID技术的光交箱哑资源智能化管理方案

一、现状 &#xff08;一&#xff09;现状与挑战 在当前通信网络基础设施中&#xff0c;哑资源如光缆接头、跳线等在网络中占据着重要地位。然而&#xff0c;传统的哑资源管理方式存在诸多问题&#xff0c;一方面&#xff0c;管理主要依赖人工记录和定期巡检&#xff0c;效率…
阅读更多...
活动｜华院计算宣晓华受邀出席“AI引领新工业革命”大会，探讨全球科技的最新趋势

活动｜华院计算宣晓华受邀出席“AI引领新工业革命”大会，探讨全球科技的最新趋势

8月31日&#xff0c;“AI引领新工业革命”大会于上海图书馆圆满落幕。本次大会由TAA校联会和台协科创工委会联合主办&#xff0c;得到上海市台办、上海市台联、康师傅的大力支持。大会邀请了NVIDIA全球副总裁、亚太区企业营销负责人刘念宁&#xff0c;元禾厚望资本创始合伙人潘…
阅读更多...
【视频教程】GEE遥感云大数据在林业中的应用与典型案例实践

【视频教程】GEE遥感云大数据在林业中的应用与典型案例实践

近年来遥感技术得到了突飞猛进的发展&#xff0c;航天、航空、临近空间等多遥感平台不断增加&#xff0c;数据的空间、时间、光谱分辨率不断提高&#xff0c;数据量猛增&#xff0c;遥感数据已经越来越具有大数据特征。遥感大数据的出现为相关研究提供了前所未有的机遇&#xf…
阅读更多...
基于STM32C8T6的CubeMX：HAL库点亮LED

基于STM32C8T6的CubeMX：HAL库点亮LED

三个可能的问题和解决方法&#xff1a; 大家完成之后回来看&#xff0c;每一种改错误都是一种成长&#xff0c;不要畏惧&#xff0c;要快乐&#xff0c;积极面对&#xff0c;要耐心对待 STMCuBeMX新建项目的两种匪夷所思的问题https://mp.csdn.net/mp_blog/creation/editor/1…
阅读更多...
网络基础入门指南（三）

网络基础入门指南（三）

一、远程管理交换机 1.配置IP地址 远程管理需要通过IP地址访问网络设备交换机的接口&#xff0c;默认无法配置IP地址需要使用虚接口vlan1 2.配置远程登录密码 远程管理需要配置VTY接口VTY是虚拟终端&#xff0c;是一种网络设备远程连接的方式vty 0 4表示可同时打开5个会话 3…
阅读更多...
1.C++入门1（c++编译过程，命名空间，C++输入输出，缺省参数）

1.C++入门1（c++编译过程，命名空间，C++输入输出，缺省参数）

⭐从本章开始学习c&#xff0c;此篇文章作为c专栏的第一篇文章。 ⭐本人c代码的Gitee仓库&#xff1a;c学习 橘子真甜/yzc的c学习 - 码云 - 开源中国 (gitee.com) 目录 一.编程过程 二.命名空间&#xff08;namespace&#xff09; 2.1 为何要用命名空间 2.2 命名空间的定义…
阅读更多...
2024.9.11

2024.9.11

在界面上显示当前时间&#xff0c;再设置一个闹钟&#xff0c;到了时间就吱吱响&#xff08;至少5遍&#xff09; #include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget),speecher(new QTe…
阅读更多...
Fiddle的使用------一个非常好用且正规的抓包工具

Fiddle的使用------一个非常好用且正规的抓包工具

Fiddle的下载安装&#xff08;看完再去下载安装&#xff09; https://www.telerik.com/download/fiddler 1.点击连接&#xff0c;在表格填上数据&#xff0c;点击下载&#xff0c;下载结束了就安装&#xff0c;一路next就可以了。 2.修改一下设置 以上跟我一样设置&#xff…
阅读更多...
鼠标hover过渡动画（已验证）

鼠标hover过渡动画（已验证）

基于css中的grid方案实现的一个hover小动画&#xff0c;以下代码基于vue2&#xff0c;其他的可以直接复制html和css就可以&#xff0c;注意&#xff1a;以下代码在部分浏览器不兼容 注&#xff1a;部分代码来自我接入的GPT4o/Claude网站 <template><div class"h…
阅读更多...
全国各地身份证号开头6位数字及地区对照表

全国各地身份证号开头6位数字及地区对照表

具体请前往&#xff1a;全国各地身份证号开头6位数字-省市县/区对照表
阅读更多...
数据库中的主码、候选码、主属性、非主属性

数据库中的主码、候选码、主属性、非主属性

参考链接 候选码、主码、全码、外码、主属性、主键、主关键字、非主属性清晰总结 - 知乎 (zhihu.com) 1.码&#xff1a; 能够标识一条记录的属性或者属性集 2.候选码 能够标识一条记录的最小属性集 任一候选键的任何真子集都不能唯一标识一个记录&#xff08;比如在成绩表…
阅读更多...
用Python爬虫制作一个简易翻译器

用Python爬虫制作一个简易翻译器

我们通常是通过requestsBS4的方法来获取网页内容&#xff0c;这种方法导入模块较多&#xff0c;速度相对有点儿慢&#xff0c;此时我们可以用requests的post方法向指定服务器发送请求&#xff0c;获取数据后格式化为json&#xff0c;然后获取相关键值。这种方法用到了requests和…
阅读更多...
shell学习3---for循环

shell学习3---for循环

for循环格式 基本格式 for 变量名称(注意是名称不是变量$等) [ in 名称范围 ] (可以不写) do 执行内容 &#xff08;若满足循环则做什么动作&#xff09; done &#xff08;for循环结束标志&#xff09; 名称范围是字符 [rootserver1 ~]# ./for…
阅读更多...
google vr 入门之VrPanoramaView制作全景图列表(1)

google vr 入门之VrPanoramaView制作全景图列表(1)

展示图片的列表我这里使用RecycleView&#xff0c;activity_main.xml <?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android“http://schemas.android.com/apk/res/android” xmlns:tools“http://schemas.android.com/tool…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023