华为机试练习（三）服务器广播

题目描述
服务器连接方式包括直接相连，间接连接。
A 和 B 直接连接， B 和 C 直接连接，则 A 和 C 间接连接。直接连接和间接连接都可以发送广播。
给出一个 N * N 数组，代表 N 个服务器， matrix[i][j] == 1 ，则代表 i 和 j 直接连接；
不等于 1 时，代表 i 和 j 不直接连接。 matrix[i][i]== 1 ，即自己和自己直接连接。
matrix[i][j]==matrix[j][i] 。
计算初始需要给几台服务器广播，才可以使侮个服务器都收到广播。

【分析】
实质是图的遍历，求连通分量的个数；
做这道题的时候没想到遍历该怎么写，用了比较麻烦的方法；
用一个 Set 存储一个连通分量，将它们保存到数组中，数组的长度就是连通分量的个数，即本题的答案；
具体做法是：遍历整个邻接矩阵，每遍历到新的一行，判断当前节点是否已经存在于某个已有的连通分量，如果有，将与其直接连接的节点存到该连通分量；如果没有，新建一个 Set （新连通分量）进行存储，最后得到整个连通分量的数组，用 Set 是保证没有重复，数组也可

【实现】

// 获取输入
const input = "[[1,0,1,0,1,1],[0,1,0,0,0,0],[1,0,1,0,0,0],[0,0,0,1,0,0],[1,0,0,0,1,0],[1,0,0,0,0,1]]"
// 转为数组
const arr = JSON.parse(input)

const len = arr.length
// 记录连通分量
const res = []
for (let i = 0; i < len; i++) {
    // 标记：判断当前节点是否已经被记录（已属于已有的某个连通分量）
    let flag = false

    // 当前所指向的连通分量
    let temp = null

    for (const x of res) {
        if (x.has(i)) {
            // 若在连通分量数组中找到，表示该节点已经与之前的节点连通，那么与该节点连通的节点，也与之前的节点间接连通
            temp = x
            flag = true
            break
        }
    }

    if (!flag) {
        // 如果未找到，则创建一个新的set：表示一个新的连通分量
        const set = new Set()
        set.add(i)
        res.push(set)
        temp = set
    }

    for (let j = i + 1; j < len; j++) {
    	// 邻接矩阵对称，所以从 i+1 开始
        if (arr[i][j] === 1) {
        	// i 与 j 直接连通，将 j 存储到 i 所属的连通分量中
            temp.add(j)
        }
    }
}

// 输出结果
console.log(res.length);

最后

以上就是阔达裙子为你收集整理的华为机试练习（三）服务器广播的全部内容，希望文章能够帮你解决华为机试练习（三）服务器广播所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。