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 =<V,> 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=<V, E> 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