Representing Graphs in Data Structures

Graph Basics

Contributed by: Ruchi Nayyar

A graph can be thought of as a data structure that is used to describe relationships between entities. An entity can be any item that has a distinctive and independent existence. It could either be an actual physical object or an abstract idea. For example, an entity can be a person, place or an organization about which data can be stored.  

In the computing world, graphs have become ubiquitous owing to their ability to not only provide abstractions to real life but also demonstrate complicated relationships with ease. As such, a variety of practical problems can be represented as graphs. For example, a linked structure of websites can be viewed as a graph.

Every graph is a set of points referred to as vertices or nodes which are connected using lines called edges. The vertices represent entities in a graph. Edges, on the other hand, express relationships between entities. Hence, while nodes model entities, edges model relationships in a network graph. A graph G with a set of V vertices together with a set of E edges is represented as G= (V, E). Both vertices and edges can have additional attributes that are used to describe the entities and relationships. Figure 1 depicts a simple graph with five nodes and six edges.

In real-world applications of graphs, an edge might represent professional relationships that exist between people in LinkedIn or a personal relationship on a social media platform such as Facebook or Instagram.

Graphs can broadly be categorized into Undirected (Fig 2a) or Directed (Fig 2b). An undirected graph is directionless. This means that the edges have no directions. In other words, the relationship is mutual. For example, a Facebook or a LinkedIn connection. Contrarily, edges of directed graphs have directions associated with them. An asymmetric relationship between a boss and an employee or a teacher and a student can be represented as a directed graph in data structure. Graphs can also be weighted (Fig 2c) indicating real values associated with the edges. Depending upon the specific use of the graph, edge weights may represent quantities such as distance, cost, similarity etc. 

Representing Graphs

A graph can be represented using 3 data structures- adjacency matrix, adjacency list and adjacency set. 

An adjacency matrix can be thought of as a table with rows and columns. The row labels and column labels represent the nodes of a graph. An adjacency matrix is a square matrix where the number of rows, columns and nodes are the same. Each cell of the matrix represents an edge or the relationship between two given nodes. For example, adjacency matrix Aij represents the number of links from i to j, given two nodes i and j. 

The adjacency matrix for a directed graph is shown in Fig 3. Observe that it is a square matrix in which the number of rows, columns and nodes remain the same (5 in this case). Each row and column correspond to a node or a vertex of a graph. The cells within the matrix represent the connection that exists between nodes. Since, in the given directed graph, no node is connected to itself, all cells lying on the diagonal of the matrix are marked zero. For the rest of the cells, if there exists a directed edge from a given node to another, then the corresponding cell will be marked one else zero.

To understand how an undirected graph can be represented using an adjacency matrix, consider a small undirected graph with five vertices (Fig 4). Here, A is connected to B, but B is connected to A as well. Hence, both the cells i.e., the one with source A destination B and the other one with source B destination A are marked one. This suffices the requirement of an undirected edge. Observe that the second entry is at a mirrored location across the main diagonal.

In case of a weighted graph, the cells are marked with edge weights instead of ones. In Fig 5, the weight assigned to the edge connecting nodes B and D is 3. Hence, the corresponding cells in the adjacency matrix i.e. row B column D and row D column B are marked 3.

NetworkX library provides an easy method to create adjacency matrices. The following example shows how we can create a basic adjacency matrix using NetworkX. 

In adjacency list representation of a graph, every vertex is represented as a node object. The node may either contain data or a reference to a linked list. This linked list provides a list of all nodes that are adjacent to the current node. Consider a graph containing an edge connecting node A and node B. Then, the node A will be available in node B’s linked list. Fig 6 shows a sample graph of 5 nodes and its corresponding adjacency list.  

Note that the list corresponding to node E is empty while lists corresponding to nodes B and D have 2 entries each.

Similarly, adjacency lists for an undirected graph can also be constructed. Fig 7 provides an example of an undirected graph along with its adjacency list for better understanding. 

Adjacency list enables faster search process in comparison to adjacency matrix. However, it is not the best representation of graphs especially when it comes to adding or removing nodes. For example, deleting a node would involve looking through all the adjacency lists to remove a particular node from all lists.  NetworkX library provides a function adjacency_list () to generate the adjacency list of a given graph. The following code demonstrates its use.

The adjacency set mitigates a few of the challenges posed by adjacency list. Adjacency set is quite similar to adjacency list except for the difference that instead of a linked list; a set of adjacent vertices is provided. Adjacency list and set are often used for sparse graphs with few connections between nodes. Contrarily, adjacency matrix works well for well-connected graphs comprising many nodes.

This brings us to the end of the blog on graph in data structure. We hope you found this helpful. If you wish to learn more such concepts, you can check out Great Learning Academy’s free online courses.