【数据结构】最小生成树(Prim算法、Kruskal算法)解析+完整代码

2024-04-28 22:44

本文主要是介绍【数据结构】最小生成树(Prim算法、Kruskal算法)解析+完整代码,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

5.1 最小生成树

  • 定义

    对一个带权连通无向图 G = ( V , E ) G=(V,E) G=(V,E),生成树不同,每棵树的权(即树中所有边上的权值之和)也可能不同。

    设R为G的所有生成树的集合,若T为R中边的权值之和最小的生成树,则T称为G的最小生成树(MST)。

  • 性质

    1.最小生成树可能有多个,但边的权值之和总是唯一且最小的;

    2.最小生成树的边数=顶点数-1。砍掉一条则不连通,增加一条会出现回路;

    3.如果一个连通图本身就是一棵树,则其最小生成树就是它本身;

    4.只有连通图才有最小生成树,非连通图只有生成森林。

5.1.1 Prim算法
  • 定义

    从某一个顶点开始构建生成树;

    每次将代价最小的新顶点纳入生成树,直到所有顶点都纳入为止。

    在这里插入图片描述

    • 即选最小权值的结点
  • 时间复杂度

    O ( ∣ V ∣ 2 ) O(|V|^2) O(V2),适用于稠密图(|E|大的)。

  • 算法的实现思想

    • 思路:

      V 0 V_0 V0开始,总共需要n-1轮处理。

      第一轮处理:循环遍历所有个结点,找到lowCast最低的,且还没加入树的顶点。

      再次循环遍历,更新还没加入的各个顶点的lowCast值。

    • 代码步骤:

      1.创建isJoin数组,初始为false,判断结点是否加入树。

      2.创建lowCost数组,用于存储到该结点的最短距离。

      3.从 v 0 v_0 v0开始,将与其连接的权值加入到lowCost数组中。

      4.遍历lowCast数组,找到最小值,将其加入树中,并继续遍历与其相连的边。

5.1.2 Kruskal算法
  • 定义

    每次选则一条权值最小的边,使这条边的两头连通(原本已经连通的不选),直到所有结点都连通。

    • 即每次选最小的边
  • 时间复杂度

    O ( ∣ E ∣ l o g 2 ∣ E ∣ ) O(|E|log_2|E|) O(Elog2E),适用于边稀疏图。

  • 算法的实现思想

    • 思路:

      初始:将各条边按权值排序。

      共执行e轮,每轮判断两个顶点是否属于同一集合,需要 O ( l o g 2 e ) O(log_2e) O(log2e)

5.1.3 最小生成树代码
A.邻接矩阵
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>#define V 5 // 图的顶点数// 找到距离集合最近的顶点
int min_key(int key[], bool mst_set[]) {int min = INT_MAX, min_index;for (int v = 0; v < V; v++) {if (mst_set[v] == false && key[v] < min) {min = key[v];min_index = v;}}return min_index;
}// 打印最小生成树
void print_mst(int parent[], int graph[V][V]) {printf("Edge   Weight\n");for (int i = 1; i < V; i++)printf("%d - %d    %d \n", parent[i], i, graph[i][parent[i]]);
}// Prim算法
void prim_mst(int graph[V][V]) {int parent[V]; // 存放最小生成树的父节点int lowCost[V];    // 用于存放顶点到最小生成树的最小权重bool isJoin[V]; // 记录顶点是否已经加入最小生成树for (int i = 0; i < V; i++) {lowCost[i] = INT_MAX;isJoin[i] = false;}lowCost[0] = 0; // 初始点为0parent[0] = -1; // 根节点没有父节点for (int count = 0; count < V - 1; count++) {int u = min_key(lowCost, isJoin);isJoin[u] = true;for (int v = 0; v < V; v++) {if (graph[u][v] && !isJoin[v] && graph[u][v] < lowCost[v]) {parent[v] = u;lowCost[v] = graph[u][v];}}}print_mst(parent, graph);
}// Kruskal算法// 结构体用于表示边
struct Edge {int src, dest, weight;
};// 比较函数,用于排序
int compare(const void* a, const void* b) {return ((struct Edge*)a)->weight - ((struct Edge*)b)->weight;
}// 查找函数,用于查找集合的根节点
int find(int parent[], int i) {if (parent[i] == -1)return i;return find(parent, parent[i]);
}// 合并函数,用于合并两个集合
void Union(int parent[], int x, int y) {int xset = find(parent, x);int yset = find(parent, y);parent[xset] = yset;
}// Kruskal算法
void kruskal_mst(int graph[V][V]) {struct Edge result[V]; // 用于存放最小生成树的边int e = 0; // 表示result数组中的边数int i = 0; // 表示当前考虑的边// 边集合struct Edge edges[V*V];for (int u = 0; u < V; u++) {for (int v = u + 1; v < V; v++) {if (graph[u][v] != 0) {edges[e].src = u;edges[e].dest = v;edges[e].weight = graph[u][v];e++;}}}// 根据权重对边进行排序qsort(edges, e, sizeof(edges[0]), compare);int parent[V]; // 用于记录每个顶点的父节点for (int v = 0; v < V; v++)parent[v] = -1;// 最小生成树的边数小于V-1时继续while (i < V - 1 && e > 0) {struct Edge next_edge = edges[--e];// 检查是否会产生环int x = find(parent, next_edge.src);int y = find(parent, next_edge.dest);if (x != y) {result[i++] = next_edge;Union(parent, x, y);}}printf("Edge   Weight\n");for (int i = 0; i < V - 1; i++)printf("%d - %d    %d \n", result[i].src, result[i].dest, result[i].weight);
}// 测试主函数
int main() {int graph[V][V] = {{0, 2, 0, 6, 0},{2, 0, 3, 8, 5},{0, 3, 0, 0, 7},{6, 8, 0, 0, 9},{0, 5, 7, 9, 0}};printf("Prim's Minimum Spanning Tree:\n");prim_mst(graph);printf("\nKruskal's Minimum Spanning Tree:\n");kruskal_mst(graph);return 0;
}

在这里插入图片描述

B.邻接表
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>#define MaxVertexNum 100
#define INF 9999typedef struct ArcNode {int adjvex;int weight;struct ArcNode *next;
} ArcNode;typedef struct VNode {int data;ArcNode *first;
} VNode, AdjList[MaxVertexNum];typedef struct {AdjList vertices;int vexnum, arcnum;
} ALGraph;void InitALGraph(ALGraph *G, int vexnum, int arcnum) {G->vexnum = vexnum;G->arcnum = arcnum;for (int i = 0; i < vexnum; i++) {G->vertices[i].data = i;G->vertices[i].first = NULL;}
}void AddEdgeUndirectedALGraph(ALGraph *G, int v1, int v2, int weight) {ArcNode *arcNode1 = (ArcNode *)malloc(sizeof(ArcNode));arcNode1->adjvex = v2;arcNode1->weight = weight;arcNode1->next = G->vertices[v1].first;G->vertices[v1].first = arcNode1;ArcNode *arcNode2 = (ArcNode *)malloc(sizeof(ArcNode));arcNode2->adjvex = v1;arcNode2->weight = weight;arcNode2->next = G->vertices[v2].first;G->vertices[v2].first = arcNode2;
}void PrintALGraph(ALGraph G) {for (int i = 0; i < G.vexnum; i++) {printf("%d -> ", G.vertices[i].data);ArcNode *p = G.vertices[i].first;while (p != NULL) {printf("(%d, %d) ", p->adjvex, p->weight);p = p->next;}printf("\n");}
}// Prim算法
void Prim(ALGraph G) {int lowCost[G.vexnum], parent[G.vexnum];bool inMST[G.vexnum];for (int i = 0; i < G.vexnum; i++) {lowCost[i] = INF;parent[i] = -1;inMST[i] = false;}lowCost[0] = 0;for (int i = 0; i < G.vexnum - 1; i++) {int minIndex, minCost = INF;for (int j = 0; j < G.vexnum; j++) {if (!inMST[j] && lowCost[j] < minCost) {minCost = lowCost[j];minIndex = j;}}inMST[minIndex] = true;ArcNode *p = G.vertices[minIndex].first;while (p != NULL) {if (!inMST[p->adjvex] && p->weight < lowCost[p->adjvex]) {lowCost[p->adjvex] = p->weight;parent[p->adjvex] = minIndex;}p = p->next;}}printf("Edge   Weight\n");for (int i = 1; i < G.vexnum; i++) {printf("%d - %d    %d\n", parent[i], i, lowCost[i]);}
}// Kruskal算法
typedef struct {int src, dest, weight;
} Edge;int find(int parent[], int i) {if (parent[i] == -1)return i;return find(parent, parent[i]);
}void Union(int parent[], int x, int y) {int xset = find(parent, x);int yset = find(parent, y);parent[xset] = yset;
}int compare(const void *a, const void *b) {return ((Edge *)a)->weight - ((Edge *)b)->weight;
}void Kruskal(ALGraph G) {Edge result[G.arcnum];Edge edges[G.arcnum];int parent[G.vexnum];int e = 0;for (int i = 0; i < G.vexnum; i++) {ArcNode *p = G.vertices[i].first;while (p != NULL) {if (i < p->adjvex) {edges[e].src = i;edges[e].dest = p->adjvex;edges[e].weight = p->weight;e++;}p = p->next;}}qsort(edges, G.arcnum, sizeof(Edge), compare);for (int i = 0; i < G.vexnum; i++)parent[i] = -1;int i = 0, j = 0;while (i < G.vexnum - 1 && j < G.arcnum) {Edge next_edge = edges[j++];int x = find(parent, next_edge.src);int y = find(parent, next_edge.dest);if (x != y) {result[i++] = next_edge;Union(parent, x, y);}}printf("Edge   Weight\n");for (int i = 0; i < G.vexnum - 1; i++) {printf("%d - %d    %d\n", result[i].src, result[i].dest, result[i].weight);}
}int main() {ALGraph G;InitALGraph(&G, 5, 7);AddEdgeUndirectedALGraph(&G, 0, 1, 2);AddEdgeUndirectedALGraph(&G, 0, 3, 6);AddEdgeUndirectedALGraph(&G, 1, 2, 3);AddEdgeUndirectedALGraph(&G, 1, 3, 8);AddEdgeUndirectedALGraph(&G, 1, 4, 5);AddEdgeUndirectedALGraph(&G, 2, 4, 7);AddEdgeUndirectedALGraph(&G, 3, 4, 9);PrintALGraph(G);printf("Prim's Minimum Spanning Tree:\n");Prim(G);printf("\nKruskal's Minimum Spanning Tree:\n");Kruskal(G);return 0;
}

在这里插入图片描述

这篇关于【数据结构】最小生成树(Prim算法、Kruskal算法)解析+完整代码的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库,完全使用 Python 语言编写,它对 XPath表达式提供了良好的支 持,因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块,该模块专门用来解析 HTML/XML 文档,下面来介绍一下 lxml 库

大模型研发全揭秘:客服工单数据标注的完整攻略

在人工智能(AI)领域,数据标注是模型训练过程中至关重要的一步。无论你是新手还是有经验的从业者,掌握数据标注的技术细节和常见问题的解决方案都能为你的AI项目增添不少价值。在电信运营商的客服系统中,工单数据是客户问题和解决方案的重要记录。通过对这些工单数据进行有效标注,不仅能够帮助提升客服自动化系统的智能化水平,还能优化客户服务流程,提高客户满意度。本文将详细介绍如何在电信运营商客服工单的背景下进行

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

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

康拓展开(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]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

AI一键生成 PPT

AI一键生成 PPT 操作步骤 作为一名打工人,是不是经常需要制作各种PPT来分享我的生活和想法。但是,你们知道,有时候灵感来了,时间却不够用了!😩直到我发现了Kimi AI——一个能够自动生成PPT的神奇助手!🌟 什么是Kimi? 一款月之暗面科技有限公司开发的AI办公工具,帮助用户快速生成高质量的演示文稿。 无论你是职场人士、学生还是教师,Kimi都能够为你的办公文

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视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

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

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来