Depth-first search is a general technique to explore a graph from a certain start vertex $s$. We imagine the mythical Greek hero Theseus starting to walk from $s$, carrying behind him a thread that his lover Ariadne has given him. When at a vertex $u$, Theseus progresses to a neighbor $v$, further unfurling the thread. He marks every visited vertex with chalk to remember where he has already been. When running in a dead end (either no outgoing edges or all outgoing edges go to vertices already carrying a chalk mark), he goes back where he came from, furling up the thread. When coming back to a vertex $u$, he proceeds to the next neighbor $v$ that he has not already visitied. So he additionally writes down, at each vertex $u$, the number of out-edges from $u$ he has already taken (this part is missing in the Greek legend, as far as I know). When he is back to $s$ and $s$ itself has no further unexplored out-neighbors, he completely furls up the rope and terminates. He has explored all vertices reachable from $s$.

There are several variants how to implement depth-first search. Some use recursion; others immediately throw all out-neighbors no the stack. I like the one where the stack really represents Ariadne's threads and Theseus uses a counter at every vertex because in my opinion it is the most explicit. I think in the case of depth-first search, using recursion really obscures how things work.

Here is my python code:


debug_mode = True 

def debug_print(s):
    if debug_mode:
        print(s)
    

def dfs(start_vertex, graph):
    
    visited = {} # the set of vertices that are or have been on the stack 
    number_of_visited_out_edges = {} # for each vertex u, the number of outgoing edges (u,v) we have looked at 

    for u in graph:
        number_of_visited_out_edges[u] = 0
        visited[u] = False 

    stack = [start_vertex] # this is a path starting at start_vertex
    visited[start_vertex] = True

    while (len(stack) > 0):
        u = stack[-1] # top element of the stack
        i = number_of_visited_out_edges[u] # what is the next unexplored edge out of u?
        if i == len(graph[u]): # then all out-edges of u have already been explored
            stack.pop() # remove u from stack, i.e., backtrack 
            debug_print(f"popping {u} from the stack")
        else: 
            v = graph[u][i] # edge (u,v) is the next unexplored out-edge of u 
            number_of_visited_out_edges[u] += 1 
            debug_print(f"taking edge {(u,v)}")
            if not visited[v]:
                stack.append(v) # advancing the depth-first search 
                visited[v] = True 
                debug_print(f"pusing {v} onto stack")
            else:
                debug_print(f"{v} already visited")

The complete program that reads the graph in "ICPC format" plus a start vertex is in generic-dfs-digraph.py. Save it an use it with input digraph-6-8-start-at-1.txt:

generic-dfs-digraph < digraph-6-8-start-at-1.txt                    
[lots of output]

Reachability

Reachability is the problem of determining which vertices are reachable from a given start vertex. For example, in the graph

the vertices reachable from start vertex $4$ are (in ascending order): $2, 3, 4, 6$. The other vertices $1$ and $5$ are not reachable.

Problem (Vanilla Reachability) Given a directed graph and a start vertices $s$, determine the set of vertices that can be reached from $s$.

Input: The first line contains two integers $n$ and $m$, the number of vertices and edges of the graph. The next $m$ lines each contain two integers $u$ and $v$, indicating that $(u,v)$ is an edge. The final line contains a single integer $s$, the start node.

Output: A total of $n$ lines, line $i$ ($1 \leq i \leq n$) containing the words "$i$ reachable" or "$i$ not reachable".

Sample Input

Sample Output

1 not reachable     
2 reachable 
3 reachable 
4 reachable 
5 not reachable 
6 reachable