首页 > Python资料 博客日记
图--最小生成树(Prim&&Kruskal)
2024-08-17 09:00:10Python资料围观38次
本篇文章分享图--最小生成树(Prim&&Kruskal),对你有帮助的话记得收藏一下,看Python资料网收获更多编程知识
最小生成树的定义
图的生成树(Spanning Tree):如果无向连通图 G 的一个子图是一棵包含图 G 所有顶点的树,则称该子图为 G 的生成树。
一个连通图的生成树是指一个连通子图,它含有图中全部n个顶点,但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边,如果生成树中再添加一条边,则必定成环。
图的生成树不唯一。从不同的顶点出发进行遍历,可以得到不同的生成树。
最小生成树:在无向连通图的所有生成树中,所有边的代价和最小的生成树,称为最小生成树。
为了找到无向图的最小生成树,常用的算法有【Prim算法】和【Kruskal算法】。
Prim算法
Prim算法的思想是选择一个起始顶点,逐步选择与已经构建的树连接的最短边,直到包含所有的顶点为止。
实现步骤:
- 将图G 中所有的顶点V 分为两个顶点集合A 和 B。其中A 为已经加入到最小生成树的顶点集合,B 是还未加入生成树的顶点集合。
- 选择起始顶点start,将其加入到最小生成树的顶点集合A 中。
- 从A 的顶点集合中选择一个顶点 u,然后找到连接顶点 u 与B 之间的边中权重最小的边。
- 让上一步中找到的顶点和边加入到生成树的顶点集合MST 中,更新MST 的顶点集合和边集合。
- 重复第 3∼4步,直到 MST 的顶点集合中包含了图中的所有顶点为止。
选择A作为起始顶点,选择权值最小的边A->C,将C标记为已访问,然后从{A,C}中选择一条与未访问的节点集合{B,E,F,D}的权值最小的边C->F,重复以上,直到所有的顶点都已访问
#define MAXSIZE 100
struct tempVaria
{
int adjvex; //存放某一条边的起点值
int lowcost; //存放以i为终点的的边的最小的权值
};
void Prim(int v)//连接整个图的最小生成树
{
int sum=0;
struct tempVaria shortEdge[MAXSIZE];
for (int i = 0; i < vertexNum; i++) //初始化数组shortEdge
{
shortEdge[i].lowcost = arc[v][i]; //以v为起点,到其他节点的权值
shortEdge[i].adjvex = v; //将起点设置为v
}
shortEdge[v].lowcost = 0;
for(int i = 0; i < vertexNum ; i++)
{
if (v == i)
continue;
int min=inf;
int k = 0; //权值最小的边的顶点
int j = 0;
while (j< vertexNum)//寻找权值最小的边的下标
{
//节点未访问并且到该节点的权值小于min
if (shortEdge[j].lowcost != 0 && shortEdge[j].lowcost < min)
{
min = shortEdge[j].lowcost;
k = j;
}
j++;
}
shortEdge[k].lowcost = 0; //将顶点加入集合
sum += min;
for (j = 0; j < vertexNum; j++) //更新数组shortEdge
{
//更新已访问集合到未访问节点的最小权值
if (shortEdge[j].lowcost!=0&&arc[k][j] < shortEdge[j].lowcost)
{
shortEdge[j].lowcost = arc[k][j];
shortEdge[j].adjvex = k;
}
}
}
cout << "最小生成树的权值之和为" << sum << endl;
}
Kruskal算法
- 将图中所有边按照权重从小到大进行排序。
- 将每个顶点看做是一个单独集合,即初始时每个顶点自成一个集合。
- 按照排好序的边顺序,按照权重从小到大,依次遍历每一条边。
- 对于每条边,检查其连接的两个顶点所属的集合:
- 如果两个顶点属于同一个集合,则跳过这条边,以免形成环路。
- 如果两个顶点不属于同一个集合,则将这条边加入到最小生成树中,同时合并这两个顶点所属的集合。
- 重复第 3∼4步,直到最小生成树中的节点数等于所有节点数减 1 为止。
#include<iostream>
using namespace std;
const int Maxver = 10;
const int Maxedge = 100;
//存储每一条边的起点,终点和权值
struct EdgeType
{
int start, end;
int weight;
//重载比较运算符,比较边的大小
bool operator<(const EdgeType& a)
{
return weight < a.weight ?true:false;
}
};
class Graph
{
public:
Graph(char *,int ,int);
//查找顶点在顶点数组中对应的下标
int Locatevex(const char& a)
{
for (int i = 0; i < vertexNum; i++)
{
if (vertex[i] == a)
return i;
}
return -1;
}
void Kruskal();
private:
char vertex[Maxver];
EdgeType edge[Maxedge];
int vertexNum, edgeNum;
};
Graph::Graph(char* Vv, int vertexNum, int edgeNum)
{
this->vertexNum = vertexNum;
this->edgeNum = edgeNum;
for (int i = 0; i < this->vertexNum; i++)
{
vertex[i] = Vv[i];
}
cout << "输入各边的起点、终点、权值" << endl;
for (int i = 0; i < this->edgeNum; i++)
{
char a, b;
int weight;
cin >> a >> b >> weight;
int vi = Locatevex(a);
int vj = Locatevex(b);
edge[i].start = vi;
edge[i].end = vj;
edge[i].weight = weight;
}
for (int i = 1, j; i < edgeNum; i++)
{
EdgeType temp = edge[i];
for (j = i; j > 0 && temp < edge[j - 1]; j--)
{
edge[j] = edge[j - 1];
edge[j-1] = temp;
}
}
}
int findRoot(int parent[], int v)
{
int temp = v;
while (parent[temp] != -1)
{
temp = parent[temp];
}
return temp;
}
void Graph::Kruskal()
{
int parent[Maxver];
for (int i = 0; i < vertexNum; i++)
{
parent[i] = -1; //将每个节点看作独立集合
}
int num=0; //节点数量
for (int i = 0; i < vertexNum; i++)
{ //查找第i条边的起点和终点是否在同一个集合中
int vex1 = findRoot(parent, edge[i].start);
int vex2 = findRoot(parent, edge[i].end);
if (vex1 != vex2)
{
cout << '(' << vertex[edge[i].start] << ',' << vertex[edge[i].end ]<< ')' << " ";
parent[vex2] = vex1;
num++;
if (num == vertexNum - 1)
{
return;
}
}
}
}
int main()
{
char V1[10] = { 'A','B','C','D','E','F' ,'G'};
Graph G1(V1, 7, 12);
G1.Kruskal();
return 0;
}
版权声明:本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:jacktools123@163.com进行投诉反馈,一经查实,立即删除!
标签:
相关文章
最新发布
- 【Python】Tkinter + Pandas实现窗口表格显示
- 【Python系列】SQLAlchemy 基本介绍
- 【Python】selenium 的EC.presence_of_element_located 和 EC.element_to_be_clickable 的区别
- 从零到一!超详细Pycharm安装教程(图解+详细步骤)
- python json jsonl 的用法
- 【Python篇】深度探索NumPy(下篇):从科学计算到机器学习的高效实战技巧
- boto3:Python连接S3对象存储并进行文件操作(上传、下载、删除)
- 全网最适合入门的面向对象编程教程:50 Python函数方法与接口-接口和抽象基类
- Python pycryptodome类库使用学习总结
- import torch 报错:WinError 126
点击排行
- 版本匹配指南:Numpy版本和Python版本的对应关系
- Python 可视化 web 神器:streamlit、Gradio、dash、nicegui;低代码 Python Web 框架:PyWebIO
- 版本匹配指南:PyTorch版本、torchvision 版本和Python版本的对应关系
- 相关性分析——Pearson相关系数+热力图(附data和Python完整代码)
- Could not build wheels for llama-cpp-python, which is required to install pyproject.toml-based proj
- Python pyinstaller打包exe最完整教程
- Anaconda版本和Python版本对应关系(持续更新...)
- Python与PyTorch的版本对应