Computer Science 225
Advanced Programming
Spring 2020, Siena College
Lecture 11: Designing a Graph Data Structure
Date: Friday, February 14, 2020
Agenda
- Announcements
- Lab 3: More Java Swing due as usual in labs next week
- Problem Set 3
- time to be making progress: get one of the two major
sections done by early next week then the other closer to the
deadline
- Quick Problem Set 2 recap
- A look at structure5 in BlueJ, showing the inheritance hierarchy
- Using Java's object-oriented features to design a graph data structure
Terminology
- graph
- vertex
- edge
- weighted graph
- adjacent vertices
- path of vertices
- simple path
- cycle
- directed graph/digraph
- undirected graph
- vertex degree, in-degree, out-degree
- connected vertices
- subgraph
- connected component
- acyclic graph
- complete graph
- adjacency matrix
- adjacency list