Welcome to Lesson 17!


Learning Objectives
  • Graph traversal using depth first search (DFS)


Announcements

Review Activity


  • Trace BFS on the following graph, using 8 as the source vertex

ملف:Disconnected simple graph.svg

  • Don't forget to use the following chart and to darken the lines of the BFS tree that results from tracing the graph


 Vertex Adjacency_List[]
 Color[] Distance[] Parent[]
 0 W
 -1 NIL
1
 W
-1 NIL
2
  W-1 NIL
3
  W-1 NIL
4
  W -1NIL
 5  W -1 NIL
 6  W-1 NIL
 7  W -1NIL
 8  W -1NIL

Queue:



Wrap Up Graphs



Upcoming Assignments
  • Project Report 4 due Tuesday
  • Final exam on Thursday