《算法设计》课程教学资源（PPT课件讲稿）Lecture 6 Graph Traversal

Lecture 6 Graph Traversal Graph Undirected graph Directed graph 2/32021 Xiaojuan Cai

• Graph • Undirected graph • Directed graph Lecture 6 Graph Traversal 2/3/2021 Xiaojuan Cai 1

Overview Graph Undirected graph a DFS BFS, application Directed graph n DFS, BFS, Application 2/32021 Xiaojuan Cai

Overview • Graph • Undirected graph ‣ DFS, BFS, Application • Directed graph ‣ DFS, BFS, Application 2/3/2021 Xiaojuan Cai 2

Graph theory KONINGNTHERCA R CELT 慰 7器, The Konigsberg bridge problem Source from Wikipedia) 2/32021 Xiaojuan Cai

Graph theory The Königsberg Bridge problem (Source from Wikipedia) 2/3/2021 Xiaojuan Cai 3

Graph terminology vertex length vertex degree 4 path of and indegree 2 length 4 vertex directed path rected from O to 2 le components 00 Undirected graph Directed graph 2/32021 Xiaojuan Cai

Graph terminology Undirected graph Directed graph 2/3/2021 Xiaojuan Cai 5

Adjacency matrix v.S. Adjacency list = 21 30 45 2++s+34Z 30 010 Directed: n +m Directed: n2 Undirected: n+ 2m Undirected: n2 For every edge connected with v s u and v connected with an edge 2/32021 Xiaojuan Cai

Adjacency Matrix v.s. Adjacency List G= Directed: n + m Undirected: n + 2m Directed: n 2 Undirected: n 2 For every edge connected with v ... Is u and v connected with an edge? 2/3/2021 Xiaojuan Cai 6

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