SimuVedaAlgorithms Lab Open in the lab

Graphs / Intermediate

Detect a Cycle in a Directed Graph Visualizer

Colour nodes white (new), grey (on the current DFS path) and black (finished). Meeting a grey node again means you walked back into your own path: that edge closes a cycle. Meeting a black node is fine.

Start the Detect a Cycle in a Directed Graph simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(V + E)
Average timeO(V + E)
Worst timeO(V + E)
Extra spaceO(V)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Every node starts white. Run DFS from each white node.
  2. Visit A: colour it grey. It is on the current path.
  3. A → B: B is white, so go deeper.
  4. Visit B: colour it grey. It is on the current path.
  5. B → C: C is white, so go deeper.
  6. Visit C: colour it grey. It is on the current path.
  7. C → D: D is white, so go deeper.
  8. Visit D: colour it grey. It is on the current path.
  9. D → B leads back to grey B, which is on the current path. Cycle: B → C → D → B.
  10. The graph has a cycle, so no order can satisfy every edge.

Try it with your own input →

Detect a cycle in a directed graph in Java, Python, C++, C and JavaScript

boolean hasCycle(int u) {
  color[u] = GREY;
  for (int v : adj[u]) {
    if (color[v] == GREY) return true;
    if (color[v] == WHITE && hasCycle(v)) return true;
  }
  color[u] = BLACK;
  return false;
}
// try hasCycle(u) for every WHITE u
WHITE, GREY, BLACK = 0, 1, 2

def has_cycle(adj, color, u):
    color[u] = GREY
    for v in adj[u]:
        if color[v] == GREY:
            return True
        if color[v] == WHITE and has_cycle(adj, color, v):
            return True
    color[u] = BLACK
    return False

# try has_cycle(adj, color, u) for every WHITE u
enum { WHITE, GREY, BLACK };

bool hasCycle(const vector<vector<int>>& adj, vector<int>& color, int u) {
  color[u] = GREY;
  for (int v : adj[u]) {
    if (color[v] == GREY) return true;
    if (color[v] == WHITE && hasCycle(adj, color, v)) return true;
  }
  color[u] = BLACK;
  return false;
}
// try hasCycle(adj, color, u) for every WHITE u
#define MAXN 100
enum { WHITE, GREY, BLACK };
int adj[MAXN][MAXN], deg[MAXN], color[MAXN];

int hasCycle(int u) {
  color[u] = GREY;
  for (int k = 0; k < deg[u]; k++) {
    int v = adj[u][k];
    if (color[v] == GREY) return 1;
    if (color[v] == WHITE && hasCycle(v)) return 1;
  }
  color[u] = BLACK;
  return 0;
}
// try hasCycle(u) for every WHITE u
const WHITE = 0, GREY = 1, BLACK = 2;

function hasCycle(adj, color, u) {
  color[u] = GREY;
  for (const v of adj[u]) {
    if (color[v] === GREY) return true;
    if (color[v] === WHITE && hasCycle(adj, color, v)) return true;
  }
  color[u] = BLACK;
  return false;
}
// try hasCycle(adj, color, u) for every WHITE u

In an interview

LeetCode 207 Course Schedule asks the same thing: does a directed graph have a cycle? Here with depth-first search and three colours.

Two colours are not enough in a directed graph: reaching a finished (black) node from another branch is not a cycle. In an undirected graph, just skip the edge back to the parent.

More graphs