Posts

Showing posts from February, 2017

Algorithms

Image
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]= blackLemma: There is no cross edges, it means if there is an edge between v and u, then v = par[u] or u = par[v].
Starting time, finishing time Starting time of a vertex is the time we enter it (the…