Algorithms are one of the most common themes in coding interviews. In order to gain an advantage in interviews, it is important to be very familiar with the top algorithms and their implementations.
In today’s tutorial, we will be exploring graph algorithms. We’ll begin with an introduction to graph theory and graph algorithms. Next, we will learn how to implement a graph. Finally, we will examine common graph problems you can expect to see in a coding interview.
Today, we will learn:
- What are graph algorithms?
- Properties of a graph
- How to represent graphs in code
- How to implement breadth-first traversal
- How to implement depth-first traversal
- How to remove an edge
- More interview questions
What are graph algorithms?
An algorithm is a mathematical process to solve a problem using a well-defined or optimal number of steps. It is simply the basic technique used to get a specific job done.
A graph is an abstract notation used to represent the connection between all pairs of objects. Graphs are widely-used mathematical structures visualized by two basic components: nodes and edges.
Graph algorithms are used to solve the problems of representing graphs as networks like airline flights, how the Internet is connected, or social network connectivity on Facebook. They are also popular in NLP and machine learning to form networks.
Some of the top graph algorithms include:
- Implement breadth-first traversal
- Implement depth-first traversal
- Calculate the number of nodes in a graph level
- Find all paths between two nodes
- Find all connected components of a graph
- Dijkstra's algorithm to find shortest path in graph data
- Remove an edge
While graphs form an integral part of discrete mathematics, they also have practical uses in computer science and programming, including the following:
- Caller-callee relationships in a computer program represented as a graph
- The link structure of a website could be represented by a directed graph
- Neural networks
Properties of a graph
A graph, denoted by G, is represented by a set of vertices (V) or nodes linked at edges (E). The number of edges you have depends on the vertices. The edges may be directed or undirected.
In a directed graph, the nodes are linked in one direction. The edges here show a one-way relationship.
In an undirected graph, the edges are bi-directional, showing a two-way relationship.
Example: A good use-case of an undirected graph is Facebook friend suggestions algorithm. The user (node) has an edge running to a friend A (another node) who is in turn connected (or has an edge running) to friend B. Friend B is then suggested to the user.
There are many other complex types of graphs that fall into different subsets. A directed graph, for example, has strongly connected components when every vertex is reachable from every other vertex.
Vertex
A vertex is a point where multiple lines meet. It is also called a node.
Edge
An edge is a mathematical term used for a line that connects two vertices. Many edges can be formed from a single vertex. However, without a vertex, an edge cannot be formed. There must be a starting and ending vertex for each edge.
Path
A path in a graph G = (V,E) is a sequence of vertices v1, v2, …, vk, with the property that there are edges between vi and vi+1. We say that the path goes from v1 to vk.
The sequence 6,4,5,1,26,4,5,1,2 defines a path from node 6 to node 2.
Similarly, other paths can be created by traversing the edges of the graph. A path is simple, if its vertices are all different.
Walk
Walks are paths, but they don’t require a sequence of distinct vertices.
Connected graph
A graph is connected if for every pair of vertices u and v, there is a path from u to v.
Cycle
A cycle is a path v1, v2, …, vk for which the following are true:
- k>2k>2
- The first k−1 vertices are all different
- v1=vk
Tree
A tree is a connected graph that does not contain a cycle.
Loop
In a graph, if an edge is drawn from the vertex to itself, it is called a loop. In the illustration, V is a vertex whose edge, (V, V), is forming a loop.
How to represent graphs in code
Before we move on to solving problems using graph algorithms, it is important to first know how to represent graphs in code. Graphs can be represented as an adjacency matrix or adjacency list.
Adjacency Matrix
An adjacency matrix is a square matrix labeled by graph vertices and is used to represent a finite graph. The entries of the matrix indicate whether the vertex pair is adjacent or not in the graph.
In the adjacency matrix representation, you will need to iterate through all the nodes to identify a node’s neighbors.
a b c d e
a 1 1 - - -
b - - 1 - -
c - - - 1 -
d - 1 1 - -
Adjacency List
An adjacency list is used to represent a finite graph. The adjacency list representation allows you to iterate through the neighbors of a node easily. Each index in the list represents the vertex, and each node that is linked with that index represents its neighboring vertices.
1 a -> { a b }
2 b -> { c }
3 c -> { d }
4 d -> { b c }
For the base graph class below, we will be using the Adjacency List implementation as it performs faster for the algorithm solutions later in this article.
The Graph Class
The requirements of our graph implementation are fairly straightforward. We would need two data members: the total number of vertices in the graph and a list to store adjacent vertices. We also need a method to add edges or a set of edges.
class AdjNode:
"""
A class to represent the adjacency list of the node
"""
def __init__(self, data):
"""
Constructor
:param data : vertex
"""
self.vertex = data
self.next = None
class Graph:
"""
Graph Class ADT
"""
def __init__(self, vertices):
"""
Constructor
:param vertices : Total vertices in a graph
"""
self.V = vertices
self.graph = [None] * self.V
# Function to add an edge in an undirected graph
def add_edge(self, source, destination):
"""
add edge
:param source: Source Vertex
:param destination: Destination Vertex
"""
# Adding the node to the source node
node = AdjNode(destination)
node.next = self.graph[source]
self.graph[source] = node
# Adding the source node to the destination if undirected graph
# Intentionally commented the lines
#node = AdjNode(source)
#node.next = self.graph[destination]
#self.graph[destination] = node
def print_graph(self):
"""
A function to print a graph
"""
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")
# Main program
if __name__ == "__main__":
V = 5 # Total vertices
g = Graph(V)
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(3, 4)
g.print_graph()
//output
Adjacency list of vertex 0
head -> 4 -> 1
Adjacency list of vertex 1
head -> 4 -> 3 -> 2
Adjacency list of vertex 2
head -> 3
In the above example, we see the Python graph class. We’ve laid down the foundation of our graph class. The variable V contains an integer specifying the total number of vertices.
How to implement breadth-first traversal
Given a graph represented as an adjacency list and a starting vertex, your code should output a string containing the vertices of the graph listed in the correct order of traversal. As you traverse the graph from the starting vertex, you are to print each node’s right child first, then the left.
To solve this problem, the previously implemented Graph class is already prepended.
Input: A graph represented as an adjacency list and a starting vertex
Output: A string containing the vertices of the graph listed in the correct order of traversal
Sample Output:
result = "02143"
or
result = "01234"
Take a look and design a step-by-step algorithm before jumping on to the implementation. Try to solve it on your own first. If you get stuck, you can always refer to the provided solution.
dfs:
def bfs(graph, source):
"""
Function to print a BFS of graph
:param graph: The graph
:param source: starting vertex
:return:
"""
# Write your code here!
pass
GraphClass:
class AdjNode:
"""
A class to represent the adjacency list of the node
"""
def __init__(self, data):
"""
Constructor
:param data : vertex
"""
self.vertex = data
self.next = None
class Graph:
"""
Graph Class ADT
"""
def __init__(self, vertices):
"""
Constructor
:param vertices : Total vertices in a graph
"""
self.V = vertices
self.graph = [None] * self.V
def add_edge(self, source, destination):
"""
add edge
:param source: Source Vertex
:param destination: Destination Vertex
"""
# Adding the node to the source node
node = AdjNode(destination)
node.next = self.graph[source]
self.graph[source] = node
# Adding the source node to the destination if undirected graph
# Intentionally commented the lines
#node = AdjNode(source)
#node.next = self.graph[destination]
#self.graph[destination] = node
def print_graph(self):
"""
A function to print a graph
"""
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")
Solution:
dfs:
def dfs(my_graph, source):
"""
Function to print a DFS of graph
:param graph: The graph
:param source: starting vertex
:return: returns the traversal in a string
"""
# Mark all the vertices as not visited
visited = [False] * (len(my_graph.graph))
# Create a stack for DFS
stack = []
# Result string
result = ""
# Push the source
stack.append(source)
while stack:
# Pop a vertex from stack
source = stack.pop()
if not visited[source]:
result += str(source)
visited[source] = True
# Get all adjacent vertices of the popped vertex source.
# If a adjacent has not been visited, then push it
while my_graph.graph[source] is not None:
data = my_graph.graph[source].vertex
if not visited[data]:
stack.append(data)
my_graph.graph[source] = my_graph.graph[source].next
return result
# Main to test the above program
if __name__ == "__main__":
V = 5
g = Graph(V)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
print(dfs(g, 0))
GraphClass:
class AdjNode:
"""
A class to represent the adjacency list of the node
"""
def __init__(self, data):
"""
Constructor
:param data : vertex
"""
self.vertex = data
self.next = None
class Graph:
"""
Graph Class ADT
"""
def __init__(self, vertices):
"""
Constructor
:param vertices : Total vertices in a graph
"""
self.V = vertices
self.graph = [None] * self.V
def add_edge(self, source, destination):
"""
add edge
:param source: Source Vertex
:param destination: Destination Vertex
"""
# Adding the node to the source node
node = AdjNode(destination)
node.next = self.graph[source]
self.graph[source] = node
# Adding the source node to the destination if undirected graph
# Intentionally commented the lines
#node = AdjNode(source)
#node.next = self.graph[destination]
#self.graph[destination] = node
def print_graph(self):
"""
A function to print a graph
"""
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")
The depth-first graph algorithm uses the idea of backtracking. Here, ‘backtrack’ means to move forward as long as there are no more nodes in the current path, then to move backward on the same path to find nodes to traverse.
How to remove an edge
In this problem, you must implement the remove_edge function which takes a source and a destination as arguments. If an edge exists between the two, it should be deleted.
Input: A graph, a source (integer), and a destination (integer)
Output: A BFS traversal of the graph with the edge between the source and the destination removed
First, take a close look at this problem and design a step-by-step algorithm before jumping to the implementation. Try it yourself before checking the solution!
remove_edge:
def remove_edge(graph, source, destination):
"""
A function to remove an edge
:param graph: A graph
:param source: Source Vertex
:param destination: Destination Vertex
"""
# Write your code here!
pass
graph.py:
import copy
class AdjNode:
"""
A class to represent the adjacency list of the node
"""
def __init__(self, data):
"""
Constructor
:param data : vertex
"""
self.vertex = data
self.next = None
class Graph:
"""
Graph Class ADT
"""
def __init__(self, vertices):
"""
Constructor
:param vertices : Total vertices in a graph
"""
self.V = vertices
self.graph = [None] * self.V
# Function to add an edge in an undirected graph
def add_edge(self, source, destination):
"""
add edge
:param source: Source Vertex
:param destination: Destination Vertex
"""
# Adding the node to the source node
node = AdjNode(destination)
node.next = self.graph[source]
self.graph[source] = node
# Adding the source node to the destination if undirected graph
# Intentionally commented the lines
#node = AdjNode(source)
#node.next = self.graph[destination]
#self.graph[destination] = node
def print_graph(self):
"""
A function to print a graph
"""
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")
Solution:
def remove_edge(graph, source, destination):
"""
A function to remove an edge
:param graph: A graph
:param source: Source Vertex
:param destination: Destination Vertex
"""
if graph.V == 0:
return graph
if source >= graph.V or source < 0:
return graph
if destination >= graph.V or destination < 0:
return graph
temp = graph.graph[source]
# If head node itself holds the key to be deleted
if temp is not None:
if temp.vertex == destination:
graph.graph[source] = temp.next
temp = None
return
while temp is not None:
if destination == temp.vertex:
break
prev = temp
temp = temp.next
if temp is None:
return
# Set the new link
# from removed node's previous node to next node
prev.next = temp.next
temp = None
# Main program to test above function
if __name__ == "__main__":
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 4)
print("Before: ")
g.print_graph()
remove_edge(g, 1, 3)
print("After: ")
g.print_graph()
Solution
This challenge is very similar to the deletion in the linked list, if you are familiar with it.
Our vertices are stored in a linked list. First, we access the source linked list. If the head node of the source linked list holds the key to be deleted, we shift the head one step forward and return the graph.
If the key to be deleted is in the middle of the linked list, we keep track of the previous node and connect the previous node with the next node when the destination encounters.
More interview questions
Below are other interview questions that you can try your hand at solving these problems:
- Check if a graph is strongly connected.
- Count all possible paths between two vertices.
- Count the number of nodes at a given level in a tree using breadth-first search (BFS)
- Count the number of trees in a forest.
- Detect a cycle in a graph.
- Find a Mother Vertex in a graph.
- Find K cores of an undirected graph.
- Find the path in a rectangle with circles.
- Use a minimum spanning tree to design network
- Find the shortest path to reach one prime to others by changing a single digit at a time.
- Find the smallest binary digit multiple of given number.
- Height of a generic tree from parent array.
- Iterative Depth First Search(DFS).
- Use Kruskal's algorithm to find a minimum spanning forest of an undirected edge-weighted graph
- Use Prim’s Minimum Spanning Tree Greedy algorithm (MST)
- Minimum initial vertices to traverse whole matrix with given conditions.
- Use Bellman–Ford algorithm to compute the shortest paths from a vertex to other vertices in a weighted graph
- Transpose a graph.
- Water Jug problem using BFS.
What to learn next
Congratulations on making it to the end. You should know understand graphs in Python and understand what to prepare for graph-related coding interview questions.
If you’d like to learn more about algorithms in Python, check out Educative’s learning path Ace the Python Coding Interview. In these modules, you'll brush up on data structures, algorithms, and important syntax by practicing hundreds of real interview questions.
By the end, you'll even be able to confidently answer multithreading and concurrency questions.
Happy learning!
Continue reading about coding interviews and Python on Educative
- 3 Month Coding Interview Preparation Bootcamp
- Python 3.9 Updates: topographical sort and string manipulation
- 50 Python Interview Questions and Answers
Start a discussion
What area of coding interviews would you like to read about next? Was this article helpful? Let us know in the comments below!
Top comments (0)