我们如何使用深度优先搜索来检查 2 个顶点是否连接？

Question

我无法理解dfs如何用于检查图中的两个顶点是否连接（不仅直接连接还可以间接连接）。

Answer 1

设两个顶点为source和destination。不失一般性，其中任何一个可以是source，另一个可以是destination。所以基本的想法是，你从 source 节点开始做一个 dfs，然后你保留一个数组来跟踪每个节点的状态（即它们是否已经被访问过）。当无法访问新节点时，dfs 将终止。如果source和destination确实是连通的，那么从source运行dfs之后，访问数组中destination节点的状态将被访问（已访问状态可以用 1 或 true 表示）或未访问（0 或 false）。如果它们已连接，则为 1 或 true，否则为 0。这不仅适用于 destination，而且适用于所有其他节点。

visited[n] --> n nodes, 0 to n - 1,  initialize with 0 or false values

dfs(source){
    visited[source] = true;
    for(node : adjacencyList[source]){
        if(!visited[node]){
            dfs(node);
        }
    }
}

connected(source){
    dfs(source);
    for(i = 0 ; i < n ; ++i){
        if(!visited[i]){
            // source and i are not connected
        }
    }
}