# Represent a Graph Using a Linked List

In this article, we will learn how to represent a graph using Linked Lists. A graph is a data structure that consists of a set of vertices (nodes) and a set of pairs showing the connection between vertices. A single pair is known as an edge. Moreover, if the graph is directed, then it will be ordered. For example, `(v1, v2)` shows that a connection line exists from v1 to v2 and not from v2 to v1. On the contrary, if the graph is undirected, then we have unordered pairs. For example, `(v1, v2)` shows that an edge exists from v1 to v2 and v2 to v1.

You can represent a graph using an Adjacency List. The Adjancey list is an array of linked lists, where the array length is equal to the number of vertices, and each array index represents a node. Moreover, an array item at index `i` contains a linked list containing all nodes adjacent to vertex `i`.  ## Implementation of Graph Representation using Linked List

This implementation of graphs using linked lists has the following functionalities:

• Creation: The graph can either be a Directed or an Undirected Graph. By default, it is directed.
• Insert an edge: It takes a pair `(v1, v2)` and adds it to the graph. If it is a directed graph, we only add v2 in the linked list of vertex v1 located at index v1. Otherwise, we also insert an edge from v2 to v1.
• Display the graph: It shows the complete graph represented using linked lists.

The code is given below.

```class Node:
def __init__(self,vertex=None):
self.vertex = vertex
self.next = None

#implementation of linked list for the graph
def __init__(self):

def insert(self, vertex):
node = Node(vertex) #create a node
if self.head == None: #if list is empty insert a vertex(node) at the start
else:
#iterate through the list till last node is found
while temp.next:
temp = temp.next
temp.next = node #adding a new node

def traverse(self):
while temp:
print(temp.vertex, end='-->')
temp = temp.next

#representation of graph using linked lists
class Graph:
def __init__(self, no_vertices, directed=True):
self.no_vertices = no_vertices
self.vertices_list = [LinkedList() for i in range(0, no_vertices)] #create a list to represent the graph
self.directed = directed

#insert an edge in the graph
def insert_edge(self, edge):
vertex1, vertex2 = edge
if (vertex1 >=0 and vertex1 < self.no_vertices) and (vertex2 >=0 and vertex2 < self.no_vertices):
#add an edge from vertex1 to vertex2
self.vertices_list[vertex1].insert(vertex2)
if not self.directed: #if the graph is undirected, add an edge from vertex2 to vertex1 as well
self.vertices_list[vertex2].insert(vertex1)
else:
raise ValueError("Invalid vertices")

#display the graph
def display_graph(self):
for i in range(0, self.no_vertices):
print(i, end="\t")
self.vertices_list[i].traverse()
print("None")
```

## Create an undirect Graph

Now call the function above to create an Undirect Graph:

```n = 5 #number of vertices

graph = Graph(n, directed=False) #create an undirected graph

#insert edges
graph.insert_edge((0, 3))
graph.insert_edge((1, 3))
graph.insert_edge((1, 2))
graph.insert_edge((2, 4))
graph.insert_edge((3, 4))

#display graph
graph.display_graph()
```

Result

```0	3-->None
1	3-->2-->None
2	1-->4-->None
3	0-->1-->4-->None
4	2-->3-->None
```

Create a Direct Graph

Again, call the function to create a direct Graph

```n = 5 #number of vertices

graph = Graph(n, directed=True) #create a directed graph

#insert edges
graph.insert_edge((0, 3))
graph.insert_edge((2, 1))
graph.insert_edge((2, 4))
graph.insert_edge((3, 1))
graph.insert_edge((3, 4))
graph.insert_edge((4, 2))

#display graph
graph.display_graph()
```

Result

```0	3-->None
1	None
2	1-->4-->None
3	1-->4-->None
4	2-->None
```

Back to: Data Structure > Data Structure - Linked List