fun validPath(n: Int, edges: Array<IntArray>, source: Int, destination: Int): Boolean {
val graph = buildGraph(edges)
// return dfs(graph, source, destination, hashSetOf<Int>())
return bfs(graph, source, destination)
}
private fun buildGraph(edges: Array<IntArray>): HashMap<Int, HashSet<Int>> {
val graph = hashMapOf<Int, HashSet<Int>>()
for (edge in edges) {
if (!graph.containsKey(edge[0])) graph[edge[0]] = hashSetOf<Int>()
if (!graph.containsKey(edge[1])) graph[edge[1]] = hashSetOf<Int>()
graph[edge[0]]!!.add(edge[1])
graph[edge[1]]!!.add(edge[0])
}
return graph
}
private fun dfs(graph: HashMap<Int, HashSet<Int>>, x: Int, destination: Int, visited: HashSet<Int>): Boolean {
if (visited.contains(x)) return false
if (x == destination) return true
visited.add(x)
graph[x]?.forEach { adj ->
if (dfs(graph, adj, destination, visited)) return true
}
return false
}
fun bfs(g: HashMap<Int, HashSet<Int>>, s: Int, d: Int): Boolean {
val q = ArrayDeque<Int>()
val visited = HashSet<Int>()
q.addLast(s)
visited.add(s)
while (q.isNotEmpty()) {
val node = q.removeFirst()
if (node == d) return true
val adjSet = g.getOrDefault(node, emptySet())
for (adj in adjSet) {
if (adj in visited) continue
q.addLast(adj)
visited.add(adj)
}
}
return false
}
- Time Complexity:
O(|V| + |E|).
- Space Complexity:
O(|V| + |E|).