图论DFS函数在无向图两点路径验证问题中的作用问询

问题背景 #

我正在学习图（Graphs）和深度优先搜索（DFS），遇到如下图论问题：给定一个含n个顶点的无向图，顶点编号为0到n-1，边由二维数组edges表示，edges[i] = [ui, vi]表示顶点ui和vi间的无向边，要求判断从source顶点到destination顶点是否存在有效路径，存在则返回true，否则返回false。

示例1 #

Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2

输出：true，解释：从顶点0到2有两条路径：0→1→2、0→2。

示例2 #

Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5

输出：false，解释：从顶点0到5无有效路径。

Kotlin解决方案代码 #

fun validPath(n: Int, edges: Array<IntArray>, source: Int, destination: Int): Boolean {
    val graph = buildGraph(n, edges)
    val seen = HashSet<Int>().also{
        it.add(source)
    }
    
    return dfs(seen, source, destination, graph)
}

private fun dfs(seen: HashSet<Int>, cur: Int, end: Int, graph: List<HashSet<Int>>): Boolean{
    if(cur == end){
        return true
    }
    
    //checks to see if the path is valid
    for (next in graph[cur]){
        if(seen.add(next))
            if(dfs(seen, next, end, graph))
                return true
    }
    return false
}

private fun buildGraph(n: Int, edges: Array<IntArray>): List<HashSet<Int>>{
    val graph = MutableList(n){ hashSetOf<Int>() }
    
    for((u, v) in edges){
        graph[u].add(v)
        graph[v].add(u)
    }
    
    return graph
}

DFS函数的具体作用 #

这个DFS函数核心就是验证从当前节点到目标节点是否存在有效路径，具体工作逻辑如下：

• 终止条件判断：首先检查当前节点cur是否就是目标节点end，如果是直接返回true，说明找到有效路径。
• 遍历邻接节点：遍历当前节点的所有邻接节点next，通过seen.add(next)判断该节点是否未被访问过（HashSet的add方法仅在元素不存在时返回true）。
• 递归探索路径：如果邻接节点未被访问，就递归调用DFS函数探索该节点的路径。如果递归返回true，说明从这个邻接节点能到达目标节点，直接向上返回true。
• 回溯处理：如果当前节点的所有邻接节点都遍历完且都无法到达目标节点，就返回false，表示从当前节点出发没有有效路径到目标节点。

简单来说，它通过深度优先的方式，沿着一条路径走到头，走不通就回溯换另一条路径，全程用seen集合记录已访问节点，避免重复遍历和循环，最终判断起始节点与目标节点是否连通。

内容的提问来源于stack exchange，提问作者OEThe11