Check if a directed graph has a cycle or not.
This class provides 2 methods to check for cycle in a directed graph: isCyclicDFS & isCyclicBFS.
- isCyclicDFS uses DFS traversal method to check for cycle in a graph.
- isCyclidBFS used BFS traversal method to check for cycle in a graph.
static bool CycleCheck::isCyclicDFS |
( |
Graph const & |
graph | ) |
|
|
inlinestatic |
Driver function to check if a graph has a cycle.
This function uses DFS to check for cycle in the graph.
- Parameters
-
graph | which needs to be evaluated for the presence of cycle. |
- Returns
- true if a cycle is detected, else false.
State of the node.
It is a vector of "nodeStates" which represents the state node is in. It can take only 3 values: "not_visited", "in_stack", and "visited".
Initially, all nodes are in "not_visited" state.
213 auto vertices =
graph.getVertices();
229 if (state[
node] == not_visited) {