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

Class Schedule

Monday

  • Search Trees & Search Implementation

Tuesday

  • Search related Algorithms

Wednesday

  • Weighted Graph Algorithms

Thursday

  • Final Review

Topics

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:
  • 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

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: