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.
212 {
213 auto vertices =
graph.getVertices();
214
215
216
217
218
219
220
221
223
224
226
227
228
229 if (state[
node] == not_visited) {
230
232 return true;
233 }
234 }
235 }
236
237
238
239 return false;
240 }
static bool isCyclicDFSHelper(AdjList const &adjList, std::vector< nodeStates > *state, unsigned int node)
Definition cycle_check_directed_graph.cpp:170