-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcyle-in-graph.js
More file actions
38 lines (30 loc) · 1.04 KB
/
Copy pathcyle-in-graph.js
File metadata and controls
38 lines (30 loc) · 1.04 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//CYCLE IN GRAPH
// time O(v + e) | O(v) space - where v is the number of vertices and e the number of edges in the graph
function cycleInGraph(edges) {
const numberOfNodes = edges.length;
const visitedVetices = new Array(numberOfNodes).fill(false);
const inStack = new Array(numberOfNodes).fill(false);
for (let node = 0; node < numberOfNodes; node++) {
if (visitedVetices[node]) continue;
const containsCycle = DFS(node, edges, visitedVetices, inStack);
if (containsCycle) return true;
}
return false;
}
function DFS(node, edges, visitedVertices, inStack) {
visitedVertices[node] = true;
inStack[node] = true;
const neighbors = edges[node];
for (const neighbor of neighbors) {
if (!visitedVertices[neighbor]) {
const containsCycle = DFS(neighbor, edges, visitedVertices, inStack);
if (containsCycle) return true;
} else if (inStack[neighbor]) {
return true;
}
}
inStack[node] = false;
return false;
}
const edges = [[1, 3], [2, 3, 4], [0], [], [2, 5], []];
console.log(cycleInGraph(edges));