Lecture 24:
Graphs & Iterators
CS 136: Spring 2024
Katie Keith
Record on Zoom
📣 Announcements
🎯 Today’s Learning Objectives
📚Readings
Multiple data structures can implement the same ADT
Data Structures
List
Finite number of elements
(same element may occur more than once)
Stack
Last in first out (LIFO) operations
Symbol Table
Associates a key with a value
Graph
A set of vertices, pairs of which are connected by edges
Queue
First in first out (FIFO) operations
ADT
Graphs
A graph is a set of vertices and a collection of edges, each of which connect a pair of vertices.
Vertex
Edge
Undirected edge (no arrow on either side)
Preview: We’ll talk about directed & weighted graphs next week
Application: New York City Subway
Vertices = Subway stops; Edges = track between stop
Important graph operations:
Application: US Railways
Vertices = cities; Edges = rail lines connecting the cities
Equivalent
Note, the connections matter, not the exact location of each vertex
Guesses of this graph?
Application: The internet, circa 1998
Undirected Graph ADT
Look-ahead: We’ll define this
Degree
The degree of vertex v is the number of edges incident (attached) to v.
What’s the degree of a?
Of c?
Path
A path in a graph is a sequence of vertices connected by edges, with no repeated edges.
How many distinct paths are there between b and c?
Reachability and Connectedness
Reachability
A vertex v in graph G is reachable from vertex u in G if there is a path from u to v.
Is a reachable from b? Is c reachable from b?
Connectedness
An undirected graph G is connected if for every pair of vertices u, v in graph G, v is reachable from u.
This subgraph (vertices d, a, b) is connected
This subgraph (a single vertex c) is also connected
✅
🎯 Today’s Learning Objectives
ADTs to Data Structures
Adjacency matrices
ADTs
Data Structures
Adjacency lists
List
Finite number of elements
(same element may occur more than once)
Stack
Last in first out (LIFO) operations
Queue
First in first out (FIFO) operations
Symbol Table
Associates a key with a value
Graphs
A set of vertices, pairs of which are connected by edges
Adjacency List Representation
An adjacency list representation of an undirected graph consists of an array where indices are vertices and each array index contains a reference to a linked list of adjacent vertices.
Look-ahead: We’ll come back and implement.
Adjacency Matrix Representation
An adjacency matrix representation of an undirected graph consists of a 2-dimensional array of size VxV where V is the number of vertices in the graph.
A 1 indicates an edge exists (here between vertex 5 and 2)
A 0 indicates an edge does not exists (here between vertex 1 and 5)
Vertices
Adjacency matrix in Java
int V = 10; // num. vertices
boolean[][] adj = new boolean[V][V]; // adjacency matrix
adj[0][5] = true; // add edge between vertex 0 and 5
adj[5][0] = true;
2-D array type
Add edge for both 0->5 and 5->0 for undirected graph
Thinking about time-space tradeoff, brainstorm when is an adjacency list representation better? When is an adjacency matrix representation better?
Adjacency list
Adjacency matrix
💡Think-pair-share
Trade-offs: Adjacency lists versus matrices
| Adjacency list | Adjacency matrix |
Adding an edge (time) | O(1) | O(1) |
Memory (space) | O(V+E) | O(V2 ) |
Checking if an edge exists from vertex v to u (time) | O(degree(v)) | O(1) |
Let V be the number of vertices in our graph and let E be the number of edges.
✅
✅
🎯 Today’s Learning Objectives
Iterators
Goal: Be able to use an enhanced for loop for an object of our custom class/reference type (e.g., set of adjacent vertices).
for (int number : numbers) {
System.out.println(number);
}
Enhanced for-loop
Java’s Iterable and Iterator
Java defines two interfaces that facilitate enhanced for loops.
Why? Abstraction! With an iterator, we don't need to know how the collection is implemented (e.g., array, linked list, hash table etc.).
Checks if there are more elements to iterate over
Returns the next item in the iteration
Aside: CS History
AdjacencyList.java
Bag.java
💻
Development Tip: Exceptions
import java.util.NoSuchElementException;
...
if (!hasNext()) throw new NoSuchElementException();
In Java, an Exception is an event that disrupts the normal flow of a program's execution, usually caused by errors like invalid input, missing files, or failed operations.
Many different exceptions you can import
New object
Keyword to trigger exception at runtime
✅
✅
✅
🎯 Today’s Learning Objectives