这个答案的dfs部分在整体功能中做了什么

Question

所以我正在学习图和DFS。我看到了这个涉及它的问题：

存在一个具有n个顶点的双向图，其中每个顶点被标记为从0到n-1(包括0到n-2(。图中的边表示为2D整数数组边，其中每个边[i]=[ui，vi]表示顶点ui和顶点vi之间的双向边。每个顶点对最多由一条边连接，没有一个顶点本身有边。

您需要确定是否存在从顶点源到顶点目标的有效路径。

给定边和整数n、source和destination，如果存在从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没有路径。

以下是解决问题的解决方案

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职能部门在这个特定问题上做了什么。函数是否正在检查该路径是否为有效路径？还是别的什么？感谢您抽出时间

Answer 1

我认为DFS函数中的注释解释了这一点，但您必须记住问题语句中的"有效路径"；定义。它检查您是否可以从当前节点到达目标节点。

它基本上是以DFS方式遍历图(总是在第一个相邻节点上递归调用(，并确保不会为已经访问的节点调用自己。

如果到达目标节点，则返回true。