【2024年华为OD机试】(C/D卷,200分)- 5G网络建设 （JavaScript&Java & Python&C/C++）
一、问题描述
题目描述
现需要在某城市进行5G网络建设，已经选取N个地点设置5G基站，编号固定为1到N。接下来需要各个基站之间使用光纤进行连接以确保基站能互联互通。不同基站之间假设光纤的成本各不相同，且有些节点之间已经存在光纤相连。
请你设计算法，计算出能联通这些基站的最小成本是多少。
注意：基站的联通具有传递性，比如基站A与基站B架设了光纤，基站B与基站C也架设了光纤，则基站A与基站C视为可以互相联通。
输入描述
- 第一行输入表示基站的个数N，其中：
0 < N ≤ 20。 - 第二行输入表示具备光纤直连条件的基站对的数目M，其中：
0 < M < N * (N - 1) / 2。 - 从第三行开始连续输入M行数据，格式为：
X Y Z P。X，Y表示基站的编号，0 < X ≤ N，0 < Y ≤ N，X ≠ Y。Z表示在X、Y之间架设光纤的成本，0 < Z < 100。P表示是否已存在光纤连接，0表示未连接，1表示已连接。
输出描述
- 如果给定条件，可以建设成功互联互通的5G网络，则输出最小的建设成本。
- 如果给定条件，无法建设成功互联互通的5G网络，则输出
-1。
用例
用例1
输入
3
3
1 2 3 0
1 3 1 0
2 3 5 0
输出
4
说明
只需要在1，2以及1，3基站之间铺设光纤，其成本为 3 + 1 = 4。
用例2
输入
3
1
1 2 5 0
输出
-1
说明
3基站无法与其他基站连接，输出 -1。
用例3
输入
3
3
1 2 3 0
1 3 1 0
2 3 5 1
输出
1
说明
2，3基站已有光纤相连，只要在1，3基站之间铺设光纤，其成本为 1。
题目解析
本题是经典的最小生成树问题的变种。最小生成树（Minimum Spanning Tree, MST）是指在一个无向连通图中，选择一部分边，使得所有顶点都连通，并且这些边的总权重最小。
生成树概念
在无向连通图中，生成树是指包含了全部顶点的极小连通子图。生成树包含原图全部的 n 个顶点和 n-1 条边。生成树的两个重要特性是：
- 包含所有顶点。
- 无环。
最小生成树概念
最小生成树是指生成树中 n-1 条边的权重值之和最小。求解最小生成树的常用算法有 Prim算法 和 Kruskal算法。
Prim算法
Prim算法是基于顶点的贪心算法。其步骤如下：
- 选择一个起始顶点。
- 从当前已选顶点集合出发，选择一条权重最小的边，连接到未选顶点。
- 将新顶点加入已选顶点集合。
- 重复上述步骤，直到所有顶点都被选中。
适用场景：适用于节点少、边多的情况。
Kruskal算法
Kruskal算法是基于边的贪心算法。其步骤如下：
- 将所有边按权重从小到大排序。
- 依次选择权重最小的边，如果这条边的两个顶点不在同一个连通分量中，则将其加入生成树。
- 重复上述步骤，直到生成树中有
n-1条边。
适用场景：适用于节点多、边少的情况。
本题的特殊性
本题中，某些基站之间已经存在光纤连接（即某些边的权重为0）。处理这种情况的方法是将已连接的边视为权重为0的边，然后使用最小生成树算法求解。
解题思路#
- 输入处理：读取基站数量
N和边数量M，然后读取每条边的信息。 - 处理已连接的边：对于已连接的边（
P = 1），将其权重设为0。 - 构建图：将所有边按权重从小到大排序。
- 使用Kruskal算法：
-
初始化并查集，每个基站初始为一个独立的连通分量。
-
依次选择权重最小的边，如果这条边的两个基站不在同一个连通分量中，则将其加入生成树，并合并这两个连通分量。
-
记录总成本。
-
- 判断连通性：如果最终生成树中的边数小于
N-1，则输出-1；否则输出总成本。
关键点
- 并查集：用于判断两个基站是否在同一个连通分量中，避免形成环。
- 权重处理：已连接的边权重设为0，确保优先选择这些边。
- 连通性判断：最终生成树的边数必须为
N-1，否则无法连通所有基站。
通过上述方法，可以高效地求解本题的最小建设成本。 #
二、JavaScript算法源码
Prim算法
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void (async function () {
const n = parseInt(await readline()); // 基站数量（节点数）
const m = parseInt(await readline()); // 基站对数量（边数）
// 邻接矩阵, 初始化默认各点之间互不联通，即i-j边权无限大
const graph = new Array(n + 1)
.fill(0)
.map(() => new Array(n + 1).fill(Infinity));
for (let i = 0; i < m; i++) {
const [x, y, z, p] = (await readline()).split(" ").map(Number);
if (p == 0) {
// x-y边权为z
graph[x][y] = z;
graph[y][x] = z;
} else {
// 对应已经联通的两点，可以理解为边权为0
graph[x][y] = 0;
graph[y][x] = 0;
}
}
function prim() {
// 记录最小生成树的边权和
let minWeight = 0;
// inTree[i] 表示 节点i 是否在最小生成树中
const inTree = new Array(n + 1).fill(false);
// 初始时任选一个节点作为最小生成树的初始节点，这里选择节点1
inTree[1] = true;
// 记录最小生成树中点数量
let inTree_count = 1;
// dis[i]表示 节点i 到最小生成树集合 的最短距离
// 初始时，最小生成树集合中只有节点1，因此其他节点到最小生成树的距离，其实就是到节点1的距离
const dis = new Array(n + 1).fill(0).map((_, i) => graph[i][1]);
// 如果最小生成树中点数量达到n个，则结束循环
while (inTree_count < n) {
// 现在我们需要从未纳入最小生成树的点中，找到一个距离最小生成树最近的
let minDis = Infinity; // minDis 记录这个最近距离
let nodeIdx = 0; // idx 记录距离最小生成树minDis个距离的节点
for (let i = 1; i <= n; i++) {
// 从未纳入最小生成树的点中，找到一个距离最小生成树最近的
if (!inTree[i] && dis[i] < minDis) {
minDis = dis[i];
nodeIdx = i;
}
}
// 如果nodeIdx == 0,则说明未纳入最小生成树的这些点到最小生成树的距离都是Integer.MAX_VALUE，即不与最小生成树存在关联
if (nodeIdx == 0) {
// 则说明，当前所有点无法形成最小生成树
return -1;
}
inTree[nodeIdx] = true; // 最小生成树需要纳入最短距离点nodeIdx
inTree_count++; // 最小生成树中点数量+1
minWeight += dis[nodeIdx]; // 更新最小生成树的权重和
// dis[i] 初始时记录的是节点i 到 节点1 的距离（初始的生成树中只有节点1）
// 现在生成树纳入了新节点nodeIdx，则我们需要更新一下dis[i]，即有可能某些点到最小生成树中的nodeIdx点距离更近
for (let i = 1; i <= n; i++) {
if (!inTree[i] && graph[nodeIdx][i] < dis[i]) {
// 注意，这是一个累进过程，初始时dis[i]记录的是节点i到节点1的距离，
// 之后，最小生成树纳入新点后，如果节点i到新点的距离更近，则dis[i]就更新为这个更短距离
// 总之，dis[i] 记录的是 节点 i 到最小生成树的最短距离
dis[i] = graph[nodeIdx][i];
}
}
}
return minWeight;
}
console.log(prim());
})();
代码讲解：
-
输入处理：首先读取基站数量
n和基站对数量m，然后初始化一个邻接矩阵graph，表示基站之间的连接关系。如果两个基站已经联通，则边权为0，否则边权为输入的z。 -
Prim算法实现：
- 初始化：选择一个起始节点（这里选择节点1），并将其标记为已加入最小生成树。
- 距离数组
dis：记录每个节点到当前最小生成树的最短距离。 - 主循环：每次从未加入最小生成树的节点中，选择一个距离最小生成树最近的节点加入，并更新最小生成树的权重和。
- 更新距离数组：每当有新节点加入最小生成树时，更新其他节点到最小生成树的最短距离。
-
输出结果：最终输出最小生成树的权重和。
Kruskal算法
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void (async function () {
const n = parseInt(await readline()); // 基站数量（节点数）
const m = parseInt(await readline()); // 基站对数量（边数）
const edges = [];
for (let i = 0; i < m; i++) {
// 边起点, 边终点，边权重，起点和终点是否已关联
const [x, y, z, p] = (await readline()).split(" ").map(Number);
if (p == 0) {
// 起点和终点未关联
edges.push([x, y, z]);
} else {
// 起点和终点已关联，则关联代价实际为0
edges.push([x, y, 0]);
}
}
function kruskal() {
let minWeight = 0;
// 按照边权升序
edges.sort((a, b) => a[2] - b[2]);
const ufs = new UnionFindSet(n + 1);
// 最先遍历出来是边权最小的边
for (const [x, y, z] of edges) {
// 如果edge.from节点 和 edge.to节点 是同一个连通分量（即都在最小生成树中），则此时会产生环
// 因此只有当edge.from节点 和 edge.to节点不在同一个连通分量时，才能合并（纳入最小生成树）
if (ufs.find(x) != ufs.find(y)) {
minWeight += z;
ufs.union(x, y);
// 需要注意的是，上面初始化并查集的节点数为n+1个，因此并查集底层fa数组的长度就是n+1，即索引范围是[0, n]，左闭右闭，
// 其中0索引是无用的，1~n索引对应最小生成树中各个节点，如果者n个节点可以变为最小生成树，那么1~n节点会被合并为一个连通分量
// 而0索引虽然无用，但是也会自己形成一个连通分量，因此最终如果能形成最小生成树，则并查集中会有两个连通分量
if (ufs.count == 2) {
return minWeight;
}
}
}
return -1;
}
console.log(kruskal());
})();
// 并查集实现
class UnionFindSet {
constructor(n) {
this.fa = new Array(n).fill(true).map((_, idx) => idx);
this.count = n; // 初始时各站点互不相连，互相独立，因此需要给n个站点发送广播
}
// 查x站点对应的顶级祖先站点
find(x) {
while (x !== this.fa[x]) {
x = this.fa[x];
}
return x;
}
// 合并两个站点，其实就是合并两个站点对应的顶级祖先节点
union(x, y) {
let x_fa = this.find(x);
let y_fa = this.find(y);
if (x_fa !== y_fa) {
// 如果两个站点祖先相同，则在一条链上，不需要合并
this.fa[y_fa] = x_fa; // 合并站点，即让某条链的祖先指向另一条链的祖先
this.count--; // 一旦两个站点合并，则发送广播次数减1
}
}
}
代码讲解：
-
输入处理：读取基站数量
n和基站对数量m，然后读取每条边的信息并存储在edges数组中。如果两个基站已经联通，则边权为0，否则边权为输入的z。 -
Kruskal算法实现：
- 排序：将所有边按权重从小到大排序。
- 并查集初始化：初始化一个并查集
ufs，用于管理节点的连通性。 - 主循环：遍历排序后的边，如果边的两个端点不在同一个连通分量中，则将这条边加入最小生成树，并合并这两个连通分量。
- 终止条件：当并查集中的连通分量减少到2时，说明最小生成树已经形成，返回最小生成树的权重和。
-
并查集实现：
- 初始化：每个节点的父节点初始化为自身。
- 查找操作：查找某个节点的根节点。
- 合并操作：将两个节点的根节点合并，减少连通分量的数量。
-
输出结果：最终输出最小生成树的权重和。
三、Java算法源码
Prim算法
Prim算法是一种用于求解最小生成树（Minimum Spanning Tree, MST）的贪心算法。它从一个起始节点开始，逐步扩展生成树，每次选择与当前生成树距离最近的节点加入生成树，直到所有节点都被包含。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 基站数量（节点数）
int m = sc.nextInt(); // 基站对数量（边数）
// 邻接矩阵
int[][] graph = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
// 初始化默认各点之间互不联通，即i-j边权无限大
graph[i][j] = Integer.MAX_VALUE;
}
}
for (int i = 0; i < m; i++) {
int x = sc.nextInt();
int y = sc.nextInt();
int z = sc.nextInt();
int p = sc.nextInt();
if (p == 0) {
// x-y边权为z
graph[x][y] = z;
graph[y][x] = z;
} else {
// 对应已经联通的两点，可以理解为边权为0
graph[x][y] = 0;
graph[y][x] = 0;
}
}
System.out.println(prim(graph, n));
}
public static int prim(int[][] graph, int n) {
// 记录最小生成树的边权和
int minWeight = 0;
// inTree[i] 表示 节点i 是否在最小生成树中
boolean[] inTree = new boolean[n + 1];
// 初始时任选一个节点作为最小生成树的初始节点，这里选择节点1
inTree[1] = true;
// 记录最小生成树中点数量
int inTree_count = 1;
// dis[i]表示 节点i 到最小生成树集合 的最短距离
int[] dis = new int[n + 1];
for (int i = 1; i <= n; i++) {
// 初始时，最小生成树集合中只有节点1，因此其他节点到最小生成树的距离，其实就是到节点1的距离
dis[i] = graph[1][i];
}
// 如果最小生成树中点数量达到n个，则结束循环
while (inTree_count < n) {
// 现在我们需要从未纳入最小生成树的点中，找到一个距离最小生成树最近的
// minDis 记录这个最近距离
int minDis = Integer.MAX_VALUE;
// idx 记录距离最小生成树minDis个距离的节点
int nodeIdx = 0;
for (int i = 1; i <= n; i++) {
// 从未纳入最小生成树的点中，找到一个距离最小生成树最近的
if (!inTree[i] && dis[i] < minDis) {
minDis = dis[i];
nodeIdx = i;
}
}
// 如果nodeIdx == 0,则说明未纳入最小生成树的这些点到最小生成树的距离都是Integer.MAX_VALUE，即不与最小生成树存在关联
if (nodeIdx == 0) {
// 则说明，当前所有点无法形成最小生成树
return -1;
}
inTree[nodeIdx] = true; // 最小生成树需要纳入最短距离点nodeIdx
inTree_count++; // 最小生成树中点数量+1
minWeight += dis[nodeIdx]; // 更新最小生成树的权重和
// dis[i] 初始时记录的是节点i 到 节点1 的距离（初始的生成树中只有节点1）
// 现在生成树纳入了新节点nodeIdx，则我们需要更新一下dis[i]，即有可能某些点到最小生成树中的nodeIdx点距离更近
for (int i = 1; i <= n; i++) {
if (!inTree[i] && graph[nodeIdx][i] < dis[i]) {
// 注意，这是一个累进过程，初始时dis[i]记录的是节点i到节点1的距离，
// 之后，最小生成树纳入新点后，如果节点i到新点的距离更近，则dis[i]就更新为这个更短距离
// 总之，dis[i] 记录的是 节点 i 到最小生成树的最短距离
dis[i] = graph[nodeIdx][i];
}
}
}
return minWeight;
}
}
Kruskal算法
Kruskal算法也是一种用于求解最小生成树的算法。它通过按边权从小到大排序，逐步选择边加入生成树，同时避免形成环。
import java.util.Arrays;
import java.util.Scanner;
public class Main {
// 边
static class Edge {
int from; // 边起点
int to; // 边终点
int weight; // 边权重
public Edge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 基站数量（节点数）
int m = sc.nextInt(); // 基站对数量（边数）
Edge[] edges = new Edge[m];
for (int i = 0; i < m; i++) {
int x = sc.nextInt();
int y = sc.nextInt();
int z = sc.nextInt();
int p = sc.nextInt();
// 如果p==1，则可以认为x-y边权为0
edges[i] = new Edge(x, y, p == 0 ? z : 0);
}
System.out.println(kruskal(edges, n));
}
public static int kruskal(Edge[] edges, int n) {
int minWeight = 0;
// 按照边权升序
Arrays.sort(edges, (a, b) -> a.weight - b.weight);
UnionFindSet ufs = new UnionFindSet(n + 1);
// 最先遍历出来是边权最小的边
for (Edge edge : edges) {
// 如果edge.from节点 和 edge.to节点 是同一个连通分量（即都在最小生成树中），则此时会产生环
// 因此只有当edge.from节点 和 edge.to节点不在同一个连通分量时，才能合并（纳入最小生成树）
if (ufs.find(edge.from) != ufs.find(edge.to)) {
minWeight += edge.weight;
ufs.union(edge.from, edge.to);
// 需要注意的是，上面初始化并查集的节点数为n+1个，因此并查集底层fa数组的长度就是n+1，即索引范围是[0, n]，左闭右闭，
// 其中0索引是无用的，1~n索引对应最小生成树中各个节点，如果者n个节点可以变为最小生成树，那么1~n节点会被合并为一个连通分量
// 而0索引虽然无用，但是也会自己形成一个连通分量，因此最终如果能形成最小生成树，则并查集中会有两个连通分量
if (ufs.count == 2) {
return minWeight;
}
}
}
return -1;
}
}
// 并查集
class UnionFindSet {
int[] fa;
int count;
public UnionFindSet(int n) {
this.fa = new int[n];
this.count = n;
for (int i = 0; i < n; i++) this.fa[i] = i;
}
public int find(int x) {
if (x != this.fa[x]) {
return (this.fa[x] = this.find(this.fa[x]));
}
return x;
}
public void union(int x, int y) {
int x_fa = this.find(x);
int y_fa = this.find(y);
if (x_fa != y_fa) {
this.fa[y_fa] = x_fa;
this.count--;
}
}
}
代码解释
-
Prim算法：
- 邻接矩阵：使用二维数组
graph存储图的边权信息。 - 初始化：将所有边的权重初始化为
Integer.MAX_VALUE，表示初始时各节点之间不连通。 - 输入处理：根据输入的边信息更新邻接矩阵。如果
p == 0，表示边权为z；如果p == 1，表示边权为0（即已经连通）。 - Prim算法核心：
- 使用
inTree数组记录哪些节点已经在生成树中。 - 使用
dis数组记录每个节点到生成树的最短距离。 - 每次选择距离生成树最近的节点加入生成树，并更新其他节点到生成树的距离。
- 如果所有节点都被加入生成树，则返回最小生成树的总权重；否则返回
-1表示无法形成最小生成树。
- 使用
- 邻接矩阵：使用二维数组
-
Kruskal算法：
- 边类：定义了一个
Edge类，用于存储边的起点、终点和权重。 - 输入处理：根据输入的边信息创建
Edge对象数组。 - Kruskal算法核心：
- 将边按权重升序排序。
- 使用并查集（
UnionFindSet）来管理节点的连通性。 - 遍历所有边，如果边的两个端点不在同一个连通分量中，则将边加入生成树，并合并两个连通分量。
- 如果最终并查集中只剩下两个连通分量（一个包含所有节点，另一个是未使用的0索引），则返回最小生成树的总权重；否则返回
-1表示无法形成最小生成树。
- 边类：定义了一个
-
并查集：
- 初始化：每个节点的父节点初始化为自己。
- 查找：使用路径压缩优化查找操作。
- 合并：将两个节点的连通分量合并，并减少连通分量的数量。
总结
- Prim算法：适用于稠密图，时间复杂度为O(n^2)。
- Kruskal算法：适用于稀疏图，时间复杂度为O(m log m)，其中m是边的数量。
这两种算法都可以有效地求解最小生成树问题，选择哪种算法取决于图的结构和具体需求。
四、Python算法源码
以下是关于 Prim 和 Kruskal 算法的详细注释和讲解。这两个算法用于在图中找到最小生成树（Minimum Spanning Tree，MST）。
Prim 算法
代码解析
import sys
# 输入获取
n = int(input()) # 基站数量（节点数）
m = int(input()) # 基站对数量（边数）
# 邻接矩阵, 初始化默认各点之间互不联通，即i-j边权无限大
graph = [[sys.maxsize for _ in range(n + 1)] for _ in range(n + 1)]
for _ in range(m):
x, y, z, p = map(int, input().split())
if p == 0:
# x-y边权为z
graph[x][y] = z
graph[y][x] = z
else:
# 对应已经联通的两点，可以理解为边权为0
graph[x][y] = 0
graph[y][x] = 0
- 输入部分：
- 读取节点数量
n和边数量m。 - 使用邻接矩阵
graph存储图中每对节点之间的边权。初始时，所有边权设为sys.maxsize（无穷大），表示未联通。 - 根据输入信息，如果
p == 0，则边权为z；如果p == 1，则表示已联通，边权为0。
- 读取节点数量
# Prim算法
def prim():
minWeight = 0 # 记录最小生成树的总权重
inTree = [False] * (n + 1) # 表示每个节点是否在生成树中
inTree[1] = True # 初始选择节点1加入生成树
inTree_count = 1 # 生成树中的节点数
dis = [0] * (n + 1)
for i in range(1, n + 1):
dis[i] = graph[1][i] # 初始距离为节点1到各节点的距离
while inTree_count < n:
minDis = sys.maxsize # 最近距离初始化为无穷大
nodeIdx = 0 # 记录距离最短的节点
for i in range(1, n+1):
if not inTree[i] and dis[i] < minDis:
minDis = dis[i]
nodeIdx = i
if nodeIdx == 0:
return -1 # 无法形成生成树
inTree[nodeIdx] = True
inTree_count += 1
minWeight += dis[nodeIdx]
for i in range(1, n+1):
if not inTree[i] and graph[nodeIdx][i] < dis[i]:
dis[i] = graph[nodeIdx][i]
return minWeight
- Prim 算法逻辑：
- 初始化：最小生成树的权重
minWeight为0，从节点1开始构建生成树。 - 使用数组
inTree跟踪哪些节点已在生成树中。 dis数组保存每个节点到生成树的最短距离。- 主循环：在生成树节点数小于
n时，继续进行。- 从未加入生成树的节点中，选择距离生成树最近的节点
nodeIdx。 - 如果所有未加入的节点距离生成树无穷大，返回
-1，表示无法构成生成树。 - 纳入该节点并更新生成树的总权重。
- 更新
dis数组，记录新加入的节点可能带来的更短距离。
- 从未加入生成树的节点中，选择距离生成树最近的节点
- 初始化：最小生成树的权重
# 算法调用
print(prim())
- 调用
prim()函数并打印结果。
Kruskal 算法
代码解析
# 并查集实现
class UnionFindSet:
def __init__(self, n):
self.fa = [i for i in range(n)]
self.count = n
def find(self, x):
if x != self.fa[x]:
self.fa[x] = self.find(self.fa[x])
return self.fa[x]
def union(self, x, y):
x_fa = self.find(x)
y_fa = self.find(y)
if x_fa != y_fa:
self.fa[y_fa] = x_fa
self.count -= 1
- 并查集（Union-Find）：
- 用于高效判断节点是否属于同一连通分量。
find方法：路径压缩，找到节点的根，并将路径上的节点直接连接到根。union方法：连接两个节点，合并它们所属的连通分量。
# 输入获取
n = int(input()) # 基站数量（节点数）
m = int(input()) # 基站对数量（边数）
edges = []
for _ in range(m):
x, y, z, p = map(int, input().split())
if p == 0:
edges.append([x, y, z]) # 未关联
else:
edges.append([x, y, 0]) # 已关联，权重为0
- 输入部分：
- 读取节点和边的数量。
- 使用
edges列表存储所有边的信息。如果已关联，则权重设为0。
# kruskal算法
def kruskal():
minWeight = 0
edges.sort(key=lambda x: x[2]) # 按边权升序排序
ufs = UnionFindSet(n+1)
for x, y, z in edges:
if ufs.find(x) != ufs.find(y):
minWeight += z
ufs.union(x, y)
if ufs.count == 2:
return minWeight
return -1
- Kruskal 算法逻辑：
- 按边权重升序对边排序。
- 遍历所有边，使用并查集判断边的两个节点是否属于不同连通分量。
- 如果是，则合并两个节点并将该边纳入生成树，增加总权重。
- 当并查集中的连通分量数量为
2时，表示所有节点已形成一个连通分量，返回当前权重。
# 算法入口
print(kruskal())
- 调用
kruskal()函数并打印结果。
结论
-
Prim 算法：适合稠密图，利用邻接矩阵和顶点集来构造最小生成树，每次选择最近的节点加入生成树。
-
Kruskal 算法：适合稀疏图，使用边集和并查集处理，按边权重排序后逐一尝试加入边构建最小生成树。
-
这两种算法都有效解决了最小生成树问题，选用哪种取决于图的性质（稠密或稀疏）和具体需求。
五、C/C++算法源码：
C 版本
以下是 Prim 算法和 Kruskal 算法的 C 语言版本
Prim 算法
代码实现
#include <stdio.h>
#include <limits.h>
int n, m; // 节点数量 n 和边数量 m
int graph[21][21]; // 邻接矩阵表示图，最多支持 20 个节点
// Prim 最小生成树算法
int prim() {
int minWeight = 0; // 最小生成树的总权重
int inTree[21] = {0}; // 标记节点是否在最小生成树中
int dis[21]; // 存储节点到最小生成树的最短距离
// 初始化：从节点 1 开始构建最小生成树
inTree[1] = 1; // 节点 1 加入生成树
int inTree_count = 1; // 生成树节点数量
// 初始化 dis 数组，初始时其他节点到生成树的距离为到节点 1 的距离
for (int i = 1; i <= n; i++) {
dis[i] = graph[1][i];
}
// 循环直到所有节点都被加入到生成树中
while (inTree_count < n) {
int minDis = INT_MAX; // 当前最短距离
int nodeIdx = 0; // 最近的节点编号
// 找到距离最小生成树最近的未加入节点
for (int i = 1; i <= n; i++) {
if (!inTree[i] && dis[i] < minDis) {
minDis = dis[i];
nodeIdx = i;
}
}
// 如果无法找到这样的节点，说明图不连通，返回 -1
if (nodeIdx == 0) {
return -1;
}
// 将新节点加入最小生成树
inTree[nodeIdx] = 1;
inTree_count++;
minWeight += minDis; // 累加边权到总权重
// 更新其他节点到最小生成树的最短距离
for (int i = 1; i <= n; i++) {
if (!inTree[i] && graph[nodeIdx][i] < dis[i]) {
dis[i] = graph[nodeIdx][i];
}
}
}
return minWeight; // 返回最小生成树的总权重
}
int main() {
scanf("%d %d", &n, &m);
// 初始化邻接矩阵，所有节点间距离初始化为无穷大
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
graph[i][j] = INT_MAX;
}
}
// 读取边的信息
for (int i = 0; i < m; i++) {
int x, y, z, p;
scanf("%d %d %d %d", &x, &y, &z, &p);
if (p == 0) {
// 如果节点未联通，取权重为 z
graph[x][y] = z;
graph[y][x] = z;
} else {
// 如果节点已联通，边权重为 0
graph[x][y] = 0;
graph[y][x] = 0;
}
}
// 输出 Prim 算法计算的最小生成树权重
printf("%d\n", prim());
return 0;
}
Prim 算法讲解
-
邻接矩阵表示图：
- 使用二维数组
graph表示图，graph[i][j]存储节点i到节点j的边权值。 - 如果两个节点不直接连接，边权值初始化为无穷大 (
INT_MAX)。
- 使用二维数组
-
逻辑流程：
- 从任意一个节点（本例中为节点
1）开始构建最小生成树。 - 在每一步中，找到距离当前生成树最近的未加入节点，将其加入生成树，并更新其他节点到生成树的最短距离。
- 重复上述过程，直到所有节点都加入生成树。
- 从任意一个节点（本例中为节点
-
复杂度：
- 时间复杂度是 (O(n^2))，因为每次需要遍历所有节点找到最近的节点。
Kruskal 算法
代码实现
#include <stdio.h>
#include <stdlib.h>
// 并查集结构
typedef struct {
int *fa; // 父节点数组
int count; // 连通分量数量
} UFS;
// 初始化并查集
UFS *new_UFS(int n) {
UFS *ufs = (UFS *)malloc(sizeof(UFS));
ufs->fa = (int *)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++) {
ufs->fa[i] = i; // 每个节点的初始父节点是自身
}
ufs->count = n;
return ufs;
}
// 并查集查找操作
int find_UFS(UFS *ufs, int x) {
if (x != ufs->fa[x]) {
ufs->fa[x] = find_UFS(ufs, ufs->fa[x]); // 路径压缩
}
return ufs->fa[x];
}
// 并查集合并操作
void union_UFS(UFS *ufs, int x, int y) {
int rootX = find_UFS(ufs, x);
int rootY = find_UFS(ufs, y);
if (rootX != rootY) {
ufs->fa[rootY] = rootX; // 合并两个连通分量
ufs->count--;
}
}
// 边结构
typedef struct Edge {
int from; // 起点
int to; // 终点
int weight; // 权重
} Edge;
int n, m; // 节点数量和边数量
Edge *edges; // 边数组
// 边权排序规则
int cmp(const void *a, const void *b) {
return ((Edge *)a)->weight - ((Edge *)b)->weight;
}
// Kruskal 最小生成树算法
int kruskal() {
int minWeight = 0; // 最小生成树总权重
// 按边的权重升序排序
qsort(edges, m, sizeof(Edge), cmp);
UFS *ufs = new_UFS(n + 1); // 初始化并查集，节点编号从 1 开始
// 遍历所有边
for (int i = 0; i < m; i++) {
int x = edges[i].from;
int y = edges[i].to;
// 如果两个节点不在同一连通分量中，则将此边加入最小生成树
if (find_UFS(ufs, x) != find_UFS(ufs, y)) {
minWeight += edges[i].weight; // 累加权重
union_UFS(ufs, x, y); // 合并连通分量
// 如果剩下的连通分量只有 2 个，说明所有节点已连通
if (ufs->count == 2) {
return minWeight;
}
}
}
return -1; // 如果图不连通，返回 -1
}
int main() {
scanf("%d %d", &n, &m);
edges = (Edge *)malloc(sizeof(Edge) * m); // 动态分配边数组
// 读取边信息
for (int i = 0; i < m; i++) {
int x, y, z, p;
scanf("%d %d %d %d", &x, &y, &z, &p);
edges[i].from = x;
edges[i].to = y;
edges[i].weight = (p == 0) ? z : 0; // 如果已联通，边权值为 0
}
// 输出 Kruskal 算法计算的最小生成树权重
printf("%d\n", kruskal());
return 0;
}
Kruskal 算法讲解
-
边排序：
- 按边的权重升序排序，优先处理权重较小的边。
-
并查集：
- 使用并查集判断两个节点是否属于同一连通分量；如果不属于，则将它们合并。
-
逻辑流程：
- 遍历所有边，尝试将其加入生成树。
- 当所有节点形成一个连通分量时，停止算法并返回生成树总权重。
-
复杂度：
- 排序复杂度为 (O(m \log m))，查找和合并复杂度为 (O(\alpha(n)))，总复杂度接近 (O(m \log m))。
总结
- Prim 算法适用于稠密图，使用邻接矩阵存储图。
- Kruskal 算法适用于稀疏图，使用边集和并查集处理。
- 两种算法都可以高效解决最小生成树问题，根据具体的图结构选择合适的算法即可。
C++ 版本
以下是 Prim 和 Kruskal 算法：
Prim 算法
#include <iostream>
#include <climits>
#include <vector>
using namespace std;
const int MAX_N = 21; // 假设节点最大数量为 21
int graph[MAX_N][MAX_N]; // 邻接矩阵，用于存储边权值
int n, m; // n 表示节点数量，m 表示边数量
int prim() {
int minWeight = 0; // 最小生成树的总权重
vector<bool> inTree(n + 1, false); // inTree[i] 表示节点 i 是否已经纳入到最小生成树
vector<int> dis(n + 1, INT_MAX); // dis[i] 表示每个节点到生成树的最小距离
inTree[1] = true; // 从节点 1 开始构建最小生成树
for (int i = 1; i <= n; i++) {
dis[i] = graph[1][i]; // 初始化距离：从节点 1 到其他所有节点的距离
}
int inTree_count = 1; // 当前生成树中的节点数量
while (inTree_count < n) {
int minDis = INT_MAX; // 当前最短距离
int nodeIdx = 0; // 记录距离生成树最近的节点
// 遍历所有未加入生成树的节点，找到距离生成树最近的节点
for (int i = 1; i <= n; i++) {
if (!inTree[i] && dis[i] < minDis) {
minDis = dis[i];
nodeIdx = i;
}
}
if (nodeIdx == 0) {
// 如果无法找到合适的节点，则说明图不连通，无法形成生成树
return -1;
}
// 将该节点加入到生成树中
inTree[nodeIdx] = true;
inTree_count++;
minWeight += dis[nodeIdx]; // 更新总权重
// 更新 dis 数组：检查是否通过新加入的节点可以缩短其他节点到生成树的距离
for (int i = 1; i <= n; i++) {
if (!inTree[i] && graph[nodeIdx][i] < dis[i]) {
dis[i] = graph[nodeIdx][i];
}
}
}
return minWeight;
}
int main() {
cin >> n >> m;
// 初始化邻接矩阵，所有边权值初始为无穷大（表示节点间不联通）
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
graph[i][j] = INT_MAX;
}
}
// 输入边信息
for (int i = 0; i < m; i++) {
int x, y, z, p;
cin >> x >> y >> z >> p;
if (p == 0) {
// 如果 p == 0，边权值为 z
graph[x][y] = z;
graph[y][x] = z;
} else {
// 如果 p == 1，表示两点已经联通，边权值设为 0
graph[x][y] = 0;
graph[y][x] = 0;
}
}
cout << prim() << endl;
return 0;
}
C++ Prim 算法讲解
-
数据结构：
- 使用邻接矩阵
graph表示图，其中graph[i][j]表示节点i和节点j之间的边权值。 - 使用数组
inTree表示节点是否已经加入到生成树中。 - 使用数组
dis记录每个节点到生成树的最短距离。
- 使用邻接矩阵
-
初始化：
- 将所有边权值初始化为
INT_MAX，表示两点之间最初不直接联通。 - 从节点
1开始构建生成树，初始化dis为从节点1到其他节点的距离。
- 将所有边权值初始化为
-
主循环：
- 每次找到距离生成树最近的未加入节点，将其加入生成树。
- 更新
dis数组，检查是否通过新加入节点可以更短连接其他未加入节点。
-
返回结果：
- 如果找到了一棵包含所有节点的生成树，返回其总权重；否则返回
-1表示图不连通。
- 如果找到了一棵包含所有节点的生成树，返回其总权重；否则返回
Kruskal 算法
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 边的结构体
struct Edge {
int from; // 边的起点
int to; // 边的终点
int weight; // 边的权重
};
// 并查集实现
class UnionFindSet {
public:
vector<int> fa; // 并查集的父节点数组
int count; // 当前连通分量数量
UnionFindSet(int n) {
fa.resize(n);
for (int i = 0; i < n; i++) {
fa[i] = i; // 每个节点初始化时是独立的连通分量
}
count = n;
}
int find(int x) {
if (x != fa[x]) {
fa[x] = find(fa[x]); // 路径压缩
}
return fa[x];
}
void unionSet(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
fa[rootY] = rootX; // 合并两个连通分量
count--;
}
}
};
// Kruskal 算法
int kruskal(int n, vector<Edge>& edges) {
int minWeight = 0;
// 按边权值升序排序
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.weight < b.weight;
});
UnionFindSet ufs(n + 1); // 初始化并查集，包含 n+1 个节点
// 遍历每条边
for (const auto& edge : edges) {
int x = edge.from;
int y = edge.to;
// 如果两个节点不在同一个连通分量中，则合并它们
if (ufs.find(x) != ufs.find(y)) {
minWeight += edge.weight; // 累加边权
ufs.unionSet(x, y); // 合并连通分量
// 如果所有节点已连通，返回结果
if (ufs.count == 2) {
return minWeight;
}
}
}
return -1; // 如果图不连通，返回 -1
}
int main() {
int n, m;
cin >> n >> m;
vector<Edge> edges(m);
for (int i = 0; i < m; i++) {
int x, y, z, p;
cin >> x >> y >> z >> p;
edges[i].from = x;
edges[i].to = y;
edges[i].weight = (p == 0 ? z : 0); // 如果已联通，权值为 0
}
cout << kruskal(n, edges) << endl;
return 0;
}
C++ Kruskal 算法讲解
-
数据结构：
- 使用结构体
Edge表示边，包括起点、终点和权重。 - 使用类
UnionFindSet实现并查集，用于判断节点是否属于同一连通分量。
- 使用结构体
-
排序：
- 按权重升序排序所有边，以便从权重最小的边开始处理。
-
算法流程：
- 遍历排序后的边集，如果两个节点不在同一连通分量，则将其加入生成树，并合并两个连通分量。
- 直到所有节点连通时，返回生成树的总权重。
-
返回结果：
- 如果能形成生成树，返回其总权重；否则返回
-1表示图不连通。
- 如果能形成生成树，返回其总权重；否则返回
总结
- Prim 算法：适用于稠密图，直接从任意节点开始构建生成树。
- Kruskal 算法：适用于稀疏图，先将边排序，逐步构建生成树。
- 这两种算法都能够高效解决最小生成树问题，适用场景不同。
六、尾言
什么是华为OD？
华为OD（Outsourcing Developer，外包开发工程师）是华为针对软件开发工程师岗位的一种招聘形式，主要包括笔试、技术面试以及综合面试等环节。尤其在笔试部分，算法题的机试至关重要。
为什么刷题很重要？
-
机试是进入技术面的第一关：
华为OD机试（常被称为机考）主要考察算法和编程能力。只有通过机试，才能进入后续的技术面试环节。 -
技术面试需要手撕代码：
技术一面和二面通常会涉及现场编写代码或算法题。面试官会注重考察候选人的思路清晰度、代码规范性以及解决问题的能力。因此提前刷题、多练习是通过面试的重要保障。 -
入职后的可信考试：
入职华为后，还需要通过“可信考试”。可信考试分为三个等级：- 入门级：主要考察基础算法与编程能力。
- 工作级：更贴近实际业务需求，可能涉及复杂的算法或与工作内容相关的场景题目。
- 专业级：最高等级，考察深层次的算法以及优化能力，与薪资直接挂钩。
刷题策略与说明：
2024年8月14日之后，华为OD机试的题库转为 E卷，由往年题库（D卷、A卷、B卷、C卷）和全新题目组成。刷题时可以参考以下策略：
-
关注历年真题：
- 题库中的旧题占比较大，建议优先刷历年的A卷、B卷、C卷、D卷题目。
- 对于每道题目，建议深度理解其解题思路、代码实现，以及相关算法的适用场景。
-
适应新题目：
- E卷中包含全新题目，需要掌握全面的算法知识和一定的灵活应对能力。
- 建议关注新的刷题平台或交流群，获取最新题目的解析和动态。
-
掌握常见算法：
华为OD考试通常涉及以下算法和数据结构：- 排序算法（快速排序、归并排序等）
- 动态规划（背包问题、最长公共子序列等）
- 贪心算法
- 栈、队列、链表的操作
- 图论（最短路径、最小生成树等）
- 滑动窗口、双指针算法
-
保持编程规范：
- 注重代码的可读性和注释的清晰度。
- 熟练使用常见编程语言，如C++、Java、Python等。
如何获取资源？
-
官方参考：
- 华为招聘官网或相关的招聘平台会有一些参考信息。
- 华为OD的相关公众号可能也会发布相关的刷题资料或学习资源。
-
加入刷题社区：
- 找到可信的刷题交流群，与其他备考的小伙伴交流经验。
- 关注知名的刷题网站，如LeetCode、牛客网等，这些平台上有许多华为OD的历年真题和解析。
-
寻找系统性的教程：
- 学习一本经典的算法书籍，例如《算法导论》《剑指Offer》《编程之美》等。
- 完成系统的学习课程，例如数据结构与算法的在线课程。
积极心态与持续努力：
刷题的过程可能会比较枯燥，但它能够显著提升编程能力和算法思维。无论是为了通过华为OD的招聘考试，还是为了未来的职业发展，这些积累都会成为重要的财富。
考试注意细节
-
本地编写代码
- 在本地 IDE（如 VS Code、PyCharm 等）上编写、保存和调试代码，确保逻辑正确后再复制粘贴到考试页面。这样可以减少语法错误，提高代码准确性。
-
调整心态，保持冷静
- 遇到提示不足或实现不确定的问题时，不必慌张，可以采用更简单或更有把握的方法替代，确保思路清晰。
-
输入输出完整性
- 注意训练和考试时都需要编写完整的输入输出代码，尤其是和题目示例保持一致。完成代码后务必及时调试，确保功能符合要求。
-
快捷键使用
- 删除行可用
Ctrl+D，复制、粘贴和撤销分别为Ctrl+C，Ctrl+V，Ctrl+Z，这些可以正常使用。 - 避免使用
Ctrl+S，以免触发浏览器的保存功能。
- 删除行可用
-
浏览器要求
- 使用最新版的 Google Chrome 浏览器完成考试，确保摄像头开启并正常工作。考试期间不要切换到其他网站，以免影响考试成绩。
-
交卷相关
- 答题前，务必仔细查看题目示例，避免遗漏要求。
- 每完成一道题后，点击【保存并调试】按钮，多次保存和调试是允许的，系统会记录得分最高的一次结果。完成所有题目后，点击【提交本题型】按钮。
- 确保在考试结束前提交试卷，避免因未保存或调试失误而丢分。
-
时间和分数安排
- 总时间：150 分钟；总分：400 分。
- 试卷结构：2 道一星难度题（每题 100 分），1 道二星难度题（200 分）。及格分为 150 分。合理分配时间，优先完成自己擅长的题目。
-
考试环境准备
- 考试前请备好草稿纸和笔。考试中尽量避免离开座位，确保监控画面正常。
- 如需上厕所，请提前规划好时间以减少中途离开监控的可能性。
-
技术问题处理
- 如果考试中遇到断电、断网、死机等技术问题，可以关闭浏览器并重新打开试卷链接继续作答。
- 出现其他问题，请第一时间联系 HR 或监考人员进行反馈。
祝你考试顺利，取得理想成绩！
原文地址：https://blog.csdn.net/m0_63168877/article/details/145280396
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！