Linux发行版的数量(图的遍历)

题目描述

Linux 操作系统有多个发行版，distrowatch.com 提供了各个发行版的资料。这些发行版互相存在关联，例如 Ubuntu 基于Debian 开发，而 Mint 又基于 Ubuntu 开发，那么我们认为 Mint 同 Debian 也存在关联。发行版集是一个或多个相关存在关联的操作系统发行版，集合内不包含没有关联的发行版。给你一个 n * n 的矩阵 isConnected，其中 isConnected[i][j] = 1 表示第 i 个发行版和第 j 个发行版直接关联，而 isConnected[i][j] = 0 表示二者不直接相连。

返回最大的发行版集中发行版的数量。

输入描述

第一行输入发行版的总数量N，

之后每行表示各发行版间是否直接相关

输出描述

输出最大的发行版集中发行版的数量

备注

1≤N≤200

示例一

输入

4
1 1 0 0
1 1 1 0
0 1 1 0
0 0 0 1

输出

3

说明Debian(1) 和 Unbuntu(2) 相关Mint(3) 和 Ubuntu(2) 相关，EeulerOS(4) 和另外三个都不相关，所以存在两个发行版集，发行版集中发行版的数量分别是3和1，所以输出3。

分析

这个问题是求图的连通分量中节点数最多的那个，也就是求图的最大连通子图的大小。我们可以用深度优先搜索(DFS)或者广度优先搜索(BFS)来解决。具体来说，我们首先遍历每一个节点，如果这个节点没有被访问过，那么我们就从这个节点出发，进行一次深度优先搜索或者广度优先搜索，每访问到一个节点，我们就把这个节点标记为已访问，同时计数器加1，然后再去访问所有与它直接相连并且还没有被访问过的节点。这样，当一次深度优先搜索或者广度优先搜索结束之后，我们就得到了一个连通子图，而计数器的值就是这个连通子图的大小。我们在所有连通子图的大小中取最大的就是我们要求的答案。时间复杂度上，我们需要遍历所有的节点和边，因此时间复杂度是O(n^2)，其中n是节点的数量。空间复杂度上，我们需要一个长度为n的数组来存储每个节点的访问状态，因此空间复杂度是O(n)。这种基于深度优先搜索或者广度优先搜索的算法很实用，因为它可以用于解决各种图的问题，比如求图的连通分量数量，求图的最大连通子图，检测图是否存在环等等。只要我们能够正确地构建出图，并且正确地实现深度优先搜索或者广度优先搜索，就可以很容易地解决这些问题。

解法

广度优先遍历

function bfs(arr,n){

    //创建存储节点的数组 nodes，下标作为节点名称，数值表示是否被访问 0 未访问， 1 已访问

    let nodes = new Array(n).fill(0);

    //创建一个二维数组result,每个元素表示一个连通分量，值表示连通分量中的节点

    let result = [];

    //创建一个队列queue，辅助顶点进行广度优先遍历，使用push,shift

    let queue = [];

    for(let i = 0;i0){

                //获取队列头部的节点

                let tmp = queue.shift();

                //遍历联系的节点

                for(let j=tmp+1;j{

        if(length