Week 10 - Graphs

Learning objectives

  • Use BFS and DFS to identify bipartitie graphs, cycles, and do topological sorts
  • Execute Djikstra's and Prim's algorithms

Class Schedule

Monday

  • Search Trees & Search Implementation

Tuesday

  • Search related Algorithms

Wednesday

  • Weighted Graph Algorithms

Thursday

  • Final Review

Topics

Search Trees & Search Implementation

  • Read Ch 26.4

  • Watch this video:

  • Read Ch 26.6-26.7

  • Watch this video:

  • Try out the Topological sort simulator. Note that it marks each vertex with a timestamp on enter and exit. (And that time gets updated every time we enter or leave a node). The part we really care about is the exit time for each node.

  • Do the SortRelatedAlgorithms WS

Weighted Graphs

  • Read Ch 27.4-27.5

  • Watch this video: