资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

js怎么判断连通图

创作时间:

作者:

@小白创作中心

js怎么判断连通图

引用

来源

https://docs.pingcode.com/baike/3531569

在JavaScript中判断连通图的方法有：使用深度优先搜索（DFS）、广度优先搜索（BFS）、检查是否所有节点都被访问到。

深度优先搜索（DFS）是一种图遍历算法，能够有效地访问图中的每一个节点，并且在访问过程中记录已经访问过的节点。通过DFS遍历图，如果所有节点都被访问到，那么这个图就是连通的。下面将详细描述如何使用DFS来判断图的连通性。

一、深度优先搜索（DFS）

1、DFS的基本概念

深度优先搜索是一种遍历或搜索树或图的算法。算法会从一个起始节点开始，沿着路径尽可能深地搜索，然后回溯到上一个节点继续搜索其他路径。DFS可以用递归或栈来实现。

2、实现DFS遍历

在实现DFS遍历时，我们需要一个辅助数据结构（如数组）来记录哪些节点已经被访问过。以下是一个简单的JavaScript实现：

function dfs(graph, start, visited) {
    visited[start] = true;
    for (let neighbor of graph[start]) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor, visited);
        }
    }
}

3、判断连通图

要判断一个图是否连通，我们可以从一个任意的起点开始使用DFS遍历整个图，并检查是否所有节点都被访问到。以下是完整的实现：

function isConnected(graph) {
    let visited = new Array(graph.length).fill(false);
    dfs(graph, 0, visited);
    for (let i = 0; i < visited.length; i++) {
        if (!visited[i]) {
            return false;
        }
    }
    return true;
}
// 示例用法
let graph = [
    [1, 2],
    [0, 3],
    [0, 3],
    [1, 2]
];
console.log(isConnected(graph)); // 输出 true

在上述代码中，我们定义了一个isConnected函数，该函数接收一个图的邻接表表示作为参数。它会检查图中的所有节点是否都被访问过，如果有任何一个节点未被访问到，则该图不是连通图。

二、广度优先搜索（BFS）

1、BFS的基本概念

广度优先搜索是一种图遍历算法，它会从一个起始节点开始，首先访问所有相邻节点，然后再访问这些相邻节点的相邻节点。BFS通常用队列来实现。

2、实现BFS遍历

在实现BFS遍历时，我们需要一个队列来记录将要访问的节点，以及一个数组来记录已经访问过的节点。以下是一个简单的JavaScript实现：

function bfs(graph, start, visited) {
    let queue = [start];
    visited[start] = true;
    while (queue.length > 0) {
        let node = queue.shift();
        for (let neighbor of graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.push(neighbor);
            }
        }
    }
}

3、判断连通图

同样地，我们可以使用BFS遍历整个图并检查是否所有节点都被访问到。以下是完整的实现：

function isConnected(graph) {
    let visited = new Array(graph.length).fill(false);
    bfs(graph, 0, visited);
    for (let i = 0; i < visited.length; i++) {
        if (!visited[i]) {
            return false;
        }
    }
    return true;
}
// 示例用法
let graph = [
    [1, 2],
    [0, 3],
    [0, 3],
    [1, 2]
];
console.log(isConnected(graph)); // 输出 true

三、检查所有节点是否被访问到

1、基本概念

无论使用DFS还是BFS，我们都需要确保在遍历图的过程中所有节点都被访问到。如果有任何一个节点未被访问到，则该图不是连通图。

2、实现细节

在上面的实现中，我们通过一个布尔数组visited来记录每个节点是否被访问过，并在遍历结束后检查该数组中的所有元素。如果有任何一个元素为false，则说明该节点未被访问到。

3、优化建议

在实际应用中，如果图的节点数量非常大，我们可以在遍历过程中记录被访问到的节点数量，并在遍历结束后与图的总节点数量进行比较。如果两个数量相等，则说明所有节点都被访问到了。

function isConnected(graph) {
    let visited = new Array(graph.length).fill(false);
    let count = 0;
    function dfs(node) {
        visited[node] = true;
        count++;
        for (let neighbor of graph[node]) {
            if (!visited[neighbor]) {
                dfs(neighbor);
            }
        }
    }
    dfs(0);
    return count === graph.length;
}
// 示例用法
let graph = [
    [1, 2],
    [0, 3],
    [0, 3],
    [1, 2]
];
console.log(isConnected(graph)); // 输出 true

在上述代码中，我们通过一个计数器count来记录被访问到的节点数量，并在遍历结束后与图的总节点数量进行比较。如果两个数量相等，则说明所有节点都被访问到了。