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)`

.

Blog Hero