Chapter 7: Graphs

So far, we have learned about data structures that can store linear sequences (e.g., arrays, lists, stack,
queues) and data structures that can represent non-linear hierarchical relationships (i.e., different types
of trees). What can be the most generic data structures that can represent arbitrary relationships among
entities without any ordering restrictions? The answer is graphs. The graph is the most versatile data
structure that can represent any relationship network among a collection of objects. For example, we can
use graphs to represent road networks, the internet, structure of molecules and proteins, social networks,
evolutionary relationships among species, geographic regions, and so on.

Figure 2: a graph showing a Protein Structure2

Figure 1: A graph for a road network1

Figure 3: a Facebook network3

Figure 4: graph visualizing the internet4

In fact, a single graph can capture multiple types of entities and relationships. Whenever we have a
collection of entities and need to model their interactions and relations as a network, we can use graphs.
Therefore, being able to store and use graphs in our programs is absolutely essential. Graphs are so
important in computer science that graph theory and graph algorithms are considered core computer

1
Image source: [Link]
2
Image source: [Link]
3
Image source: [Link]
4
Image source: [Link]
the_fig2_239550496

1
science courses and many books have been written on them. Even drawing a graph for visualization and
human analysis is a vast topic taught as a separate course in many universities! Here we will only learn
the basics related to graphs: the terminologies we have to understand, common graph data structure
representations, and how to traverse a graph.

Graph Terminologies
A graph G is represented as a set of vertices (or nodes) V that represent the entities/objects/concepts and
a set of edges (or links) E that represent relationship/interaction among those vertices. So, we typically
write a graph G as G = (V, E). If a and b are two vertices in V and if there is an edge between them in the
graph, we commonly write the edge as (a, b). When there is an edge (a,b) in E, we say vertex a and b are
adjacent or neighbors. Note that the relationship a graph captures may be directional or undirected. In
the former case we have a directed graph, in the latter case, an undirected graph. Below are examples, of
a directed and an undirected graph. We typically draw edges in a undirected graph as lines/curves and
edges in a directed graph as arrows.

Figure 6: a directed graph

Figure 5: an undirected graph

Notice that in a undirected graph having an edge (a,b) in E means the same thing as having the edge (b,a).
However, in a directed graph (a,b) means an edge from a to b, while (b,a) means an edge from b to a. We
can have none, either, or both in a directed graph. If we have both the edges, then we have to draw two
arrows (one from a to b and another from b to a) when drawing the graph.

The degree of a vertex in an undirected graph is the number of edges the vertex has. For example, in
Figure 5, degree of vertex d is 3. In a directed graph, a vertex has both in-degree and out-degree. The
former represents the number of edges originating from other vertices and ending at that vertex, the
latter represents the opposite. So, the in-degree of vertex d in Figure 6 is 1 and out-degree is 2. A directed
edge (a,b) in E is an outgoing edge of a and an incoming edge of b.

A path between two vertices x and y in a graph is a sequence of edges of the form (x = u0, u1),(u1,
u2),(u2,u3),…,(un-1, un=y). For example, the sequences of edges (a,b),(b,c),(c,e),(e,d) forms a path between
vertex a and d in the graph of Figure 5. The length of the path is the number of edges in it. Note that, there
may be zero, one, or more paths between any two vertices in a graph. When there is no path between
two vertices u, v in a graph then the graph is called disconnected. Then we also say that u and v are
unreachable from each other. The subset of vertices that are mutually reachable from one another along
with the various edges form a component of a disconnected graph. Hence, there are two components in
the graph of Figure 5.

2
Note that, the c -> e -> d -> b -> a path which exists in the undirected graph (Figure 5) but not in the
directed one (Figure 6). However, vertex d is still reachable from a as we have the path a -> b -> d. Notice
that, a is not reachable from d in this case, this is again because the edges are directional.

In both directed and undirected cases, the vertices and/or the edges of the graph can have weights
assigned to them. Then we call the graph a weighted directed/undirected graph. The weight assigned to
a vertex is used to represent the importance of the entity/object/concept it represents. The weight
assigned to an edge typically represents the cost or strength of the relationship among the vertices it
connects. For example, in a road network graph, the vertices are road junctions and the edges are road
segments. Then the weight of a junction can be the maximum traffic capacity at that junction and the
weight of the edge between two junctions can be their distance, aka, the length of the road. Below are
two examples of weighted graphs.

Figure 7: an edge weighted undirected graph Figure 8: directed graph having both vertex and edge weights

We say a graph is sparse when the number of edges is too low compared to the number of vertices. We
call it a dense graph when the number of edges is high. This distinction is important when we choose
among various data structure representations of a graph.

There are many more definitions related to graphs. However, for our purpose, knowing up to this much
is sufficient. Given an undirected, unweighted graph is the most common case, in the rest of this chapter
we will use the term graph to mean an undirected, unweighted graph by default. When we will refer to
the other cases, we mention them explicitly.

Graph Representations
Unlike a tree, a graph generally does not have a root vertex/node that we can use to recursively discover
all other vertices. The reason for that is simple. As the graph may be disconnected, it may be impossible
to explore the entire graph if we are given only a single starting vertex. Hence, in any typical graph
representation we have all the vertices and edges given. The most common representations of a graph
are the following:

1. Adjacency List Representation

2. Adjacency matrix representation, and
3. Incidence matrix representation

3
Adjacency List Representation
In this representation, the vertices of the graph are represented by the indices of an array. Each entry of
the array is a linked list. The elements of the list contain indices of the vertices that are adjacent to the
vertex owning the index.

Let us consider the graph of Figure 5, and assume vertices a to n are assigned successive increasing indices
starting from 0. Then the adjacency list representation of the graph is as follows:

a b c d e f g h I j K l m n
0 1 2 3 4 5 6 7 8 9 10 11 12 13
1 0 1 1 2 6 2 2 5 8 9 12 11 12
2 3 2 3 8 5 9 10 13
3 4 4
6
7
Table 1: adjacency list representation of graph in Figure 5

It is quite easy to represent a directed graph using this format also. Everything remains the same, we just
include the edge in the entry for the vertex where the edge starts from – not where it ends. Therefore,
the adjacency list representation of the directed graph of Figure 6 is as follows:

a b c d e f g h I j K l m n
0 1 2 3 4 5 6 7 8 9 10 11 12 13
1 2 6 2 2 8 5 9 9 12 13
3 7 4
Table 2: Adjacency list representation of the graph in Figure 6

When we have a weighted graph to represent then this plain array of list of numbers is not sufficient. Let
us consider the most generic case, where both the vertices and the edges can have weights. We now have
to construct an Edge class to hold all information about an edge and a separate array holding the node
weights. Then the Edge class should look as follows:

Class Edge {
int ep1
int ep2
Int weight
}

Here in the properties of the Edge class, ep1 and ep2 are the indices of the vertices that an edge connects.
With this modification, we can represent the weighted directed graph of Figure 8 as follows.

a b c D e f g h
0 1 2 3 4 5 6 7
Node Weight Array
6 3 1 2 5 2 9 1

4
 A b c d e f g h
0 1 2 3 4 5 6 7
<0,1,5> <1,2,1> <2,3,2> <4,3,5> <5,6,4>
Adjacency List
<1,3,3> <2,4,9>
<2,6,7>
<2,7,2>
Table 3: Adjacency list representation of the weighted directed graph of Figure 8

In the above, the tuple <x,y,z> stands for <ep1,ep2,weight> of an edge. Notice that in the directed
weighted graph case, the edge class can record only the destination vertex of an edge; the source is not
needed as it is the same as vertex owning the index of the array holding the list of edges. However, the
way we defined the edge class, we can represent both directed and undirected weighted graphs using
that class.

Finally, note that the vertices and edge can have other properties along with their weights in graph
representations of real-world scenarios. In that case, we can define a Node class for the vertices and have
an array of nodes and include more properties related to the edges in the Edge class. One can further,
combine the two arrays by having a node class holding the list of edges along with a vertex’s other
properties.

Space Complexity: if a graph has N vertices and M edges, then the adjacency list representation needs
an array of size N and the total number of nodes in various lists in different array indices will be total
2M (in case of undirected graph) or M (in case of a directed graph). Hence the space requirement for
the adjacency list representation is proportional to N + M. In the asymptotic notation, we can write the
space complexity as O(N+M).

Adjacency Matrix Representation

The adjacency matrix representation of a graph with N vertices uses an N×N matrix. As in the case of
previous representation, vertices are assigned increasing indices starting from 0. The ith row and column
of the matrix are for the ith vertex of the graph. The entry at ith row and jth column of the matrix is 1 if there
is an edge between the corresponding vertices of the graph. Below is the drawing and adjacency matrix
of a graph as an example.

5
 0 1 2 3 4 5 6 7
a0 0 1 1 0 0 0 0 0
b1 1 0 1 1 0 0 0 0
c2 1 1 0 1 1 0 1 1
d3 0 1 1 0 1 0 0 0
e4 0 0 1 1 0 0 0 1
f5 0 0 0 0 0 0 1 0
g6 0 0 1 0 0 1 0 0
h7 0 0 1 0 1 0 0 0
Table 4: an adjacency matrix representation of an undirected unweighted graph

Notice that the matrix is symmetric. That is if we call the matrix A then each A[i][j] entry is the same as
A[j][i] entry for all i,j < N. The reason for this is simple, as the edges are undirected, each edge occurs twice
in the matrix. The adjacency matrix of a directed graph is not symmetric, unless of course when for each
(a,b) edge of the graph there is also a (b,a) edge from vertex b to vertex a. Below is an adjacency matrix
representation of a small directed graph.

0 1 2 3 4
a0 0 1 1 0 0
b1 1 0 1 1 0
c2 0 1 0 0 0
d3 0 0 1 0 1
e4 1 0 1 0 0

Table 5: an adjacency matrix representation of a directed graph

If a graph has only weight on its edges, then we can represent it using the adjacency matrix just as easily
in both directed and undirected cases. If there is an edge (a,b) with weight w in the graph and the indices
of a and b are i and j in the matrix respectively, then we simply write w in the <i,j> cell of the adjacency
matrix, instead of writing 1. If the edge is undirected then we do the same in <j,i> cell also. Below is an
adjacency representation when the earlier directed graph is edge-weighted (i.e., only the edges have
weights).

0 1 2 3 4
a0 0 4 6 0 0
b1 2 0 1 9 0
c2 0 2 0 0 0
d3 0 0 3 0 6
e4 1 0 5 0 0

Table 6: adjacency matrix representation of a weighted directed graph

6
When both vertices and the edges of a graph have weights then we need a node weight array as in Table
3 to represents the weights of the vertices along with the adjacency matrix that captures the edge weights.
Write the adjacency matrix representation of the graph of Figure 8 as an exercise of this case.

Space Complexity: for a graph with N vertices and M edges, the adjacency matrix representation will
take N×N entries, that is, N2 entries. Consequently, the asymptotic space complexity in this
representation is O(N2). Apparently, the space cost of adjacency matrix representation is significantly
higher than that of adjacency list representation. Then why we use this second representation? The
answer is many computations are easier in the matrix representation than in the list representation.
We trade space with time when using any representation.

Incidence Matrix Representation

The final commonly used representation for graphs is the incidence matrix representation. This
representation is particularly useful and popularized by electrical circuit analysis where edges represent
wires with resistance/inductance/capacitance and the vertices represents junctions where the edges
connect and where voltage being applied. You would be surprised to know that this representation is
more than 150 years old!

In the incidence matrix representation, the edges and vertices both are numbered. Thus, if there are M
edges and N vertices in the graph, edges are numbered from 0 to M – 1 and vertices are from 0 to N – 1.
Then a M×N matrix is used where the rows are the edges and the columns are the vertices. We write a 1
in the two columns of a row to indicate that these are the two vertices connected by the edge owning
that row. The remaining entries of the row are filled with zeros. Below is an example (here the indices of
the edges are shown in red color).

a:0 b:1 c:2 d:3 e:4 f:5 g:6 h:7

0 1 1 0 0 0 0 0 0
1 1 0 1 0 0 0 0 0
2 0 1 0 1 0 0 0 0
3 0 1 1 0 0 0 0 0
4 0 0 1 1 0 0 0 0
5 0 0 0 1 1 0 0 0
6 0 0 1 0 1 0 0 0
7 0 0 1 0 0 0 0 1
8 0 0 1 0 0 0 1 0
9 0 0 0 0 0 1 1 0
10 0 0 0 0 1 0 0 1
Table 7: The incidence matrix representation of an undirected graph

When we have a directed graph, we put a 1 in the source of the edge and a -1 in the destination (or vice
versa). Below is an example.

7
 a:0 b:1 c:2 d:3 e:4 f:5 g:6 h:7
0 1 -1 0 0 0 0 0 0
1 1 0 -1 0 0 0 0 0
2 0 1 0 -1 0 0 0 0
3 0 -1 1 0 0 0 0 0
4 0 0 1 -1 0 0 0 0
5 0 0 0 -1 1 0 0 0
6 0 0 -1 0 1 0 0 0
7 0 0 -1 0 0 0 0 1
8 0 0 1 0 0 0 -1 0
9 0 0 0 0 0 1 -1 0
10 0 0 0 0 1 0 0 -1
Table 8: incidence matrix representation of a directed unweighted graph

You probably already understand how to represent an edge-weighted graph in this representation.
Instead of writing 1 and -1, we have to put the positive and negative weight of the edge in the proper
columns in a row.

Space Complexity: for a graph with N vertices and M edges, the incidence matrix representation will
require M×N entries. Consequently, the asymptotic space complexity in this representation is O(MN).
When the underlying graph is sparse, the incidence matrix representation may be cheaper than the
adjacency matrix representation or similar in cost. When the opposite is true, the adjacency matrix is
better. Electrical circuits are typically sparse graphs, that is why, incidence matrix representation is
quite popular in circuit analysis. However, there are algorithms that specifically need the incidence
matrix representation for computation efficiency.

Exercises
1. Given an undirected, unweighted graph as input, write a function to find the vertex with maximum
degree and return the degree of that vertex.
2. Given an undirected, edge-weighted graph as input, write a function to find the vertex whose sum
of edge weights is maximum.
3. Solve Problem #1 and #2 for directed, edge-weighted graph considering only outgoing edges.

Solve the above problem for all three types of representation of the input graph.