Last active
February 18, 2021 17:39
-
-
Save trykhov/fb25d21f2a347e73166a58aca6616d9d to your computer and use it in GitHub Desktop.
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 our adjacency matrix is {A: [B, C, D], B:[D, E], ...} | |
| // assuming that our vertices have the following properties: | |
| // 1. (boolean) visited | |
| // 2. (boolean) explore | |
| function cyclicGraphDetection(adj) { | |
| // get all the vertices from the adjacency matrix | |
| let vertices = Object.keys(adj); | |
| // look through all the vertices in the graph | |
| for(let vertex of vertices) { | |
| // only do unvisited nodes | |
| if(!vertex.visited) { | |
| // determine if there's a cycle from any path starting from vertex | |
| let cycleDetected = dfsCycleDetect(adj, vertex); | |
| // if there's a cycle, terminate program and return true | |
| if(cycleDetected) return true; | |
| } | |
| } | |
| // no cycle detected | |
| return false; | |
| } | |
| // our DFS helper function | |
| function dfsCycleDetect(adj, node) { | |
| // base case | |
| // if the node has been visited, that means there are no cycles | |
| if(node.visited) return false; | |
| // if we're on a current path and we come across a node that is currently being explore, there's a cycle | |
| if(node.explore) return true; | |
| // mark the node as being explored | |
| node.explore = true; | |
| let neighbors = adj[node]; | |
| for(let neighbor of neighbors) { | |
| if(!neighbor.visited) { | |
| let cycleDetected = dfsCycleDetect(adj, neighbor); | |
| // if the neighbor being explored is already marked as explored, then we come across a cycle | |
| if(cycleDetected) return true; | |
| } | |
| } | |
| // if we break out here, then we have not found a cycle on any path from this node | |
| node.explore = false; | |
| node.visited = true; | |
| return false; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment