Hello, in this post we'll discuss the **representations** of a graph, their **characteristics**, **space complexity**, and also their **implementation** in python.

## Representation of Graph

### 1. Adjacency matrix

in this type of representation, we use 2-dimensional arrays to represent the graph where the number of columns and rows is the total number of vertices.

- if
`A[i][j] = 1`

that means**i**and**j**are adjacent.

### characteristics of using adjacency matrix

- Fast to lookup and check for presence or absence of a specific edge between any two nodes
**O(1)** - Fast to add a new edge
**O(1)** - Slow to iterate over all edges
- Slow to add or delete a node O(n
^{2})

### Space complexity of adjacency matrix

- The space complexity of adjacency matrix is O(
**n**)^{2}

### Example of the adjacency matrix

### Implementation Of Adjacency matrix in python

```
class Graph():
def __init__(self, matrixSize):
# fill the matrix with 0.
self.adjacencyMatrix = []
for i in range(matrixSize):
self.adjacencyMatrix.append([0 for i in range(matrixSize)])
self.matrixSize = matrixSize
def addEdge(self, node1, node2):
self.adjacencyMatrix[node1][node2] = 1
self.adjacencyMatrix[node2][node1] = 1
def deleteEdge(self, node1, node2):
# if there is an edge between the two giving nodes
if self.adjacencyMatrix[node1][node2] == 1 :
self.adjacencyMatrix[node1][node2] = 0
self.adjacencyMatrix[node2][node1] = 0
```

### 2. Adjacency List

The adjacency list is represented as an array of linked lists, where each index of the array represents a node and each node represents its adjacents nodes using a linked list.

### characteristics of adjacency list

- Memory usage depends on the number of edges (not the number of nodes) which might save a lot of memory
- slower than matrix for checking the presence or the absence of an edges
- Fast to iterate over all edges

### Space of complexity of adjacency list

The space complexity of the adjacency list is **O(|V|+|E|)**.

### Example of adjacency list

### Implementation of adjacency list

```
class AdjNode:
def __init__(self, data):
self.vertex = data
self.next = None
# A class to represent a graph. A graph
# is the list of the adjacency lists.
# Size of the array will be the no. of the
# vertices "V"
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = [None] * self.V
# Function to add an edge in an undirected graph
def add_edge(self, src, dest):
# Adding the node to the source node
node = AdjNode(dest)
node.next = self.graph[src]
self.graph[src] = node
# Adding the source node to the destination as
# it is the undirected graph
node = AdjNode(src)
node.next = self.graph[dest]
self.graph[dest] = node
# Function to print the graph
def print_graph(self):
for i in range(self.V):
print("Adjacency list of vertex {}\n head".format(i), end="")
temp = self.graph[i]
while temp:
print(" -> {}".format(temp.vertex), end="")
temp = temp.next
print(" \n")
```

## Top comments (0)