(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:
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
What's inside of a
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:
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:
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:
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:
We will discuss details of each approach as well as their relative pros/cons in lecture.
You are expected to follow the Stanford Honor Code.
If this is an assignment that allows pairs, the same rules apply to each team. For example, do not look at assignment solutions that do not belong to your team, and do not give your solution to anyone outside of your team.
Remember that we run similarity-detection software over all solutions, including this quarter and past quarters, as well as any solutions we find on the web.
If you need help solving an assignment, we are happy to help you. You can go to the LaIR, or the course message forum, or email your section leader, or visit the instructor / head TA during office hours. You can do it!