Teaching Graphs
Definition
Graphs are a fundamental data structure in computer science used to model relationships between objects.
Each object is a node (also called a vertex), and the connection between them is an edge (or arc).
In a complete graph, there is a single edge between every pair of distinct vertices. There are no loops and no multiple edges.
Common Uses
- Pathfinding algorithms (Google Maps, GPS)
- Web page ranking (Google’s PageRank algorithm)
- Network routing (data packet transfers)
Image Example of a Graph
Warm-Up Activity
“Imagine you are a delivery driver for Amazon. You have 10 packages to deliver to 10 different houses in a neighborhood. What’s the best way to plan your route so you don’t waste time and gas?”
- What strategies would you use to decide where to go first?
- How do real-life delivery companies solve this problem?
- Would it be practical to try every possible route? Why or why not?
Adjacency Matrix vs. Adjacency List
Adjacency Matrix
- An adjacency matrix is a way of representing a graph as a matrix of boolean (0’s and 1’s)
Undirected Graph as Adjacency Matrix
The entire matrix is intialized to 0. If there is an edge from source to destination, insert 1 because it can go either way.
Directed Graph as Adjacency Matrix
The entire matrix is intialized to 0. If there is an edge from source to destination, we insert 1 for the particular destination.
Adjacency List
- An array of Lists is used to store edges between two vertices. The size of array is equal to the number of vertices (i.e, n). Each index in this array represents a specific vertex in the graph. The entry at the index i of the array contains a linked list containing the vertices that are adjacent to vertex i.
Undirected Graph as Adjacency List
The below undirected graph has 3 vertices. So, an array of list will be created of size 3, where each indices represent the vertices. Now, vertex 0 has two neighbours (i.e, 1 and 2). So, insert vertex 1 and 2 at indices 0 of array. Similarly, For vertex 1, it has two neighbour (i.e, 2 and 0) So, insert vertices 2 and 0 at indices 1 of array. Similarly, for vertex 2, insert its neighbours in array of list.
Directed Graph as Adjacency List
The below directed graph has 3 vertices. So, an array of list will be created of size 3, where each indices represent the vertices. Now, vertex 0 has no neighbours. For vertex 1, it has two neighbour (i.e, 0 and 2) So, insert vertices 0 and 2 at indices 1 of array. Similarly, for vertex 2, insert its neighbours in array of list.
Popcorn Hack
How we can represent cities and paths as graphs:
- Nodes (Vertices) → Cities
- Edges → Roads between cities
- Weights → Distance or cost of travel
Draw a simple 5-city graph on the board and discuss possible routes.
Here is a Youtube video that shows and explains graphs in computer science with a traveling salesman example. [Traveling Salesman Problem]
Homework Hack
College Board Example
Skill 1.D. Design and Evaluate computational solutions for a purpose.
Q1: In which of the configurations is it possible to have redundant routing between devices Q and V?
A) Configuration I only
B) Configuration II only
C) Both configuration I and configuration II
D) Neither configuration I nor configuration II
Q2: In configuration I, what is the minimum number of connections that must be broken or removed before device T can no longer communicate with device U?
A) One
B) Two
C) Three
D) Four