【JavaScript算法实践】1. 无向图连通分量问题

本文主要是介绍【JavaScript算法实践】1. 无向图连通分量问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【JavaScript算法实践】无向图连通分量问题

1. 无向图连通分量
2. 不符合条件的情况
3. 连通分量计算
- 方法一：深度优先搜索（DFS）
- 方法二：广度优先搜索（BFS）
- 方法三：并查集
- 复杂度分析
4. 经典题目
- a. 岛屿问题
- b. 门墙问题

1. 无向图连通分量

在开发马尔可夫分析模型功能的过程中，遇到了一个计算前检验模型是否合格的问题。其中最主要的就是要检验图中是否存在单独的节点，即多个连通分量。
什么是连通分量？
通俗地讲，在无向图中，若所有节点都是连通的（即任意选定两个节点，都存在至少一条路使得两个节点连通），则该图有且仅有一个连通子图，即它本身。此时称该图的连通分量为1。这便是马尔可夫过程模型需要检验的条件。

2. 不符合条件的情况

存在独立的节点
上图存在了单独的节点

上图连通分量大于1

3. 连通分量计算

方法一：深度优先搜索（DFS）

深度优先搜索的思路是最直观的。遍历图中所有节点，对于每个节点，如果该节点尚未被访问过，则从该节点开始深度优先搜索，通过邻接矩阵 isConnected 得到与该节点直接相连的节点有哪些，这些节点和该节点属于同一个连通分量，然后对这些节点继续深度优先搜索，直到同一个连通分量的所有节点都被访问到，即可得到一个节点。遍历全部节点以后，即可得到连通分量的总数。

/*** DFS深度优先遍历计算连通分量数* @param isConnected : 邻接矩阵 (二维数组)* @returns circles:连通分量数* nodeNum:节点数量 visited:已访问节点集  */
var findCircleNum = function(isConnected) {const nodeNum = isConnected.length;const visited = new Set();let circles = 0;for (let i = 0; i < nodeNum; i++) {if (!visited.has(i)) {dfs(isConnected, visited, nodeNum, i);circles++;}}return circles;
};const dfs = (isConnected, visited, nodeNum, i) => {for (let j = 0; j < nodeNum; j++) {if (isConnected[i][j] == 1 && !visited.has(j)) {visited.add(j);dfs(isConnected, visited, nodeNum, j);}}
};

方法二：广度优先搜索（BFS）

也可以通过广度优先搜索的方法得到连通分量的总数。对于每个节点，如果该节点尚未被访问过，则从该节点开始广度优先搜索，直到同一个连通分量中的所有节点都被访问到，即可得到一个连通分量。

/*** BFS广度优先遍历计算连通分量数* @param isConnected : 邻接矩阵 (二维数组)* @returns circles:连通分量数* nodeNum:节点数量 visited:已访问节点集 */ 
var findCircleNum = function(isConnected) {const nodeNum  = isConnected.length;const visited = new Set();let circles = 0;const queue = new Array();for (let i = 0; i < nodeNum ; i++) {if (!visited.has(i)) {queue.push(i);while (queue.length) {const j = queue.shift();visited.add(j);for (let k = 0; k < nodeNum; k++) {if (isConnected[j][k] === 1 && !visited.has(k)) {queue.push(k);}}}circles++;}}return circles;
};

方法三：并查集

计算连通分量数的另一个方法是使用并查集。初始时，每个节点都属于不同的连通分量。遍历矩阵 isConnected，如果两个节点之间有相连关系，则它们属于同一个连通分量，对它们进行合并。

遍历矩阵 isConnected 的全部元素之后，计算连通分量的总数。

/*** 并查集 计算连通分量数* @param isConnected * @returns circles:连通分量数* nodeNum:节点数量 visited:已访问节点集 */
var findCircleNum = function(isConnected) {const nodeNum = isConnected.length;const parent = new Array(nodeNum).fill(0).map((element, index) => index);for (let i = 0; i < nodeNum; i++) {for (let j = i + 1; j < nodeNum; j++) {if (isConnected[i][j] == 1) {union(parent, i, j);}}}let circles = 0;parent.forEach((element, index) => {if (element === index) {circles++;}});return circles;
};
// 并操作
const union = (parent, index1, index2) => {parent[find(parent, index1)] = find(parent, index2);
}
// 查操作
const find = (parent, index) => {if (parent[index] !== index) {parent[index] = find(parent, parent[index]);}return parent[index];
}

复杂度分析

方法	时间复杂度	空间复杂度
深度优先DFS	O(n²)	O(n)
广度优先BFS	O(n²)	O(n)
并查集	O(n²logn)	O(n)
其中，n是节点数量。对于DFS和BFS，时间上都需要遍历邻接矩阵内的所有元素，即n²，空间上都需要一个长度为n的数组来标记已经访问过的节点。
对于并查集，时间上除了遍历邻接矩阵内的所有元素外，若存在相连关系，最多可能有2n²次查找，和log(n²)次合并。故最坏的情况下复杂度为O(2n²log(n²)) = O(n²logn)，空间上需要一个长度为n的数组来记录每个节点的祖先。