Graph Theory

A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by points termed as vertices, and the links that connect the vertices are called edges.

Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of edges, connecting the pairs of vertices. Take a look at the following graph −

In the above graph,

V = {a, b, c, d, e}

E = {ab, ac, bd, cd, de}

Graph Data Structure

Mathematical graphs can be represented in the data structure. We can represent a graph using an array of vertices and a two-dimensional array of edges. Before we proceed further, let’s familiarize ourselves with some important terms −

• Vertex − Each node of the graph is represented as a vertex. In the following example, the labeled circle represents vertices. Thus, A to G are vertices. We can represent them using an array as shown in the following image. Here A can be identified by index 0. B can be identified using index 1 and so on.
• Edge − Edge represents a path between two vertices or a line between two vertices. In the following example, the lines from A to B, B to C, and so on represent edges. We can use a two-dimensional array to represent an array as shown in the following image. Here AB can be represented as 1 at row 0, column 1, BC as 1 at row 1, column 2, and so on, keeping other combinations as 0.
• Adjacency − Two nodes or vertices are adjacent if they are connected through an edge. In the following example, B is adjacent to A, C is adjacent to B, and so on.
• Path − Path represents a sequence of edges between the two vertices. In the following example, ABCD represents a path from A to D.

Basic Operations

Following are basic primary operations of a Graph −

• Add Vertex − Adds a vertex to the graph.
• Add Edge − Adds an edge between the two vertices of the graph.
• Display Vertex − Displays a vertex of the graph.

Types of Graphs

Undirected Graph and Directed Graph

A graph in which if there is an edge connecting two vertices A and B, implies that B is also connected back to A is an undirected graph.

In the above graph, 1 is connected to 2, and 2 is connected back to 1 and this is true for every edge of the graph. So, the graph is an undirected graph.

In other words, we can say that a graph G=(V, E) is undirected if an edge (i, j) (edge from i to j) ∈∈ E implies that the edge (j, i) ∈∈ E also.

Two-lane roads on which vehicles can go in either direction are the example of undirected graphs.

In a directed graph, the edges are directed i.e., they have a direction. So, if the edge is an edge from i to j i.e., (i, j) ∈∈ E, then this doesn’t necessarily mean that there will be also an edge from j to i.

This is a directed graph as there is a path from 1 to 2 but there isn’t any path from 2 to 1.

Suppose a person is following someone on Twitter but may or may not be followed back. This can be represented by directed graphs.

Cyclic and Acyclic Graph

In a cyclic graph, there are cycles or loops formed by the edges but this doesn’t happen with an acyclic graph.

Weighted and Unweighted Graph

Sometimes weights are given to the edges of a graph and these are called weighted graphs. For example, in a graph representing roads and cities, giving the length of the road as weight is a logical choice.

Dense and Sparse Graph

When the number of edges (|E|) is close to the square of the number of vertices (|V|2), then the graph is a dense graph. To visualize, you can imagine a graph with few vertices and lots of edges between them.If |E| is much less than |V|2, then it is a sparse graph.

Simple and Non-simple Graph

The graph which has self-loops or an edge (i, j) occurs more than once (also called multiedge and graph is called multigraph) is a non-simple graph.

Connected and Disconnected Graph

If every node of a graph is connected to some other nodes is a connected graph. However, if there is at least one node which is not connected to any other node, then it is a disconnected graph.

Complete Graph

When each node of a graph is connected to every other node, then it is called a complete graph.

Representation of Graphs

There are two ways of representing a graph:

• Adjacency-list representation
• Adjacency-matrix representation

According to their names, we use lists in the case of adjacency-list representation and a matrix (2D array) in the case of adjacency matrix representation.

The way in which we are going to represent our graph depends on the task we have to perform. This will be clear after studying these representations in detail.

Adjacency-matrix Representation

In the adjacency-matrix representation, we use a |V|x|V| matrix to represent a graph.

Here, we are assuming that the vertices of the graph are numbered from 1 to |V|. Now for the cell (i, j) of this matrix, we set its value 1 if we have an edge from i to j (or (i, j) ∈∈ E), otherwise 0.

In the above picture, we have an edge from 1 to 2, so the cell (1, 2) is 1, but there is no edge connecting 2 back to 1, so the cell (2, 1) is 0.

Similarly, there is no edge from the vertex 4 to any other vertices, so (4, 1), (4, 2), … , (4, 5) all are 0.

It is quite clear that we are using a |V|x|V| matrix to represent a graph G=(V, E), so the space required to store this would be Θ(|V|2)Θ(|V|2).

Now imagine a social media site like Facebook, where there are billions of users. Using a matrix will take quite a large amount of space but the real problem is that even among these billions of people, a person is not connected most of the other person i.e., if each person on average has 1000 friends, then most of the cells are going to be empty (or 0). In this case (and most of the cases), we use adjaceny-list representation.

However, there is also one advantage of this representation — we can tell if one node is connected to another node in no time (Θ(1)Θ(1) to be appropriate).

We can say that using an adjacency-list for a sparse graph and adjacency-matrix for a dense graph is a general choice.

In most of the applications, the number of nodes which are connected from a node is much less than the total number of nodes. So, we move to adjacency-list representation.

Adjacency-list Representation

In adjacency-list representation, we have a list of all the nodes and for each node, we have a list of nodes for which the node has an edge.

For example, for the above graph, we will have a list of all the nodes.

Now, for each of these nodes, we will store a list (array, hash or linked list) of other nodes which have an edge from these nodes (or adjacent nodes). So, node 1 will have a list containing nodes 2 and 3, node 2 will have a list containing node 4, etc.

Thus, in an adjency-list representation, we have an array (Adj) of |V| lists and each element of this array Adj i.e., Adj[i] consists all the vertices adjacent to it.

The total number of items in all these lists is the number of edges in the graph i.e., |E|, if the graph is directed. But if the graph is undirected, then the total number of items in these adjacency lists will be 2|E| because for any edge (i, j), i will appear in adjacency list j and vice-versa.

Now, the total space taken to store this graph will be space needed to store all adjacency list + space needed to store the lists of vertices i.e., |V|.

So, it requires Θ(|V|+|E|)Θ(|V|+|E|) space.

We can also add a new vertex in an adjacency -list in O(1)O(1) time but doing the same will require O(|V|2)O(|V|2) time in the case of an adjacency-matrix representation because a |V+1|x|V+1| matrix is needed to be reconstructed.