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

2024-09-08 05:20
文章标签 算法 语言 数据结构 存储 邻接矩阵 kruskal 卡尔 克鲁斯

本文主要是介绍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

 

这篇关于C语言-数据结构 克鲁斯卡尔算法(Kruskal)邻接矩阵存储的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1147231。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
异构存储（冷热数据分离）

异构存储（冷热数据分离）

异构存储主要解决不同的数据，存储在不同类型的硬盘中，达到最佳性能的问题。 异构存储Shell操作 （1）查看当前有哪些存储策略可以用 [lytfly@hadoop102 hadoop-3.1.4]$ hdfs storagepolicies -listPolicies （2）为指定路径（数据存储目录）设置指定的存储策略 hdfs storagepolicies -setStoragePo
阅读更多...
HDFS—存储优化（纠删码）

HDFS—存储优化（纠删码）

纠删码原理 HDFS 默认情况下，一个文件有3个副本，这样提高了数据的可靠性，但也带来了2倍的冗余开销。 Hadoop3.x 引入了纠删码，采用计算的方式，可以节省约50％左右的存储空间。 此种方式节约了空间，但是会增加 cpu 的计算。 纠删码策略是给具体一个路径设置。所有往此路径下存储的文件，都会执行此策略。 默认只开启对 RS-6-3-1024k
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
科研绘图系列：R语言扩展物种堆积图（Extended Stacked Barplot）

科研绘图系列：R语言扩展物种堆积图（Extended Stacked Barplot）

介绍 R语言的扩展物种堆积图是一种数据可视化工具，它不仅展示了物种的堆积结果，还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异，为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl
阅读更多...
透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

引言 随着时间的发展，大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用，随着人们期望的不断增加，目标也发生了巨大的变化。在短短的几个月的时间里，人们对大模型的认识已经从对其zero-shot能力感到惊讶，转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构（例如Transformer）对海量的、多种多样的数据分布进行建模得到，它包含了大量的先验
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2