管道铺设系统-最小生成树（Prim、Kruskal算法实现）

2023-10-22 09:59
文章标签 算法 实现 系统 最小 生成 管道 prim kruskal 铺设

本文主要是介绍管道铺设系统-最小生成树（Prim、Kruskal算法实现），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

管道铺设系统-最小生成树（Prim、Kruskal算法实现）

问题

开发一个管线铺设辅助系统，以我校东校区为例，在东校区大学生活动中心、学生公寓、学生食堂、21层主楼、第一、二、三、四教学楼、原图书馆、机械馆、原信息馆、人文馆、体育馆之间铺设输水管道，设计算法并实现使铺设的输水管道距离最短。系统要求具备从文本读取数据、显示最佳铺设方案，以及绘制最佳方案的简单示意图等功能。

功能需求

1）将管线经过的建筑物以及建筑物之间的距离，抽象成无向图，并以矩阵的形式表示，并保存在文本中，系统通过读取文本的方式，获取该矩阵;
2）从Prim算法和Kruskal算法中至少选择一种实现管线铺设的最优方案，系统可以最优方案的生成过程，并且可以文本的形式输出;
3)在系统上可以生成最优方案的简易图。

功能实现

Prim算法
（1）基本思想：
设N=(V,E)是最小连通网，TE是N上最小生成树中边的集合，初始令U={u0}（u0∈V),TE={}。
在所有u∈U,v∈V-U的边（u，v）∈E中，找一条代价最小的边（u0,v0),将边（u0,v0）并入集合TE，同时v0并入U。
重复上述操作，直到U=V为止，则T=(V,TE)为N的最小生成树。
（2）代码展示：
①定义顶点数据类型。由于我们需要绘制出最小生成树的动态过程，所以需要记录顶点的坐标。顶点数据类型为我们定义的结构体类型，它包括三个信息，即x坐标，y坐标和顶点名称。

//点 
typedef struct
{char data;int x;int y;
}VerTex;

②定义图的信息。图的信息包括点集、邻接矩阵、点的个数和边的个数。

typedef struct
{VerTex vexs[MVNum];int arcs[MVNum][MVNum];int vexnum, arcnum;
}AMGraph;

③定义候选最短边集数组closeEdge[n],数组元素包括 adjvex 和 lowcost两个域，分别表示候选最短边的邻接点和权值。

// 定义记录从顶点集U到V-U代价最小的边的数组
typedef struct {char adjvex; // 候选最短边邻接点 int lowcost; // 候选最短边权值 
}arr;
arr closedge[MVNum];

(3)运行结果
①选择Prim起点，生成最小生成树
在这里插入图片描述
②动态过程展示
在这里插入图片描述
③保存在文本文档中
在这里插入图片描述
Kruska算法
(1)运行结果
①依次按下回车键，构建最小生成树
在这里插入图片描述
②动态过程展示
在这里插入图片描述

③保存在文本文档中
在这里插入图片描述

参考资料

[1] https://www.bilibili.com/video/BV1yp4y1Q74o?share_source=copy_web
[2] http://t.csdn.cn/4jtnv
[3] http://t.csdn.cn/qXRBx
[4]https://jingyan.baidu.com/article/b2c186c8c86d7c856ef6fffd.html

附：
读取的文本：

13 78
A 220 750
B 30 680
C 150 710
D 230 480
E 370 500
F 460 380
G 270 620
H 360 170
I 300 530
J 310 410
K 280 230
L 350 100
M 415 30
0 255 80 380 410 550 260 865 350 440 775 980 1100
255 0 160 370 450 590 310 840 380 470 730 930 1000
80 160 0 330 380 530 230 820 320 410 720 920 1000
380 370 330 0 100 230 130 490 60 110 390 580 680
410 450 380 100 0 150 150 470 70 40 380 560 650
550 590 530 230 150 0 300 350 220 130 310 450 530
260 310 230 130 150 300 0 610 110 185 550 715 810
865 840 820 490 470 350 610 0 500 420 160 125 210
350 380 320 60 70 220 110 500 0 80 440 600 705
440 470 410 110 40 130 185 420 80 0 370 525 625
775 730 720 390 380 310 550 160 440 370 0 190 300
980 930 920 580 560 450 715 125 600 525 190 0 105
1100 1000 1000 680 650 530 810 210 705 625 300 105 0

程序源码：
（1）Prim

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<graphics.h> 
#include<conio.h>
#include<wchar.h>
#include<fstream>
using namespace std;
#define MaxInt 32767
#define MVNum 100
int sum = 0;//点 
typedef struct
{char data;int x;int y;
}VerTex;typedef struct
{VerTex vexs[MVNum];int arcs[MVNum][MVNum];int vexnum, arcnum;
}AMGraph;// 定义记录从顶点集U到V-U代价最小的边的数组
typedef struct {char adjvex; // 候选最短边邻接点 int lowcost; // 候选最短边权值 
}arr;
arr closedge[MVNum];//确定顶点在G中的位置
int LocateVex(AMGraph G, char v)
{for (int i = 0; i < G.vexnum; ++i){if (G.vexs[i].data == v){return i;}}return -1;
}
//采用邻接矩阵表示法，创建无向网G
//int CreateUDN(AMGraph& G)
//{
//    int w;
//    char v1, v2;
//    //for (int i = 0; i < G.vexnum; ++i)
//    //    for (int j = 0; j < G.vexnum; ++j)
//    //    {
//    //        G.arcs[i][j] = MaxInt;
//    //    }
//    //ReadFromTxt(G);
//    //for (int k = 0; k < G.arcnum; ++k)
//    //{
//    //    int i, j;
//    //    cout << "请输入第" << k + 1 << "条边依附的顶点及权值：";
//    //    cin >> v1 >> v2 >> w;
//    //    i = LocateVex(G, v1);
//    //    j = LocateVex(G, v2);
//    //    G.arcs[i][j] = w;
//    //    G.arcs[j][i] = G.arcs[i][j];
//    //}
//    return 1;
//}//从txt文件中读取邻接矩阵
void ReadFromTxt(AMGraph& G) {ifstream fin;fin.open("E:\\distance.txt", ios::in);if (!fin.is_open()) {cout << "文件打开失败" << endl;exit(1);}while (!fin.eof()) {fin >> G.vexnum >> G.arcnum;for (int i = 0; i < G.vexnum; i++) {fin >> G.vexs[i].data >> G.vexs[i].x >> G.vexs[i].y;}for (int i = 0; i < G.vexnum; i++) {for (int j = 0; j < G.vexnum; j++) {fin >> G.arcs[i][j];}}fin.close();}
}void SaveToTxt(char A, int B, char p) {ofstream fout("result_prim.txt",ofstream::app);if (fout.is_open()) {fout << "(" << A << "," << p << ")" << B << endl;}fout.close();
}void MinSpanTree_PRIM(AMGraph G, char u) {// 用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边int k;k = LocateVex(G, u);//画点 setfillcolor(RGB(0, 0, 255));int radio = 22; // 圆的半径 fillcircle(G.vexs[k].x, G.vexs[k].y, radio);outtextxy(G.vexs[k].x - 5, G.vexs[k].y - 5, G.vexs[k].data);_getch();// 初始化辅助数组for (int j = 0; j < G.vexnum; ++j){closedge[j].lowcost = G.arcs[k][j];closedge[j].adjvex = u;}closedge[k].lowcost = 0;  //初始，U={u}int x1, x2, y1, y2;//画点线 int m;for (int i = 1; i < G.vexnum; ++i){// 寻找最短边的邻接点int min = MaxInt;for (int n = 0; n < G.vexnum; ++n){if (closedge[n].lowcost < min && closedge[n].lowcost != 0){min = closedge[n].lowcost;k = n;}}//画点 setfillcolor(RGB(0, 0, 255));int radio = 22; // 圆的半径 fillcircle(G.vexs[k].x, G.vexs[k].y, radio);outtextxy(G.vexs[k].x - 5, G.vexs[k].y - 5, G.vexs[k].data);_getch();char p;p = G.vexs[k].data;// 输出最小生成树路径cout << "(" << closedge[k].adjvex << "," << p << ")" << closedge[k].lowcost << endl;//char A = closedge[k].adjvex;//int B = closedge[k].lowcost;SaveToTxt(closedge[k].adjvex, closedge[k].lowcost, p);sum = sum + closedge[k].lowcost;m = LocateVex(G, closedge[k].adjvex);x1 = G.vexs[m].x;y1 = G.vexs[m].y;x2 = G.vexs[k].x;y2 = G.vexs[k].y;// cout << p << endl;char str[100];line(x1, y1, x2, y2);sprintf(str, "%d", closedge[k].lowcost); //转换成字符outtextxy((x1 + x2 - 10) / 2, (y1 + y2 - 20) / 2, str); //放权值 _getch();//第k顶点并入U集closedge[k].lowcost = 0;// 调整数组closedgefor (int j = 0; j < G.vexnum; ++j){if (G.arcs[k][j] < closedge[j].lowcost){closedge[j].lowcost = G.arcs[k][j];closedge[j].adjvex = p;}}}
}int main()
{initgraph(757, 881, SHOWCONSOLE);int i, j;char p;AMGraph G;ReadFromTxt(G);
//    CreateUDN(G);
//    for (int i = 0; i < G.vexnum; i++) {
//        cout << G.vexs[i].data << endl;
//    }
//    for (i = 0; i < G.vexnum; ++i)
//    {
//        for (j = 0; j < G.vexnum; ++j)
//        {
//            if (G.arcs[i][j] != MaxInt)
//                cout << G.arcs[i][j] << "\t";
//            else
//                cout << "0" << "\t";
//        }
//        cout << endl;
//    }
//    cout << endl;cout << "请输入管道铺设的起点(Prim算法)的起点:" << endl;cin >> p;cout << "输出从" << p << "开始的管道铺设过程如下:" << endl;MinSpanTree_PRIM(G, p);cout<<"管道铺设最短路径为："<<sum; system("pause");closegraph();return 0;
}

(2) Kruskal

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<string>
#include<graphics.h> 
#include<conio.h>
#include<wchar.h>
#include<fstream>
using namespace std;
#define MVNum 100
int sum = 0; //记录最小生成树总权值 
//边
typedef struct edge_set {char vex1; //边的其中一个顶点char vex2; //边的另一个顶点int weight; //边的权重
}Edge;//点 
typedef struct
{char data;int x;int y;
}VerTex;typedef struct
{VerTex vexs[MVNum];Edge edge[MVNum];int arcs[MVNum][MVNum];int vexnum, arcnum;
}Graph;//确定顶点在G中的位置
int locate_vex(Graph G, char v)
{for (int i = 0; i < G.vexnum; ++i){if (G.vexs[i].data == v){return i;}}return -1;
}//从txt文件中读取邻接矩阵
void ReadFromTxt(Graph& G) {ifstream fin;fin.open("E:\\distance.txt", ios::in);if (!fin.is_open()) {cout << "文件打开失败" << endl;exit(1);}int k=0;while (!fin.eof()) {fin >> G.vexnum >> G.arcnum;for (int i = 0; i < G.vexnum; i++) {fin >> G.vexs[i].data >> G.vexs[i].x >> G.vexs[i].y;}//for (int i = 0; i < 13; i++) {//	for (int j = i+1; j < 13; j++) {//		char a = G.vexs[i].data;//		char b = G.vexs[j].data;//		G.edge[k].vex1 = a;//		G.edge[k].vex2 = b;//		fin >> G.edge[k].weight;//		cout<< G.edge[k].weight<<endl;//		k++;//	}//}for (int i = 0; i < G.vexnum; i++) {for (int j = 0; j < G.vexnum; j++) {fin >> G.arcs[i][j];}}fin.close();}
}void SaveToTxt(char A, int B, char p) {ofstream fout("result_kruskal.txt", ofstream::app);if (fout.is_open()) {fout << "(" << A << "," << p << ")" << B << endl;}fout.close();
}//创建一个图，图的信息使用边集来存储
int create_graph(Graph& G) {//cout << "请输入图的总顶点数及边数：" << endl;//cin >> G.vexnum >> G.arcnum;//cout << "请依次输入各顶点的信息：" << endl;int k = 0;for (int i = 0; i < G.vexnum; i++) {for (int j = i+1; j < G.vexnum; j++) {char a = G.vexs[i].data;char b = G.vexs[j].data;G.edge[k].vex1 = a;G.edge[k].vex2 = b;G.edge[k].weight = G.arcs[i][j];k++;}}//  画点 setfillcolor(RGB(0, 0, 255));int radio = 22;for (int i = 0; i < G.vexnum; ++i){//cout << "请输入第" << i + 1 << "个顶点：";//cin >> G.vexs[i].data;//cout << "请输入第" << i + 1 << "个顶点的x坐标：";//cin >> G.vexs[i].x;//cout << "请输入第" << i + 1 << "个顶点的y坐标：";//cin >> G.vexs[i].y;fillcircle(G.vexs[i].x, G.vexs[i].y, radio);outtextxy(G.vexs[i].x - 5, G.vexs[i].y - 5, G.vexs[i].data);}//cout << "请输入各条边依附的顶点及权值：" << endl;//for (int k = 0; k < G.arcnum; ++k)//{//	int i, j;//	cout << "请输入第" << k + 1 << "条边依附的顶点及权值：";//	cin >> G.edge[k].vex1 >> G.edge[k].vex2 >> G.edge[k].weight;//}return 1;
}//排序，按权重从小到大顺序排
int cmp(const void* a, const void* b) {return ((Edge*)a)->weight - ((Edge*)b)->weight;
}//找树的根
int find_root(int* parent, int t) {while (parent[t] > -1){t = parent[t]; //求顶点t上的双亲直到根结点 }return t;
}//kruskal算法实现
void kruskal(Graph G) {//将边按从小到大顺序排序qsort(G.edge, G.arcnum, sizeof(Edge), cmp);int parent[MVNum]; //判断新添加的线是否能和原来的图构成回路 // 初始化parent数组 for (int i = 0; i < G.vexnum; i++) {parent[i] = -1;}int num = 0, vex1 = -1, vex2 = -1;int p, q;int x1, y1, x2, y2;setlinecolor(RGB(0, 125, 255));for (int i = 0; i < G.arcnum; i++){// cout << G.edge[i].weight << endl;p = locate_vex(G, G.edge[i].vex1);q = locate_vex(G, G.edge[i].vex2);vex1 = find_root(parent, p);vex2 = find_root(parent, q);//cout << vex1 << endl;//cout << vex2 << endl;if (vex1 != vex2) //说明没在同一个连通分量中 {_getch();cout << "(" << G.edge[i].vex1 << "," << G.edge[i].vex2 << ")" << G.edge[i].weight << endl;SaveToTxt(G.edge[i].vex1,G.edge[i].weight,G.edge[i].vex2);sum = sum + G.edge[i].weight;parent[vex2] = vex1;//合并生成树 // 连线 x1 = G.vexs[p].x;y1 = G.vexs[p].y;x2 = G.vexs[q].x;y2 = G.vexs[q].y;char str[100];line(x1, y1, x2, y2);sprintf(str, "%d", G.edge[i].weight); //转换成字符outtextxy((x1 + x2 - 10) / 2, (y1 + y2 - 20) / 2, str); //放权值 num++;}if (num == G.vexnum - 1){Sleep(10000);return;}}
}int main() {initgraph(640, 1280, SHOWCONSOLE);Graph G;ReadFromTxt(G);create_graph(G);//for (int i = 0; i < 13; i++) {//	for (int j = 0; j < 13; j++) {//		cout << G.arcs[i][j];//		cout << " ";//	}//	cout << endl;//}
//	for (int i = 0; i < G.arcnum; i++) {
//		cout <<G.edge[i].vex1 << G.edge[i].vex2 << G.edge[i].weight<< endl;
//	}cout<<"管道铺设过程（kruskal）如下："<<endl;kruskal(G);cout<<"管道铺设路径最短为："<<sum;closegraph();return 0;
}

这篇关于管道铺设系统-最小生成树（Prim、Kruskal算法实现）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

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

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

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

基于人工智能的图像分类系统

目录 引言项目背景环境准备 硬件要求软件安装与配置系统设计 系统架构关键技术代码示例 数据预处理模型训练模型预测应用场景结论 1. 引言 图像分类是计算机视觉中的一个重要任务，目标是自动识别图像中的对象类别。通过卷积神经网络（CNN）等深度学习技术，我们可以构建高效的图像分类系统，广泛应用于自动驾驶、医疗影像诊断、监控分析等领域。本文将介绍如何构建一个基于人工智能的图像分类系统，包括环境
阅读更多...
水位雨量在线监测系统概述及应用介绍

水位雨量在线监测系统概述及应用介绍

在当今社会，随着科技的飞速发展，各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中，水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术，其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成，形成了一个完整的闭环系统。 数据采集单元：这是系统的“眼睛”，
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（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]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
AI一键生成 PPT

AI一键生成 PPT

AI一键生成 PPT 操作步骤 作为一名打工人，是不是经常需要制作各种PPT来分享我的生活和想法。但是，你们知道，有时候灵感来了，时间却不够用了！😩直到我发现了Kimi AI——一个能够自动生成PPT的神奇助手！🌟 什么是Kimi？ 一款月之暗面科技有限公司开发的AI办公工具，帮助用户快速生成高质量的演示文稿。 无论你是职场人士、学生还是教师，Kimi都能够为你的办公文
阅读更多...
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. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
嵌入式QT开发：构建高效智能的嵌入式系统

嵌入式QT开发：构建高效智能的嵌入式系统

摘要： 本文深入探讨了嵌入式 QT 相关的各个方面。从 QT 框架的基础架构和核心概念出发，详细阐述了其在嵌入式环境中的优势与特点。文中分析了嵌入式 QT 的开发环境搭建过程，包括交叉编译工具链的配置等关键步骤。进一步探讨了嵌入式 QT 的界面设计与开发，涵盖了从基本控件的使用到复杂界面布局的构建。同时也深入研究了信号与槽机制在嵌入式系统中的应用，以及嵌入式 QT 与硬件设备的交互，包括输入输出设
阅读更多...
JAVA智听未来一站式有声阅读平台听书系统小程序源码

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来，一站式有声阅读平台听书系统 🌟&nbsp;开篇：遇见未来，从“智听”开始 在这个快节奏的时代，你是否渴望在忙碌的间隙，找到一片属于自己的宁静角落？是否梦想着能随时随地，沉浸在知识的海洋，或是故事的奇幻世界里？今天，就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统，它正悄悄改变着我们的阅读方式，让未来触手可及！ 📚&nbsp;第一站：海量资源，应有尽有 走进“智听
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2