Graph Representations

As we learned in both lecture and the textbook, there are multiple ways of representing the same Graph ADT. We typically have a collection of vertices, then also either:

  • a collection of edges (i.e., an edge list),
  • each vertex tracks its own edges in an adjacency list, or
  • we save all possible connections between vertices in an adjacency matrix

In this warm up, we will compare all three representations. Later in the lab, you are free to choose whichever of the three you prefer to represent your Graph ADT.

Graph Example

For this warmup, we are going to look at some flights connecting cities in the US. Since this is a multi-directional graph, if there is an edge between two cities there is a flight that goes from City A to City B and from City B to City A.

These flights can be illustrated by the following graph:

where the vertices are the cities and edges are flights connecting the two cities.

Vertex Collection

In your GitHub repository, create a new text file named representations.txt. In the first line, write out what the vertex collection would be for this graph. You can assume that each vertex can be written as a String (e.g., ”Chicago”, “Cleveland”) and the order of the vertices does not matter.

Edge Lists

On line 3 of your text file representations.txt (so that line 2 is a blank line), document how we would write out the graph in an edge list representation. You can write an edge as a pair of vertices inside parentheses, such as (“Cleveland”, “Chicago”).

Hint

Since the graph is undirected, you only have to include each edge once in the edge list. You do not need to include the same edge twice by flipping the order of its vertices.

Adjacency Lists

In lines 5-11 of your text file representations.txt (so that line 4 is blank), document the adjacency lists for each vertex (one vertex per line). Each line should start with the vertex, followed by a colon :, followed by the edges connected to that vertex.

Hint

Since the graph is undirected, each edge will be included in two different adjacency lists – one for each of its vertices.

Adjacency Matrix

Finally, on lines 13-20 of your text file representations.txt (so that line 12 is blank), document the adjacency matrix representation for the graph. In particular, line 14 should list the different vertices (as columns of the matrix). Line 15 should start with the first vertex in your vertex collection (from line 1), then include a 1 for any vertex it is connected to with an edge (and 0 of other vertices).

Hint

Since the names of the vertices are several characters long, you might want to replace your column names (on line 14) and row names (at the start of rows 15-20) with numbers, where the first vertex in your vertex collection is 1, the second vertex is 2, etc.

Committing Your Progress

Don’t forget to add/commit/push your representations.txt file.