Week 10 - Graphs

Learning objectives

• Describe how to represent the data in a problem as an explicit or implicit graph
• Use DFS to identify cycles and to do topological sorts
• Execute Dijkstra's and Prim's algorithms

Class Schedule

Day 1

• Implementing graphs and searches
• Do this Search Tree WS. Then check this key

Day 2

• Search Related Algorithms
• Do this Search Related Algorithms WS. Then check this key

Day 3

• Weighted Graph Algorithms
• Do this Weighted Graph Algorithms WS. Then check this key

Day 4

• Final Review - See the study guide in Canvas.

Graphs and Search Implementation

Read Ch 34.5-34.8. You already should have read 34.6/34.7 for the ideas, but now focus on the code in those sections.

This optional video review the details of how BFS and DFS work:

Search Related Algorithms

Start with 34.10 - it covers an example of using a graph algorithm without building an explicit graph data structure. Often times, we can recognize that the data in a problem can be represented as a graph, and use a graph algorithm without needing to actually build a Graph class or data structure.

Then read Ch 34.11-34.12.

This video reviews algorithms that build on top of DFS and BFS as well as reviewing the differences between the two algorithms:

Weighted Graphs

Read Ch 34.13-34.15.

This optional video reviews Dijkstra's and Prim's algorithms: