Describe how you would implement a graph data structure.?

A graph data structure consists of a collection of nodes (also called vertices) and a collection of edges. Each edge connects a pair of nodes. Graphs may be either directed (edges have a direction) or undirected.

There are different ways you can implement a graph in code, each with their relative strengths and weaknesses. The two most common implementations are an adjacency matrix and an adjacency list. I will describe how to implement both of these.

#### 1. Adjacency Matrix

In an adjacency matrix implementation, the graph is represented by a matrix (usually a 2D array in code) where the cell at the i-th row and j-th column (denoted as M[i][j]) is true (or 1) if there’s an edge from node i to node j, or false (or 0) otherwise. This works for both directed and undirected graphs. If the graph is undirected, the matrix will be symmetric around the diagonal.

class Graph:
    def __init__(self, num_of_vertices):
        self.num_of_vertices = num_of_vertices
        self.adjMatrix = [[0]*num_of_vertices for i in range(num_of_vertices)]

The adjacency matrix representation is suitable when the graph is dense, i.e., the number of edges is close to the maximum possible number of edges. Its time complexity for checking the existence of an edge is constant, i.e., O(1).

However, it’s poor in terms of space complexity, i.e., O(V²), where V is the number of vertices.

#### 2. Adjacency List

In an adjacency list implementation, the graph is represented by a map from nodes to lists of nodes (usually array of lists or linked lists):

class Graph:
    def __init__(self, num_of_vertices):
        self.num_of_vertices = num_of_vertices
        self.adjList = [[] for i in range(num_of_vertices)]

    def add_edge(self, src, dest):
        self.adjList[src].append(dest)
        self.adjList[dest].append(src)  # For undirected graph

Each node i is associated with a list that contains the nodes to which i has an edge. The adjacency list representation is suitable when the graph is sparse, i.e., the number of edges is far less than the maximum possible number of edges.

Its time complexity for checking the existence of an edge is linear in the degree of the node, i.e., O(d), where d is the degree of a node. However, it’s efficient in terms of space complexity, i.e., O(V + E), where V is the number of vertices and E is the number of edges.

For example, if a graph data structure has five vertices and four edges in an undirected graph:

0 -- 1
|    |
3 -- 2 -- 4

The adjacency matrix and adjacency list representations will be:

For adjacency matrix:

  0 1 2 3 4
0[0 1 0 1 0]
1[1 0 1 0 0]
2[0 1 0 1 1]
3[1 0 1 0 0]
4[0 0 1 0 0]

For adjacency list:

0: 1, 3
1: 0, 2
2: 1, 3, 4
3: 0, 2
4: 2

In summary, choose the type of representation based on the expected graph’s density to achieve the best trade-off between time and space complexities.