Coding

You can find all the definitions here in the book "Introduction to graph theory", Douglas.B West. Important graph algorithms : 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 white). Algorithm itself is really simple : dfs ( v ): color [ v ] = gray for u in adj [ v ]: if color [ u ] == white then dfs ( u ) color [ v ] = black Black color here is not used, but you can use it sometimes. Time complexity : O ( n  +  m ) . DFS tree DFS tree is a rooted tree that is built like this : let T be a new tree dfs ( v ): color [ v ] = gray for u in adj [ v ]: if color [ u ] == white then dfs ( u ) and par [ u ] = v ( in T ) color [ v ] = black Lemma: There is no cross edges, it means if there is an edge