最小生成树---普里姆算法(Prim算法)和克鲁斯卡尔算法(Kruskal算法)代码实现
普里姆算法(Prim算法)
#includebits/stdc++.h
using namespace std;
#define MAXVEX 100
#define INF 65535
typedef char VertexType;
typedef int EdgeType;
typedef struct {
VertexType vexs[MAXVEX];
EdgeType arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
void CreateMGraph(MGraph *G) {
int m, n, w;//vm-vn的权重w
scanf("%d %d", G-numVertexes, G-numEdges);
for(int i = 0; i G-numVertexes; i++) {
getchar();
scanf("%c", G-vexs[i]);
}
for(int i = 0; i G-numVertexes; i++) {
for(int j = 0; j G-numVertexes; j++) {
if(i == j)G-arc[i][j] = 0;
elseG-arc[i][j] = INF;
}
}
for(int k = 0; k G-numEdges; k++) {
scanf("%d %d %d", m, n, w);
G-arc[m][n] = w;
G-arc[n][m] = G-arc[m][n];
}
}
void MiniSpanTree_Prim(MGraph G) {
int min, j, k;
int arjvex[MAXVEX];//最小边在 U集合中的那个顶点的下标
int lowcost[MAXVEX];// 最小边上的权值
//初始化,从点 V0开始找最小生成树T
arjvex[0] = 0;//arjvex[i] = j表示 V-U中集合中的 Vi点的最小边在U集合中的点为 Vj
lowcost[0] = 0;//lowcost[i] = 0表示将点Vi纳入集合 U ，lowcost[i] = w表示 V-U中 Vi点到 U的最小权值
for(int i = 1; i G.numVertexes; i++) {
lowcost[i] = G.arc[0][i];
arjvex[i] = 0;
}
//根据最小生成树的定义：从n个顶点中，找出 n - 1条连线，使得各边权值最小
for(int i = 1; i G.numVertexes; i++) {
min = INF, j = 1, k = 0;
//寻找 V-U到 U的最小权值min
for(j; j G.numVertexes; j++) {
// lowcost[j] != 0保证顶点在 V-U中，用k记录此时的最小权值边在 V-U中顶点的下标
if(lowcost[j] != 0 lowcost[j] min) {
min = lowcost[j];
k = j;
}
}
}
printf("V[%d]-V[%d] weight = %d\n", arjvex[k], k, min);
lowcost[k] = 0;//表示将Vk纳入 U
//查找邻接矩阵Vk行的各个权值，与lowcost的对应值进行比较，若更小则更新lowcost，并将k存入arjvex数组中
for(int i = 1; i G.numVertexes; i++) {
if(lowcost[i] != 0 G.arc[k][i] lowcost[i]) {
lowcost[i] = G.arc[k][i];
arjvex[i] = k;
}
}
}
int main() {
MGraph *G = (MGraph *)malloc(sizeof(MGraph));
CreateMGraph(G);
MiniSpanTree_Prim(*G);
}
/*
input:
4 5
a
b
c
d
0 1 2
0 2 2
0 3 7
1 2 4
2 3 8
output:
V[0]-V[1] weight = 2
V[0]-V[2] weight = 2
V[0]-V[3] weight = 7
最小总权值: 11
*/
时间复杂度O(n^2)
克鲁斯卡尔算法(Kruskal算法)
#includebits/stdc++.h
using namespace std;
#define MAXVEX 100
#define MAXEDGE 100
#define INF 65535
typedef char VertexType;
typedef int EdgeType;
//图的邻接矩阵存储结构的定义
typedef struct {
VertexType vexs[MAXVEX];
EdgeType arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
//边集数组Edge结构的定义
typedef struct {
int begin;
int end;
int weight;
}Edge;
bool vis[100][100];
void CreateMGraph(MGraph *G) {
int m, n, w;//vm-vn的权重w
scanf("%d %d", G-numVertexes, G-numEdges);
for(int i = 0; i G-numVertexes; i++) {
getchar();
scanf("%c", G-vexs[i]);
}
for(int i = 0; i G-numVertexes; i++) {
for(int j = 0; j G-numVertexes; j++) {
if(i == j)G-arc[i][j] = 0;
elseG-arc[i][j] = INF;
}
}
for(int k = 0; k G-numEdges; k++) {
scanf("%d %d %d", m, n, w);
G-arc[m][n] = w;
G-arc[n][m] = G-arc[m][n];
}
}
void MiniSpanTree_Kruskal(MGraph G) {
int v1, v2, vs1, vs2;
Edge edges[MAXEDGE];
int parent[MAXVEX]; //标记各顶点所属的连通分量，用于判断边与边是否形成环路
//将邻接矩阵转换成按权值从小到大排序的边集数组
/*
*/
int tmp = 0, m, n, ans;
ans = (G.numVertexes*G.numVertexes) / 2 - G.numVertexes / 2;
for(int k = 0; k ans; k++) {
int min = INF, i, j;
for(i = 0; i G.numVertexes; i++) {
for(j = 0; j G.numVertexes; j++) {
if(!vis[i][j] i j min G.arc[i][j]) {
min = G.arc[i][j];
m = i;
n = j;
}
}
}
if(G.arc[i][j] == INF)
continue;
edges[tmp].begin = m;
edges[tmp].end = n;
edges[tmp].weight = min;
vis[m][n] = true;
tmp++;
}
//初始化为各顶点各自为一个连通分量
for(int i = 0; i G.numVertexes; i++)
parent[i] = i;
for(int i = 0; i G.numEdges; i++) {
//起点终点下标
v1 = edges[i].begin;
v2 = edges[i].end;
//起点终点连通分量
vs1 = parent[v1];
vs2 = parent[v2];
//边的两个顶点属于不同的连通分量，打印，将新来的连通分量更改为起始点的连通分量
if(vs1 != vs2) {
printf("V[%d]-V[%d] weight:%d\n", edges[i].begin, edges[i].end, edges[i].weight);
for(int j = 0; j G.numVertexes; j++) {
if(parent[j] == vs2)parent[j] = vs1;
}
}
}
}
int main() {
MGraph *G = (MGraph *)malloc(sizeof(MGraph));
CreateMGraph(G);
MiniSpanTree_Kruskal(*G);
}
/*
input:
4 5
a
b
c
d
0 1 2
0 2 2
0 3 7
1 2 4
2 3 8
output:
V[0]-V[1] weight:2
V[0]-V[2] weight:2
V[0]-V[3] weight:7
*/
时间复杂度O(elog2e) e为边数
最小生成树---普里姆算法(Prim算法)和克鲁斯卡尔算法(Kruskal算法)代码实现 相关文章
Java---时间日期
一、java8之前的日期相关类 JDK 1.0中包含了一个java.util.Date类，但是它的大多数方法已经在JDK 1.1引入Calendar类之后被 弃用 而Calendar并不比Date好多少。它们面临的问题是： Date类中的年份是从1900开始的，而月份都从0开始 格式化只对Date类有用，对Ca
网络流最小割专题
最小割的直接应用 网络战争 给出一个带权无向图 \(G=V,E\)，每条边 \(e\) 有一个权 \(w_e\)。 求将点 \(s\) 和点 \(t\) 分开的一个边割集 \(C\)，使得该割集的平均边权最小，即最小化： \[\frac{\sum\limits_{e\in C}w_e}{|C|}\] 注意： 边割集的定义与最小
数据结构---Splay
目录 前言 板子 前言 只会板子 先占个坑，以后再填 板子 【模板】普通平衡树 Code 只有注释，将就着看吧 /*Work by: Suzt_ilymicsKnowledge: Time: O()*/#includeiostream#includecstdio#includecstring#includealgorithm#define LL long long#define orz cou
P4389-付公主的背包【生成函数,多项式exp】
正题 题目链接:/problem/P4389 题目大意 \(n\)种物品，第\(i\)种大小为\(v_i\)，数量无限。对于每个\(s\in[1,m]\)求刚好填满\(s\)容量的方案数。 \(1\leq n,m\leq 10^5\) 解题思路 统计和为一定值的方案数，好像可以生成函数做 每种
习题3-4 统计学生成绩 (15分)
公众号【C you again】回复 “ 浙大版C语言 ” 查看每道题目详细实现思路 公众号【C you again】回复 “ 编程交流群 ” 进C/C++/Java编程题交流、问题解答群 本题要求编写程序读入N个学生的百分制成绩，统计五分制成绩的分布。百分制成绩到五分制成绩的转换
构建后端第6篇之---java 多态的本质 父类引用 指向子类实现
张艳涛写于-2-20 今天来个破例了，不用英文写了，今天在家里电脑写的工具不行，简单的说 主题是：java多态的原理与实现 结论是：java的多态 Father father= new Son()；father.sayHi(),调用的是father类的方法，father的类是抽象类，那么将方法表中的
最小费用最大流Dinic
每条边单位流量会花费价值，在跑出最大流的情况下要求费用最小 #include queue#include cstdio#include cstring#include algorithmusing namespace std;const int N = 5e3 + 5;int read(int x = 0, int f = 1, char c = getchar()) { for (; c '0' || c '9';
shell脚本实现FTP自动上传文件(转)
-----多个文件----- 123456789101112 #!/bin/bash ftp -n! open 172.20.10.242 user logftp logftp binary cd /data/ftp/pcidata/pcilogftp/AppFile/log lcd /data/localacc prompt mget *.gz close bye ! ----单个文件----- 123456789101112 #!/bin/bash ft
module1-02-JS深浅拷贝
JS深浅拷贝---代码基本功能则是(下) 在JS编程中经常需要对数据进行复制，对于什么时候用深拷贝，什么时候用钱开呗是值得我们思考的一个问题 学习好这一内容有利于 提高手撕JS代码能力 提高对边界特殊情况的深入思考 提出两个问题让我们思考以下 ① 拷贝一
module1-01-JS数据类型
JS的数据类型---代码基本测试功能(上) 虽然现在前端技术很多很复杂，但是归根到底，学好js才是重中之重，只有扎实的基础才能往上面盖大楼。 为什么学习这个是必要的呢，首先可以在 边界数据类型条件判断问题 中体现出来 比如一个函数检测参数类型当中 接下
用c语言描述普里姆算法和克鲁斯卡尔算法 最小生成树---普里姆算法（Prim算法)和克鲁斯卡尔算法（Kruskal算法）代码实现...
