Depth-first search time =0 pre/post W 1/12Q Z W 7/)8 V DES tree 2/32021 Xiaojuan Cai 12
Depth-first search u w x y z u u u v v x y w z y x DFS tree w z time = 0 pre/post 1/ 2/ 3/ 4/5 10 11 12 6/ 7/8 9 2/3/2021 Xiaojuan Cai 12
DES tree: undirected 1/6Q 9 How to figure out back edges 2/5 o tree edge back edge W 4/10 DES tree 2/32021 Xiaojuan Cai
DFS tree: undirected • tree edge: • back edge: u v x y w z DFS tree 1/ 2/ 3/ 4/1 4 5 6 5/ 6/2 3 2/3/2021 Xiaojuan Cai 13 How to figure out back edges?
Algorithm 9.1 DFS Input: A directed or undirected graph G=(V, E) Output: Preordering and postordering of the vertices in the corresponding depth first tree 1.peh←0.potn←0 2. for each vertex v∈V 3. mark y unvisited 4. end for 5. for each vertex v∈V 6. if v is marked unvisited then dfs(v) Procedure dfsly 1. mark y visited 2. preen←- preen+1 for each edge()∈E 4. if w is marked unvisited then dfs( w) 5. end for 6. postdfn 4pastdfn +1 2/32021 Xiaojuan Cai 14
2/3/2021 Xiaojuan Cai 14
Algorithm 9.1 DFS Input: A directed or undirected graph G=(V,E) Output: Preordering and postordering of the vertices in the corresponding depth first tree 1价++4tme<-0 2. for each vertex v∈V 3. mark v united +vpre <-intint 4. end for ost <--infiniti 5. for each vertex v∈V 6. if v is marked unvisited then dfs( Procedure dfsly 1. mark y visited time <--time oredfi-+-predfi +2<F- vpre <--time for each edge()∈E 4. if w is marked unvisited then dfs( w) 5. end for time <--time 6. posture postur+1 v post <--time 2/32021 Xiaojuan Cai
time <-- time + 1 v.post <-- time time <-- time + 1 v.pre <-- time v.pre <-- infinity v.post <-- infinity time <-- 0 2/3/2021 Xiaojuan Cai 15
Quiz: Complexity Time Space Adj. Matrix Undirected Adj. List? 2/32021 Xiaojuan Cai 16
Quiz: Complexity Time Space Undirected Adj. Matrix ? ? Adj. List ? 2/3/2021 Xiaojuan Cai 16