Home/Blog/Programming/Algorithms 101: How to use graph algorithms

Algorithms 101: How to use graph algorithms

Jerry Ejonavi

Dec 17, 2020

11 min read

Become a Software Engineer in Months, Not Years

From your first line of code, to your first day on the job — Educative has you covered. Join 2M+ developers learning in-demand programming skills.

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

Prepare for algorithm questions the easy way
This curates path takes you through all that you need to know to crack your Python interviews with confidence.

Ace the Python Coding Interview

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 graphs, 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()

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.

Keep the learning going.#

Prepare for Python interviews without scrubbing through videos or documentation. Educative’s text-based courses are easy to skim and feature live coding environments, making learning quick and efficient.

Ace the Python Coding Interview

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 solution provided in the solution section.

def bfs(my_graph, source):
    """
    Function to print a BFS of graph
    :param graph: The graph
    :param source: starting vertex
    :return:
    """
    
    # Mark all the vertices as not visited
    visited = [False] * (len(my_graph.graph))
    # Create a queue for BFS
    queue = []
    # Result string
    result = ""
    # Mark the source node as
    # visited and enqueue it
    queue.append(source)
    visited[source] = True
    while queue:
        # Dequeue a vertex from
        # queue and print it
        source = queue.pop(0)
        result += str(source)
        # Get all adjacent vertices of the
        # dequeued vertex source. If a adjacent
        # has not been visited, then mark it
        # visited and enqueue it
        while my_graph.graph[source] is not None:
            data = my_graph.graph[source].vertex
            if not visited[data]:
                queue.append(data)
                visited[data] = True
            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(bfs(g, 0))

How to implement depth-first traversal#

In this problem, you have to implement the depth-first traversal. To solve this problem, the previously implemented graph class is already provided.

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 = "01342" 
or
result = "02143"

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

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!

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.

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#

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

Algorithms 101: How to use graph algorithms

Prepare for algorithm questions the easy way This curates path takes you through all that you need to know to crack your Python interviews with confidence. Ace the Python Coding Interview

What are graph algorithms?#

Properties of a graph#

Vertex#

Edge#

Path#

Walk#

Connected graph#

Cycle#

Tree#

Loop#

How to represent graphs in code#

Adjacency Matrix#

Adjacency List#

The Graph Class#

Keep the learning going.#

How to implement breadth-first traversal#

Solution#

How to implement depth-first traversal#

Solution#

How to remove an edge#

Solution#

More interview questions#

What to learn next#

Continue reading about coding interviews and Python#

Prepare for algorithm questions the easy way
This curates path takes you through all that you need to know to crack your Python interviews with confidence.

Ace the Python Coding Interview