Graphs Part 5 Depth First Search One of the simplest algorithms for graph searching Very efficient Many applications Topological sort Strongly connected components Depth First Search DFS G u color WHITE for each vertex u NIL for each vertex time 0 if u color WHITE DFS Visit G u 1 2 3 4 5 6 7 8 9 10 DFS Visit G u 1 2 3 4 5 6 7 8 time time 1 u d time u color GRAY if v color WHITE for each vertex v u DFS Visit G v time time 1 9 10 u f time 11 u color BLACK Define the predecessor sub graph of G as where defines the Depth first forest 1 DFS G Running Example DFS for directed graph for each vertex u NIL for each vertex time 0 u color WHITE b a y x 2 7 5 3 6 4 c z if u color WHITE DFS Visit G u 8 9 10 a x b y c z Graph G adjacency list alphabetical DFS G 1 DFS G Running Example DFS for directed graph for each vertex u NIL for each vertex time 0 u color WHITE b a y x 7 2 5 3 6 4 c z if u color WHITE DFS Visit G u 8 9 10 a x b y c z Graph G adjacency list alphabetical DFS G Lines 1 5 1 DFS G Running Example DFS for directed graph for each vertex u NIL for each vertex time 0 u color WHITE a b x y 7 5 3 6 2 4 c z if u color WHITE DFS Visit G u 8 9 10 a x b y c z Graph G adjacency list alphabetical DFS G a is WHITE Running Example DFS for directed graph a x b y c z DFS Visit G u 1 2 3 4 5 6 7 8 time time 1 u d time u color GRAY if v color WHITE for each vertex v u DFS Visit G v time time 1 9 10 u f time 11 u color BLACK a x b y c z Graph G adjacency list alphabetical DFS Visit G a DFS G Running Example DFS for directed graph a 1 x b y c z DFS Visit G u 1 2 3 4 5 6 7 8 time time 1 u d time u color GRAY if v color WHITE for each vertex v u DFS Visit G v time time 1 9 10 u f time 11 u color BLACK a x b y c z Graph G adjacency list alphabetical DFS Visit G a Lines 1 3 DFS G Running Example DFS for directed graph a 1 x b y c z DFS Visit G u 1 2 3 4 5 6 7 8 time time 1 u d time u color GRAY if v color WHITE for each vertex v u DFS Visit G v time time 1 9 10 u f time 11 u color BLACK a x b y c z Graph G adjacency list alphabetical DFS Visit G a b is WHITE DFS G Running Example DFS for directed graph a 1 x b y c z DFS Visit G u 1 2 3 4 5 6 7 8 time time 1 u d time u color GRAY if v color WHITE for each vertex v u DFS Visit G v time time 1 9 10 u f time 11 u color BLACK a x b y c z Graph G adjacency list alphabetical DFS Visit G a Line 6 DFS G Running Example DFS for directed graph a 1 x b y c z DFS Visit G u 1 2 3 4 5 6 7 8 time time 1 u d time u color GRAY if v color WHITE for each vertex v u DFS Visit G v time time 1 9 10 u f time 11 u color BLACK a x b y c z Graph G adjacency list alphabetical DFS Visit G b DFS Visit G a DFS G Running Example DFS for directed graph a 1 x b 2 y c z DFS Visit G u 1 2 3 4 5 6 7 8 time time 1 u d time u color GRAY if v color WHITE for each vertex v u DFS Visit G v time time 1 9 10 u f time 11 u color BLACK a x b y c z Graph G adjacency list alphabetical DFS Visit G b Lines 1 3 DFS Visit G a DFS G Running Example DFS for directed graph a 1 x b 2 y c z DFS Visit G u 1 2 3 4 5 6 7 8 time time 1 u d time u color GRAY if v color WHITE for each vertex v u DFS Visit G v time time 1 9 10 u f time 11 u color BLACK a x b y c z Graph G adjacency list alphabetical DFS Visit G b y is WHITE DFS Visit G a DFS G Running Example DFS for directed graph a 1 x b 2 y c z DFS Visit G u 1 2 3 4 5 6 7 8 time time 1 u d time u color GRAY if v color WHITE for each vertex v u DFS Visit G v time time 1 9 10 u f time 11 u color BLACK a x b y c z Graph G adjacency list alphabetical DFS Visit G b Line 6 DFS Visit G a DFS G Running Example DFS for directed graph DFS Visit G u 1 2 3 4 5 6 7 8 time time 1 u d time u color GRAY if v color WHITE for each vertex v u DFS Visit G v time time 1 9 10 u f time 11 u color BLACK a 1 x b 2 y c z a x b y c z Graph G adjacency list alphabetical DFS Visit G y DFS Visit G b DFS Visit G a DFS G Running Example DFS for directed graph DFS Visit G u 1 2 3 4 5 6 7 8 time time 1 u d time u color GRAY if v color WHITE for each vertex v u DFS Visit G v time time 1 9 10 u f time 11 u color BLACK a x b y c z Graph G adjacency list alphabetical a 1 x b 2 3 y c z DFS Visit G y Lines 1 3 DFS Visit G b DFS Visit G a DFS G Running Example DFS for directed graph DFS Visit G u 1 2 3 4 5 6 7 8 time time 1 u d time u color GRAY if v color WHITE for each vertex v u DFS Visit G v time time 1 9 10 u f time 11 u color BLACK a x b y c z Graph G adjacency list alphabetical a 1 x b 2 3 4 y c z DFS Visit G y Lines 9 11 DFS Visit G b DFS …
View Full Document
Unlocking...