Created
May 15, 2020 00:59
-
-
Save trykhov/4e0ce5ebbc9910097c718ff5b41d234f to your computer and use it in GitHub Desktop.
DFS demo code
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // assuming that the input is an adjacency list | |
| // e.g adj = {A: [B,C], B:[D,F], ... } | |
| function dfs(adj, v, t) { | |
| // adj is the adjacency list | |
| // v is the node that's being visited | |
| // t is the final destination | |
| // these are the base cases | |
| // either reach the destination or has already been visited | |
| if(v === t) return true; | |
| if(v.visited) return false; | |
| // mark the node as visited | |
| v.visited = true; | |
| // explore all the neighbors of v | |
| for(let neighbor of adj[v]) { | |
| // if the neighbor hasn't been visited | |
| if(!neighbor.visited) { | |
| // go down the path & determine if t has been reached | |
| let reached = dfs(adj, neighbor, t); | |
| // return true if t has been reached | |
| if(reached) return true; | |
| } | |
| } | |
| // there is no path to t from v | |
| return false; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment