Outline:

1. Questions?
2. Graphs
   • motivation
   • properties
   • Graph ADT
3. Adjacency lists: example code
4. Shortest path via BFS
   • algorithm
   • traversal: example code
5. Wrap-up

What’s next

• Assignments 4 and 5 will be finalized tonight at 10pm
• Assignment 7 is online now
• Assignment 8 will be posted by Wednesday

What you should do now:

• The readings (see below)
• Complete Assignment 7
• Email Tanya if you’re using a token to resubmit Assignment 4
• Finish any last resubmissions (via token for A4, free for A5) for Assignments 4 and 5

Reading assignment (to be completed by the next class):

Graphs and BFS (from today):

• Graphs
• Adjacency lists
• Breadth-first search

Graphs and DFS (for next time):

• Adjacency matrices
• Depth-first search