In this article, we will represent a graph using a 2D array. A graph consists of vertices (or nodes) and edges, which connect the vertices. We can easily represent a graph using a 2D array. The size of the array will be n by n, where n is the number of vertices. If an edge exists between nodes v1 and v2, then array[v1][v2] will be 1. Otherwise, it will 0.

Moreover, if the graph is undirected, then the matrix (2D array) will be symmetric, i.e., array[v1][v2] and array[v2][v1] will be the same.

Implementation of Graph using 2D Arrays

Below is the code that represents a graph using a 2D array.

#program to represent a graph using a 2D array

def display(graph, n):
  print(" ", end="\t")
  for i in range(0, n):
    print(i, end="\t")
  print()
  for i in range(0, n):
    print(i, end="\t")
    for j in range(0, n):
      print(graph[i][j], end="\t")
    print()

def representGraph(directed=False):
  n = int(input("Enter the number of vertices: "))

  #creating a 2D array of size n by n
  graph = [[0]*n for i in range(0, n)]

  e = int(input("Enter the number of edges:"))
  #takes the edges info
  print(f"Vertices are from 0 to {n-1}")
  for i in range(0,e):
    print(f"Enter edge number {i}:")
    v1 = int(input("Vertex 1: ")) 
    v2 = int(input("Vertex 2: "))

    #check if the vertices entered are valid
    if((v1>=0 and v1<n) and (v2>=0 and v2<n)):
      if directed: #if the graph is directed
        graph[v1][v2] = 1
      else:
        graph[v1][v2] = 1
        graph[v2][v1] = 1

    else:
      print("Error: Invalid Vertex or Vertices")
      return
  #print the 2D array
  print("Graph represented using 2D array")
  display(graph, n)


#pass directed=True for a directed graph
representGraph()

Output

Enter the number of vertices: 5
Enter the number of edges:4
Vertices are from 0 to 4
Enter edge number 0:
Vertex 1: 0
Vertex 2: 1
Enter edge number 1:
Vertex 1: 3
Vertex 2: 4
Enter edge number 2:
Vertex 1: 2
Vertex 2: 1
Enter edge number 3:
Vertex 1: 1
Vertex 2: 3
Graph represented using 2D array
0   1   2   3   4
0   0   1   0   0   0
1    1   0   1    1   0
2   0   1   0   0   0
3   0   1   0   0   1
4   0  0   0   1   0

In the above code, first, we take the number of vertices from the user and then create a 2D array of size n by n. After that, the user enters the number of edges and the nodes that are connected. According to the type of the graph (directed or undirected), we represent these edges in an array. Finally, we display the graph.

Even though this approach is simple and straight forward, it is not efficient. Firstly, it consumes more space because we are storing unnecessary information. There is no need to store information about unconnected vertices. Moreover, the 2D array will contain redundant data if the graph is undirected. Secondly, it takes more time, i.e., its time complexity is O(n2).