mportant graph problems Path. Is there a directed path from s to t Shortest path. What is the shortest directed path from stot? Topological sort. Can you draw the digraph so that all edges point upwards Strong connectivity. Is there a directed path between all pairs of vertices Transitive closure For each vertices v and w is there a path from v to W 2/32021 Xiaojuan Cai
Important graph problems Path. Is there a directed path from s to t ? Shortest path. What is the shortest directed path from s to t ? Topological sort. Can you draw the digraph so that all edges point upwards? Strong connectivity. Is there a directed path between all pairs of vertices? Transitive closure. For each vertices v and w, is there a path from v to w ? 2/3/2021 Xiaojuan Cai 7
Where are we vertex Graph cle of length 5 path of Undirected graph length 4 degree 3 a DFS BFS, application Directed graph connected npo nents a DFS, BFS, Application 2/32021 Xiaojuan Cai
Where are we? • Graph • Undirected graph ‣ DFS, BFS, Application • Directed graph ‣ DFS, BFS, Application 2/3/2021 Xiaojuan Cai 8
DES Depth-first-search Unroll a ball of string behind you Mark each visited intersection and each visited passage e Retrace steps when no unvisited options 2/32021
DFS Depth-first-search. •Unroll a ball of string behind you. •Mark each visited intersection and each visited passage. •Retrace steps when no unvisited options. 2/3/2021 Xiaojuan Cai 9
Maze exploration 2/32021 Xiaojuan Cai 10
Maze exploration 2/3/2021 Xiaojuan Cai 10
Depth-first search pre/post =0/0 W 2/5 Z W V DES tree 2/32021 Xiaojuan Cai
Depth-first search u w x y z u u u v v x y w z y x DFS tree w z pre/post = 0/0 1/ 2/ 3/ 4/1 4 5 6 5/ 6/2 3 2/3/2021 Xiaojuan Cai 11