Held: Friday, 30 October 2015

Back to Outline 24 - Graph ADTs. On to Outline 26 - Minimum Spanning Trees.

Summary

We consider some additional basics for the implementation of graphs.

Related Pages

Overview

• Traversal algorithms.
• Marking vertices and edges.
• Three graph implementations and their costs.

Administrivia

• Friday PSA.

Upcoming Work

• HW (Due Monday): 5-1, 5-2, 5-6, 5-7, 5-13, 5-20, 5-23, 5-28
• Finish chapter 5 for Monday.

Extra Credit

Academic

• R.L. Stephens II events Friday.
• CS Table next Tuesday: Why is everyone so mean on the Internet?
• Sexual Misconduct at Grinnell College: Results from the 2013 and 2015

Peer Support

• Metal Show tonight.
• Women's Soccer, Saturday, 11 a.m. vs. Beloit (Senior day!)
• Men's Soccer, Saturday, 1:30 p.m. vs. Beloit (Senior day!)
• Halloween Day on Saturday

Traversal Algorithms

• Summarize the two traversal algorithms

Marking Vertices and Edges

• Many graph algorithms require you to "mark" vertices or edges.
• For example, the traversal algorithms ask us to mark vertices as "visited" and "processed"
• Sometimes we have a goal of finding a element with a partiuclar mark.
• How would you implement marking?

Implementing Graphs

• Three main approaches
  • Edge lists (+ vertex lists)
  • Adjacency lists
  • Adjacency matrix
• What are the costs for the main operations?
• Is it important that you tune your graph implementation to your algorithm? Absolutely