Directed cycles
Kahn's algorithm, the topological sort that keeps taking a vertex with no edges left into it, comes to a stop when some vertices wait for each other in a circle. A depth-first search can find out whether a directed graph has a cycle, and print the cycle when it has one.
A directed cycle is a path that follows edges in their direction and returns to the vertex where it began. In the graph with the edges , , , and , the path is a directed cycle. A graph with a directed cycle has no topological order. Whichever vertex of the cycle comes first in a list, the cycle has an edge into it from a vertex that comes later.
A directed graph without a directed cycle is called a directed acyclic graph, or DAG. Cycles are the only thing that can prevent a topological order: every DAG has one, and Kahn's algorithm finds it.
To see why, suppose the algorithm has stopped and some vertices are left. Each of them still has a count above 0, so each has an edge into it from another vertex that is left. Start at any of them and keep stepping backwards along such an edge. The graph is finite, so this walk must come to a vertex it has already visited, and the part of the walk between the two visits is a directed cycle. In a DAG, then, no vertex can be left.
The vertices Kahn's algorithm cannot take
The figure shows Kahn's algorithm on the five-vertex graph at the moment it stops:
Four vertices are left, which tells us that the graph has a cycle. It does not tell us where the cycle is. Vertex 4 is left over too, although it is not on the cycle: it waits for vertex 3, which is. To find the cycle itself we use DFS.
Three states in a depth-first search
During a depth-first search every vertex is in one of three states. A vertex is unseen until the search enters it, active while its call is running, and finished once its call has returned. The active vertices are the ones whose calls are still open: apart from the vertex the search is at now, each of them is waiting for a call it made to return. Each of those calls was made along an edge, so the active vertices form a directed path, from the vertex where the search started to the vertex it is at now.
Suppose the search is at a vertex and looks at an edge . What happens next depends on the state of :
- If is unseen, the search enters it.
- If is active, the graph has a cycle. Vertex is on the current path, so the path from down to followed by the edge returns to .
- If is finished, the edge is skipped. The search finishes every unseen vertex it enters and stops as soon as it meets an active one, so a vertex becomes finished only when each of its edges leads to a finished vertex. Following edges from one at a time, every vertex that can be reached from is finished as well. Vertex is active, so it cannot be reached from , and this edge is not part of a cycle.
In the five-vertex graph, a search from vertex 0 enters 1, 2 and 3 in turn. At vertex 3 it looks at the edge and finds vertex 1 active:
- active: on the path from vertex 0
- the edge that reaches an active vertex
The active vertices are 0, 1, 2 and 3, in the order the search entered them. The cycle is the part of this path from vertex 1 onwards, , closed by the edge . Vertex 0 is active as well, but it comes before vertex 1 on the path and is not on the cycle.
Two states, seen and unseen, are not enough for this test. Take three vertices with the edges , and . A search from 0 enters 1, then 2, and returns to 0, where the edge leads to a vertex that has been seen before. This graph has no cycle. The two edges into vertex 2 are two routes to the same place. With three states the search finds vertex 2 finished and moves on.
If the graph has a cycle, the search is sure to report one. It starts again from every vertex left unseen, so it enters some vertex of the cycle; call the first one it enters . At that moment every other vertex of the cycle is unseen.
A call does not return until it has entered every vertex it can reach through vertices that were unseen when the call began. So while is still active, the search enters the rest of the cycle, including the vertex just before , and the edge from that vertex finds active. If the search meets some other active vertex first, it reports that cycle instead.
Print the cycle
Many problems ask for the cycle itself and not only for a yes or a no. CSES Round Trip II is one. We saw that the cycle is the end of the current path, from to . To be able to walk that stretch, the search records for every vertex its parent, the vertex from which it was entered. When it finds an edge with active, it starts at and follows parents until it reaches . That lists the cycle backwards, so the list is reversed at the end.
In the example the edge is . The parent of 3 is 2 and the parent of 2 is 1, which gives 3, 2, 1. Reversed, and closed by repeating the first vertex, the cycle is 1, 2, 3, 1.
UNSEEN, ACTIVE, FINISHED = 0, 1, 2
def find_cycle(n, graph):
state = [UNSEEN] * n
parent = [-1] * n
def visit(u): # returns a cycle, or [] if it finds none
state[u] = ACTIVE
for v in graph[u]:
if state[v] == ACTIVE: # the edge u -> v closes a cycle
cycle = [u]
while cycle[-1] != v:
cycle.append(parent[cycle[-1]])
cycle.reverse() # now v, ..., u
return cycle + [v]
if state[v] == UNSEEN:
parent[v] = u
cycle = visit(v)
if cycle:
return cycle
state[u] = FINISHED
return []
for start in range(n):
if state[start] == UNSEEN:
cycle = visit(start)
if cycle:
return cycle
return []
print(find_cycle(5, [[1], [2], [3], [1, 4], []]))
print(find_cycle(5, [[1], [2], [3], [4], []]))The first call is the five-vertex graph. The second is the same graph without the edge .
The function returns the cycle as a list that starts and ends with the same vertex, or an empty list when the graph has no cycle, so it answers the yes-or-no question as well. The loop at the bottom starts a search from every vertex that is still unseen, because one search only reaches the vertices that can be reached from its starting vertex. An edge from a vertex to itself is reported as a cycle of one vertex, since the vertex is active when the search looks at its own edge.
The search is recursive, and a path of 2000 vertices needs 2000 nested calls. Python allows about 1,000 by default, so on a chain of 2000 courses this function stops with a RecursionError. For a large graph, raise the limit with sys.setrecursionlimit before the search.
A topological order from the same search
On a graph without a cycle, the same search can produce a topological order, which gives us a second method beside Kahn's algorithm. We keep a list, and we add each vertex to it at the moment the vertex becomes finished. This finish order is called a postorder. When every vertex is finished, the list read backwards is a topological order.
This works because for every edge , vertex gets into the list before does. When the search at looks at the edge, cannot be active, since the graph has no cycle. If is finished, it is in the list already. If is unseen, the search enters it and finishes it before it comes back to . So in the list every edge points from a later vertex to an earlier one, and in the reversed list every edge points from an earlier vertex to a later one.
On the four courses, the search from 0 enters 1 and then 3. Course 3 has no outgoing edge, so it finishes first, and then course 1 finishes. Back at course 0, the search enters 2, finds 3 finished, and finishes 2. Course 0 finishes last. The list is 3, 1, 2, 0, and read backwards it is 0, 2, 1, 3.
Check for a cycle and sort in one search
The function below does both jobs. It returns a topological order, or an empty list if the search reaches an active vertex, so it solves both Course Schedule and Course Schedule II.
UNSEEN, ACTIVE, FINISHED = 0, 1, 2
def dfs_order(n, graph):
state = [UNSEEN] * n
finished = []
def visit(u): # returns False when it finds a cycle
state[u] = ACTIVE
for v in graph[u]:
if state[v] == ACTIVE:
return False
if state[v] == UNSEEN and not visit(v):
return False
state[u] = FINISHED
finished.append(u)
return True
for start in range(n):
if state[start] == UNSEEN and not visit(start):
return []
return finished[::-1]
graph = [[1, 2], [3], [3], []]
print(dfs_order(4, graph))
graph[3].append(0) # add the edge 3 -> 0
print(dfs_order(4, graph))The first call sorts the four courses. The second adds the edge .
In the second call the search goes from course 0 to 1 to 3, finds course 0 active at the edge , and returns an empty list.
Step through the search
The widget runs this search on the four courses when it is switched to DFS colours. It draws unseen vertices white, active ones grey and finished ones black. Under the graph it lists the open calls, which are the active vertices, and the vertices finished so far. Pressing Add the edge 3 → 0 makes the search stop at an active vertex. The other mode runs Kahn's algorithm by hand on the same graph, where the extra edge leaves no vertex to begin with.
Cost of the two cycle checks
- DFS with three states
time - Each vertex becomes active once and finished once, and each edge is looked at once, from the vertex it starts at.
- Printing the cycle
more - The walk along the parents visits each vertex of the cycle once.
- Kahn's algorithm
time - One run of the algorithm, then one comparison of the length of the order with .
- Memory
- The adjacency lists hold every edge. The states, the parents and the nested calls take at most one entry per vertex.
Kahn's algorithm or DFS
Both methods take the same time, and either one solves the Course Schedule problems. Kahn's algorithm has no recursion, and it lets us choose which available vertex goes next: taking the smallest one each time, with a min-heap, gives the smallest order in dictionary order. DFS is the method to use when the cycle has to be printed. Kahn's algorithm leaves behind the cycle together with every vertex that waits on it, and picking the cycle out of them would take a second search.
Everything on this page is about directed graphs. In an undirected graph the test is different, because the edge back to the vertex we came from must not count as a cycle: there, a neighbor the search has already entered, other than the parent, proves a cycle. The Union-find lesson gives another way to handle that case.
Common mistakes in cycle detection
Starting the search from vertex 0 only.
- Where it breaks
- Take three vertices with the edges and and no edge at vertex 0. The search from 0 finishes at once and reports no cycle, and the graph has the cycle .
- The fix
- Start a search from every vertex that is still unseen.
Printing the whole active path as the cycle.
- Where it breaks
- In the five-vertex graph the active path is 0, 1, 2, 3 when the edge is found. Printing all four vertices includes vertex 0, and the graph has no edge from 3 to 0.
- The fix
- Follow parents from only until is reached. The cycle is 1, 2, 3.
Reversing the finish list of a graph that has a cycle.
- Where it breaks
- On the four courses with the edge added, a search that only marks vertices as seen finishes them in the order 3, 1, 2, 0 and returns 0, 2, 1, 3. That list has course 0 before course 3, against the edge .
- The fix
- Keep the three states, and return no order as soon as an edge reaches an active vertex.
Recall A graph has four vertices and the adjacency lists `[[1, 2], [3], [1], [2]]`. Which edge does the search from vertex 0 find that closes a cycle, and what does `find_cycle` return?
The search enters 0, then 1, then 3, then 2. At vertex 2 it looks at the edge and finds vertex 1 active. The parents lead from 2 to 3 to 1, so the function returns [1, 3, 2, 1]. Vertex 0 is active too, but it is not part of the cycle.