Week 10 - Graphs

Learning objectives

  • Use BFS and DFS to identify bipartite graphs and cycles, and to do topological sorts
  • Execute Dijkstra's and Prim's algorithms
Schedule your final appointment for next week. See the discussion board for more information.

Day 1

Search Trees & Search Implementation

  • Watch this video to learn about how searches in a graph explore a particular tree of edges and how we can represent that tree:

Day 2

  • Watch this video to learn about algorithms for solving problems in graphs that are based on searches:

  • Read Ch 26.6-26.7

  • 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

Day 3

Weighted Graphs

  • In an unweighted graph, every edge has a "cost" of 1. In a weighted graph, the cost associated with traversing or including each edge can vary. In these graphs, we need special algorithms to find shortest paths or to find the minimal cost set of edges to connect every vertex. Watch this video:

Day 4

  • Final Review - The final is cumulative. Review your midterms and the study guides for the midterms. Then check the finals area in Elearn for practice problems on material since midterm 2.