What is the dfs part of this answer doing in the overall function?-CodePudding

So I'm learning Graphs and DFS. I saw this question that involved it:

There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

You want to determine if there is a valid path that exists from vertex source to vertex destination.

Given edges and the integers n, source, and destination, return true if there is a valid path from source to destination, or false otherwise.

Example 1:

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

Output: true: Explanation: There are two paths from vertex 0 to vertex 2:

0 → 1 → 2
0 → 2

Example 2:

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

Output: false: Explanation: There is no path from vertex 0 to vertex 5.

Here's a solution that solves the question

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
    
}

I would like to know what the DFS function is doing in this particular question. Is the function checking to see if that path is a valid path? or something else? Thank you for your time

CodePudding user response：

I think the comment in the DFS function explains it, but you must remember the problem statement where a "valid path" is defined. It's checking if you can reach the target node from the current node.

It's basically traversing the graph in DFS fashion (always call recursively on the first neighboring node) and makes sure not to call itself for a node is has already visited.

If it reached the target node, it returns true.