Lecture Preview: Graph Implementation

(Suggested book reading: Programming Abstractions in C++, Chapter 18 sections 18.2 - 18.3, 18.5)

Today we will learn about how a graph class is actually implemented. The Stanford C++ library includes a class BasicGraph that contains several useful members related to graphs, vertices, edges, and paths. For example, if you wanted to create an object to represent the following graph:

graph implementation

Then you could create a BasicGraph as follows: 

BasicGraph graph;
graph.addVertex("a");
graph.addVertex("b");
graph.addVertex("c");
graph.addVertex("d");
graph.addEdge("a", "c");
graph.addEdge("b", "c");
graph.addEdge("c", "b");
graph.addEdge("b", "d");
graph.addEdge("c", "d");

But how exactly is BasicGraph implemented? What's inside of a BasicGraph object? How does it represent the vertices, edges, and so on? The answer is that there are multiple ways a graph can be implemented internally. Consider the following graph:

graph implementation example

One way to implement a graph is using an edge list, where the only structure you store is a list (vector) of the edges. The information about the vertices is implicit inside the edges. Here is an edge list for the above graph:

edge list

A second way to implement a graph is using an adjacency list, where the only structure you store is a list of the vertices, where each vertex contains a nested list of other vertices that are its neighbors. The information about the edges is implicit inside the vertices' neighbor lists. Here is an adjacency list for the above graph:

adjacency list graph implementation example

A third way to implement a graph is using an adjacency matrix, where the only structure you store is a two-dimensional grid where each row represents a start vertex and each column represents an end vertex. The grid cell [i, j] stores information about the edge, if any, from vertex i to vertex j. Here is an adjacency matrix for the above graph:

adjacency matrix graph implementation example

We will discuss details of each approach as well as their relative pros/cons in lecture.

This document and its content are copyright © Marty Stepp, 2014. All rights reserved. Any redistribution, reproduction, transmission, or storage of part or all of the contents in any form is prohibited without the authors' expressed written permission.