Representing Graphs

Representing a graph is to store its vertices and edges in a program. The data structure for storing a graph is arrays or lists. To write a program that processes and manipulates graphs, you have to store or represent data for the graphs in the computer.

Representing Vertices

The vertices can be stored in an array or a list. For example, you can store all the city names in the graph in Figure below using the following array:

String[] vertices = {"Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston"};

The vertices can be objects of any type. For example, you can consider cities as objects that contain the information such as its name, population, and mayor. Thus, you may define vertices as follows:

City city0 = new City("Seattle", 608660, "Mike McGinn");
...
City city11 = new City("Houston", 2099451, "Annise Parker");
City[] vertices = {city0, city1, ... , city11};

public class City {
private String cityName;
private int population;
private String mayor;

public City(String cityName, int population, String mayor) {
this.cityName = cityName;
this.population = population;
this.mayor = mayor;
 }

public String getCityName() {
return cityName;
 }

public int getPopulation() {
return population;
 }

public String getMayor() {
return mayor;
 }

public void setMayor(String mayor) {
this.mayor = mayor;
 }

public void setPopulation(int population) {
this.population = population;
 }
}

The vertices can be conveniently labeled using natural numbers 0, 1, 2, ..., n - 1, for a graph for n vertices. Thus, vertices[0] represents "Seattle", vertices[1] represents "San Francisco", and so on, as shown in Figure below.

You can reference a vertex by its name or its index, whichever is more convenient. Obviously, it is easy to access a vertex via its index in a program.

Representing Edges: Edge Array

The edges can be represented using a two-dimensional array. For example, you can store all the edges in the graph in Figure 28.1 using the following array:

int[][] edges = {
{0, 1}, {0, 3}, {0, 5},
{1, 0}, {1, 2}, {1, 3},
{2, 1}, {2, 3}, {2, 4}, {2, 10},
{3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5},
{4, 2}, {4, 3}, {4, 5}, {4, 7}, {4, 8}, {4, 10},
{5, 0}, {5, 3}, {5, 4}, {5, 6}, {5, 7},
{6, 5}, {6, 7},
{7, 4}, {7, 5}, {7, 6}, {7, 8},
{8, 4}, {8, 7}, {8, 9}, {8, 10}, {8, 11},
{9, 8}, {9, 11},
{10, 2}, {10, 4}, {10, 8}, {10, 11},
{11, 8}, {11, 9}, {11, 10}
};

This representation is known as the edge array. The vertices and edges in Figure below (a) can be represented as follows:

String[] names = {"Peter", "Jane", "Mark", "Cindy", "Wendy"};
int[][] edges = {{0, 2}, {1, 2}, {2, 4}, {3, 4}};

Representing Edges: Edge Objects

Another way to represent the edges is to define edges as objects and store the edges in a java.util.ArrayList. The Edge class can be defined as follows:

public class Edge {
int u;
int v;
public Edge(int u, int v) {
this.u = u;
this.v = v;
}
public boolean equals(Object o) {
return u == ((Edge)o).u && v == ((Edge)o).v;
}
}

For example, you can store all the edges in the graph in Figure below using the following list:

java.util.ArrayList<Edge> list = new java.util.ArrayList<>();
list.add(new Edge(0, 1));
list.add(new Edge(0, 3));
list.add(new Edge(0, 5));
...

Storing Edge objects in an ArrayList is useful if you don’t know the edges in advance.

While representing edges using an edge array or Edge objects in preceding section (Representing Edges: Edge Array) and earlier in this section may be intuitive for input, it’s not efficient for internal processing. The next two sections introduce the representation of graphs using adjacency matrices and adjacency lists. These two data structures are efficient for processing graphs.

Representing Edges: Adjacency Matrices

Assume that the graph has n vertices. You can use a two-dimensional n * n matrix, say adjacencyMatrix, to represent the edges. Each element in the array is 0 or 1. adjacencyMatrix[i][j] is 1 if there is an edge from vertex i to vertex j; otherwise, adjacencyMatrix[i][j] is 0. If the graph is undirected, the matrix is symmetric, because adjacencyMatrix[i][j] is the same as adjacencyMatrix[j][i]. For example, the edges in the graph in Figure below can be represented using an adjacency matrix as follows:

int[][] adjacencyMatrix = {
{0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0}, // Seattle
{1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, // San Francisco
{0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0}, // Los Angeles
{1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0}, // Denver
{0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0}, // Kansas City
{1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0}, // Chicago
{0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0}, // Boston
{0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0}, // New York
{0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1}, // Atlanta
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1}, // Miami
{0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1}, // Dallas
{0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0} // Houston
};

Since the matrix is symmetric for an undirected graph, to save storage you can use a ragged array.

The adjacency matrix for the directed graph in Figure below (a) can be represented as follows:

int[][] a = {{0, 0, 1, 0, 0}, // Peter
{0, 0, 1, 0, 0}, // Jane
{0, 0, 0, 0, 1}, // Mark
{0, 0, 0, 0, 1}, // Cindy
{0, 0, 0, 0, 0} // Wendy
};

Representing Edges: Adjacency Lists

You can represent edges using adjacency vertex lists or adjacency edge lists. An adjacency vertex list for a vertex i contains the vertices that are adjacent to i and an adjacency edge list for a vertex i contains the edges that are adjacent to i. You may define an array of lists. The
array has n entries, and each entry is a list. The adjacency vertex list for vertex i contains all the vertices j such that there is an edge from vertex i to vertex j. For example, to represent the edges in the graph in Figure below, you can create an array of lists as follows:

java.util.List<Integer>[] neighbors = new java.util.List[12];

neighbors[0] contains all vertices adjacent to vertex 0 (i.e., Seattle), neighbors[1] contains all vertices adjacent to vertex 1 (i.e., San Francisco), and so on, as shown in Figure below.

To represent the adjacency edge lists for the graph in Figure below, you can create an array of lists as follows:

java.util.List<Edge>[] neighbors = new java.util.List[12];

neighbors[0] contains all edges adjacent to vertex 0 (i.e., Seattle), neighbors[1] contains all edges adjacent to vertex 1 (i.e., San Francisco), and so on, as shown in Figure below.

You can represent a graph using an adjacency matrix or adjacency lists. Which one is better? If the graph is dense (i.e., there are a lot of edges), using an adjacency matrix is preferred. If the graph is very sparse (i.e., very few edges), using adjacency lists is better, because using an adjacency matrix would waste a lot of space.

Both adjacency matrices and adjacency lists can be used in a program to make algorithms more efficient. For example, it takes O(1) constant time to check whether two vertices are connected using an adjacency matrix, and it takes linear time O(m) to print all edges in a graph using adjacency lists, where m is the number of edges.

Adjacency vertex list is simpler for representing unweighted graphs. However, adjacency edge lists are more flexible for a wide range of graph applications. It is easy to add additional constraints on edges using adjacency edge lists. For this reason, this book will use adjacency edge lists to represent graphs.

You can use arrays, array lists, or linked lists to store adjacency lists. We will use lists instead of arrays, because the lists are easily expandable to enable you to add new vertices. Further we will use array lists instead of linked lists, because our algorithms only require searching for adjacent vertices in the list. Using array lists is more efficient for our algorithms. Using array lists, the adjacency edge list in Figure below can be built as follows:

List<ArrayList<Edge>> neighbors = new ArrayList<>();
neighbors.add(new ArrayList<Edge>());
neighbors.get(0).add(new Edge(0, 1));
neighbors.get(0).add(new Edge(0, 3));
neighbors.get(0).add(new Edge(0, 5));
neighbors.add(new ArrayList<Edge>());
neighbors.get(1).add(new Edge(1, 0));
neighbors.get(1).add(new Edge(1, 2));
neighbors.get(1).add(new Edge(1, 3));
...
...
neighbors.get(11).add(new Edge(11, 8));
neighbors.get(11).add(new Edge(11, 9));
neighbors.get(11).add(new Edge(11, 10));