An In-depth Guide To Adjacency List in Python

A graph is a data structure consisting of nodes and edges. The nodes are the vertices sets in a graph representing the objects, and the edges are the connections between two nodes. We use graphs to represent communication in a network.

The main purpose of a graph is to find the shortest route between two given nodes where each node represents an entity. There are two ways to represent a graph – 1. Using Adjacent Matrix and 2. Using Adjacency List. In this article, we will be focusing on the representation of graphs using an adjacency list.

What is an adjacency list?

An adjacency list in python is a way for representing a graph. This form of representation is efficient in terms of space because we only have to store the edges for a given node.

In python, we can use dictionaries to store an adjacency list. The dictionary’s keys will be the nodes, and their values will be the edges for each node.

With the help of an adjacency list, we can find for a particular node all the nodes connected to it. Let us understand the representation of an adjacency list with the help of an example.

Representation of an adjacency list

Lets us consider an undirected and an unweighted graph for our understanding.

In the above graph, we have five nodes – 0, 1, 2, 3 and 4 and five edges – (0,1), (1,2), (2,3), (3,0) and (4,0). We will construct an adjacency list for the above graph.

In the above image, the adjacency list has been represented in the form of a linked list. We have all the nodes mentioned on the left-hand side of the image. On the right side of the arrow, we have a list of all the adjacent nodes for the node given on the left.

The size of the list in the above case is the number of nodes, i.e., 5. If the graph had weights, then each edge would be represented in the form of a pair value: (node_no , weight)

Lets us consider the weighted form of the above graph:

Then, we would represent each edge as a pair.

For node 0, it is connected to node 1, 3 and 4. The weight of each edge for 1, 3 and 4 is 2, 5 and 1 respectively.

So, we will represent each node-weight pair as (1,2), (3,5) and (4,1). We will store each node in a similar way.

Creating an adjacency list Using Python

Here, we will be creating an adjacency list from a graph using python. We will store our list in a python dictionary. Also, we will be creating an adjacency list for both – directed unweighted graph and directed weighted graph.

Directed Unweighted Graph

adj_list = {}
mylist = []
def add_node(node):
  if node not in mylist:
    mylist.append(node)
  else:
    print("Node ",node," already exists!")

def add_edge(node1, node2):
  temp = []
  if node1 in mylist and node2 in mylist:
    if node1 not in adj_list:
      temp.append(node2)
      adj_list[node1] = temp
  
    elif node1 in adj_list:
      temp.extend(adj_list[node1])
      temp.append(node2)
      adj_list[node1] = temp
      
  else:
    print("Nodes don't exist!")

def graph():
  for node in adj_list:
    print(node, " ---> ", [i for i in adj_list[node]])

#Adding nodes
add_node(0)
add_node(1)
add_node(2)
add_node(3)
add_node(4)
#Adding edges
add_edge(0,1)
add_edge(1,2)
add_edge(2,3)
add_edge(3,0)
add_edge(3,4)
add_edge(4,0)

#Printing the graph
graph()

#Printing the adjacency list
print(adj_list)

In the above code, we have three user defined functions – add_node(), add_edge() and graph()

• add_node() accepts one parameter which is the name of the node. Before adding any edge, the node should be added through the function add_node()
• add_edge() accepts two parameters – node1 and node2. These are the two nodes between whom an edge has to be created
• graph() accepts no parameters. It simple prints the graph

We have a list named mylist. Inside this list all the nodes will be added first when add_node() function is called. Since each node should be unique, the add_node() function will print a message saying that ‘The node exists’ if it is already present in mylist.

In the function add_edge(), first we will check if node1 and node2 are present in the list. An edge will be created only if the two nodes have been added.

If node1 has no edges present in the graph, then we will create node1 as a new key. If node1 already has some edges present, then we will replace the value of the already existing key. adj_list[0] will have all the nodes which are connected to node ‘0’, adj_list[1] will have all the nodes connected to node ‘1’, and so on.

In the graph() function, we are simply print the entire graph. Fibrerst, we will create each node individually by calling add_nobrde() function. Then, we will create its edges accordingly. After that, we will print the graph and the dictionary adj_list which is the adjacency list.

The output of the above code is:

0  --->  [1]
1  --->  [2]
2  --->  [3]
3  --->  [0, 4]
4  --->  [0]

{0: [1], 1: [2], 2: [3], 3: [0, 4], 4: [0]}

Directed Weighted Graph

The code we will be executing here will be for a weighted graph. The difference between weighted and unweighted graphs is that the edges in weighted graphs have values to them.

So, the only change in the code will be in the add_edge() function. Instead of taking two parameters, it will now take three parameters.

The third parameter will be the weight of the edge. While appending to the dictionary, we will append the node-weight pair as a list.

While accessing the list, we will be passing three parameters – node1, node2 and the weight.

The weighted directed graph is:

The code for weighted directed graph is:

adj_list = {}
mylist = []
def add_node(node):
  if node not in mylist:
    mylist.append(node)
  else:
    print("Node ",node," already exists!")

def add_edge(node1, node2, weight):
  temp = []
  if node1 in mylist and node2 in mylist:
    if node1 not in adj_list:
      temp.append([node2,weight])
      adj_list[node1] = temp
  
    elif node1 in adj_list:
      temp.extend(adj_list[node1])
      temp.append([node2,weight])
      adj_list[node1] = temp
      
  else:
    print("Nodes don't exist!")

def graph():
  for node in adj_list:
    print(node, " ---> ", [i for i in adj_list[node]])

#Adding nodes
add_node(0)
add_node(1)
add_node(2)
add_node(3)
add_node(4)
#Adding edges
add_edge(0,1,2)
add_edge(1,2,2)
add_edge(2,3,4)
add_edge(3,0,5)
add_edge(3,4,3)
add_edge(4,0,1)

#Printing the graph
graph()

#Printing the adjacency list
print(adj_list)

The output will be:

0  --->  [[1, 2]]
1  --->  [[2, 2]]
2  --->  [[3, 4]]
3  --->  [[0, 5], [4, 3]]
4  --->  [[0, 1]]

{0: [[1, 2]], 1: [[2, 2]], 2: [[3, 4]], 3: [[0, 5], [4, 3]], 4: [[0, 1]]}

Must Read:

• Kruskal’s algorithm: Implementation in Python
• Implementing Dijkstra’s Algorithm in Python
• Doubly Linked List in Python – Advanced Data Structure
• How to Implement Breadth-First Search (BFS) using Python

Dijkstra’s Algorithm using Adjacency list

Dijkstra’s algorithm is used to find the shortest path between two nodes of a weighted graph. We can use an adjacency list for representing the graph while implementing Dijkstra’s algorithm.

The adjacency list will contain a pair of adjacent nodes for any given node and their respective weights. When implemented with python dictionary, each dictionary key would represent all the paths possible from that node along with its path cost.

Instead of checking if an edge exists between two given nodes, with an adjacency matrix, each node will have a list of all the nodes with which it is connected.

To check all the connected nodes for a particular node, we won’t have to check all the nodes. While storing the weights of two edges with different values, adjacency lists come in handy.

Suppose the cost to go from node ‘0’ to node ‘1’ is different from the cost to go from node ‘1’ to node ‘0’, we can use adjacency lists to store different edge costs under different keys of the dictionary.

FAQ’s

This covers Adjacency List in python. Do let us know your views on adjacency lists in the comments below.

Until then, Keep learning!