Computer Science 385
Design and Analysis of Algorithms
Spring 2019, Siena College
Lecture 3: Graph Data Structures
Date: Friday, January 18, 2019
Agenda
- Announcements
- Don't come to class on Monday
- Please bring a computer to lab next Tuesday/Wednesday, as
we'll be doing some coding - if you can't, don't worry, we'll
make sure you're in a group with someone who has one
- Please wrap up Lab 0: GitHub Setup today
- Lab 1: Counting Operations due at the start of your
lab session next week - remember that everyone needs to submit a
packet to earn credit
- You can read about some more complete graph data structures
than we will be studying here in sections 1-3 of chapter 16 of the
free online reference text, Java Structures: Data
Structures in Java for the Principled Programmer,
"Root 7" Edition, by Duane Bailey
- Graph data structures
- graph concept
- types of graphs: directed, undirected, weighted
- graph representations: adjacency matrix, adjacency list
- basic implementation: instance variables, helper classes, essential methods
- costs
- operations on graphs
Terminology
- graph
- graph nodes/vertices
- graph edge/edge weights
- adjacency matrix/adjacency list
- vertex degree/in-degree/out-degree