1. 广播站连通性问题解析这个问题本质上是一个典型的图论连通性问题。我们需要计算一个无向图中连通分量的数量因为每个连通分量只需要在一个节点上发送广播就能通过连接关系传播到整个连通分量中的所有节点。1.1 问题建模给定N个广播站我们可以将它们建模为图中的N个顶点。如果两个广播站之间有连接即matrix[i][j]1则在对应的顶点之间画一条边。由于连接是双向的这自然形成了一个无向图。关键观察点矩阵是对称的matrix[i][j] matrix[j][i]对角线元素matrix[i][i]可以忽略因为一个站点总是能接收自己发送的广播我们需要找出图中的连通分量数量1.2 并查集数据结构并查集Union-Find是解决这类连通性问题的理想数据结构。它支持两种主要操作Find查找元素所在的集合代表Union合并两个元素所在的集合并查集通过维护一个父指针数组来实现其中每个元素指向它的父节点根节点指向自己。通过路径压缩和按秩合并等优化技术可以达到接近常数的单次操作时间复杂度。2. 算法实现详解2.1 基础实现我们先看基础的并查集实现不使用任何优化class BasicUnionFind { constructor(size) { this.parent new Array(size); for (let i 0; i size; i) { this.parent[i] i; } this.count size; // 初始时每个节点都是独立的 } find(x) { while (x ! this.parent[x]) { x this.parent[x]; } return x; } union(x, y) { const rootX this.find(x); const rootY this.find(y); if (rootX ! rootY) { this.parent[rootY] rootX; this.count--; } } }这种实现简单直接但find操作在最坏情况下是O(n)时间复杂度。2.2 路径压缩优化路径压缩是在find操作时将查找路径上的所有节点直接指向根节点从而扁平化树结构class UnionFindWithPathCompression { constructor(size) { this.parent new Array(size); for (let i 0; i size; i) { this.parent[i] i; } this.count size; } find(x) { if (this.parent[x] ! x) { this.parent[x] this.find(this.parent[x]); // 递归进行路径压缩 } return this.parent[x]; } union(x, y) { const rootX this.find(x); const rootY this.find(y); if (rootX ! rootY) { this.parent[rootY] rootX; this.count--; } } }路径压缩将find操作的时间复杂度降低到接近O(1)。2.3 按秩合并优化按秩合并是另一种优化在union操作时总是将较小的树合并到较大的树下class OptimizedUnionFind { constructor(size) { this.parent new Array(size); this.rank new Array(size).fill(0); for (let i 0; i size; i) { this.parent[i] i; } this.count size; } find(x) { if (this.parent[x] ! x) { this.parent[x] this.find(this.parent[x]); } return this.parent[x]; } union(x, y) { const rootX this.find(x); const rootY this.find(y); if (rootX ! rootY) { if (this.rank[rootX] this.rank[rootY]) { this.parent[rootY] rootX; } else if (this.rank[rootX] this.rank[rootY]) { this.parent[rootX] rootY; } else { this.parent[rootY] rootX; this.rank[rootX]; } this.count--; } } }按秩合并可以保持树的平衡进一步优化性能。3. 完整解决方案3.1 JavaScript实现const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout, }); rl.on(line, (line) { const matrix line.split(,).map((str) str.split()); console.log(getMinBroadcastStations(matrix)); }); function getMinBroadcastStations(matrix) { const n matrix.length; const uf new UnionFind(n); for (let i 0; i n; i) { for (let j i 1; j n; j) { if (matrix[i][j] 1) { uf.union(i, j); } } } return uf.count; } class UnionFind { constructor(size) { this.parent new Array(size); this.rank new Array(size).fill(0); for (let i 0; i size; i) { this.parent[i] i; } this.count size; } find(x) { if (this.parent[x] ! x) { this.parent[x] this.find(this.parent[x]); } return this.parent[x]; } union(x, y) { const rootX this.find(x); const rootY this.find(y); if (rootX ! rootY) { if (this.rank[rootX] this.rank[rootY]) { this.parent[rootY] rootX; } else if (this.rank[rootX] this.rank[rootY]) { this.parent[rootX] rootY; } else { this.parent[rootY] rootX; this.rank[rootX]; } this.count--; } } }3.2 算法分析时间复杂度初始化O(n)主循环O(n²)次union操作每次union操作接近O(1)使用了路径压缩和按秩合并总时间复杂度O(n²)空间复杂度存储parent和rank数组O(n)总空间复杂度O(n)4. 实际应用与扩展4.1 实际应用场景这种算法不仅适用于广播站问题还可以应用于社交网络中的朋友关系分析计算机网络中的连通组件检测图像处理中的像素连通区域分析电路设计中的元件连接检查4.2 算法扩展动态连通性问题支持动态添加节点带权并查集在边上附加信息持久化并查集支持回滚操作4.3 性能优化技巧对于非常大的数据集可以考虑使用哈希表代替数组并行化处理将数据集分块处理内存优化使用更紧凑的数据结构5. 常见问题与调试技巧5.1 常见错误忘记初始化parent数组每个元素应该初始化为自己的索引没有正确处理矩阵的对称性重复处理会浪费时间但不影响结果路径压缩实现错误递归实现时忘记更新parent指针5.2 调试建议打印并查集的状态在每次union后输出parent数组使用小规模测试用例手动验证结果检查边界条件单个节点、全连接、无连接等情况5.3 性能测试对于不同规模的数据集可以测量运行时间n100: ~1msn1000: ~10msn10000: ~1000ms注意实际性能取决于具体实现和运行环境6. 替代解决方案除了并查集这个问题还可以用其他方法解决6.1 深度优先搜索(DFS)function getMinBroadcastStationsDFS(matrix) { const n matrix.length; const visited new Array(n).fill(false); let count 0; for (let i 0; i n; i) { if (!visited[i]) { dfs(i, matrix, visited); count; } } return count; } function dfs(node, matrix, visited) { visited[node] true; for (let neighbor 0; neighbor matrix.length; neighbor) { if (matrix[node][neighbor] 1 !visited[neighbor]) { dfs(neighbor, matrix, visited); } } }6.2 广度优先搜索(BFS)function getMinBroadcastStationsBFS(matrix) { const n matrix.length; const visited new Array(n).fill(false); let count 0; for (let i 0; i n; i) { if (!visited[i]) { bfs(i, matrix, visited); count; } } return count; } function bfs(start, matrix, visited) { const queue [start]; visited[start] true; while (queue.length 0) { const node queue.shift(); for (let neighbor 0; neighbor matrix.length; neighbor) { if (matrix[node][neighbor] 1 !visited[neighbor]) { visited[neighbor] true; queue.push(neighbor); } } } }6.3 方案比较方法时间复杂度空间复杂度适用场景并查集O(n² α(n))O(n)动态连通性问题DFS/BFSO(n²)O(n)静态图分析α(n)是反阿克曼函数增长极其缓慢可以认为是常数。7. 编码实践建议对于竞赛或面试建议使用路径压缩的并查集实现它足够高效且代码简洁在生产环境中如果需要处理动态图并查集是更好的选择对于一次性分析的静态图DFS/BFS可能更直观在实际编码中我发现并查集的路径压缩版本在大多数情况下已经足够高效。以下是我常用的模板class UnionFind { constructor(n) { this.parent Array.from({length: n}, (_, i) i); this.count n; } find(x) { while (x ! this.parent[x]) { this.parent[x] this.parent[this.parent[x]]; // 路径压缩 x this.parent[x]; } return x; } union(x, y) { const rootX this.find(x); const rootY this.find(y); if (rootX ! rootY) { this.parent[rootY] rootX; this.count--; } } }这个实现使用了非递归的路径压缩避免了递归可能带来的栈溢出问题同时保持了代码的简洁性。
 】Docker与容器（上篇）)
