Graph Theory

DFS

The most useful graph algorithms are search algorithms. DFS (Depth First Search) is one of them.

While running DFS, we assign colors to the vertices (initially orange). Algorithm itself is really simple :

dfs (v):
        color[v] = gray
        for u in adj[v]:
                if color[u] == orange
                        then dfs(u)
        color[v] = dark_blue

Time complexity : O(n + m).