Graphs, their traversal and use cases – II

Hi!
In our previous blog, we learned about how Graphs can be used to represent common relationships in real life and how we represent graphs in code. In this blog we will learn how to traverse or walk through various nodes in a graph.

In this realm of traversing, there are mainly two major methods:

• BFS or Breadth First Search
• DFS or Depth First Search

BFS or Breadth First Search

As the name might suggest, we try to explore the breadth(relative to a single node) of the graph rather than going in deeper looking for more nodes. Let me explain it to you graphically.

By breadth I mean the nodes being covered in green with respect to the node in black circle. The nodes which are directly connected to a single node are included in that node’s breadth.

If we had to device an algorithm for the BFS it would look something like this:

1. Select the root node.
2. Add the directly connected nodes into a queue
3. Mark the root node as ‘visited’
4. Perform dequeue operation on the queue to pop the first node in the queue
5. Add the directly connected nodes, which are not marked as ‘visited’ into the queue
6. Mark the node as ‘visited’
7. Repeat steps from 4 to 6 until queue is empty

Go through that algorithm once more so that we are ready to bring the algorithm to life, i.e code it!

from collections import defaultdict
# We will be using adjacency list approach
class Graph:
    def __init__(self, N):
        self.N = N
        self.graph = defaultdict(list)

    def addEdge(self, v, u):
        self.graph[v].append(u)
        self.graph[u].append(v)
# Function to return the array containing the traversal path using BFS
    def bfs(self, k):
        visited = [False] * self.N # Initially we have not visited any node in the graph
        queue = [k] # Adding the first node to the queue
        array = [] # We have not traversed any node
        while queue: # Iterate until queue is empty
            node = queue.pop(0) # Dequeue operation
            for n in self.graph[node]: # Iterating through nodes directly connected to the node
                if not visited[n]:
                    queue.append(n) # Add the nodes to queue if they have not been previously visited
            visited[node] = True # Finished processing the node
            array.append(node) # Append the node to the list of traversed nodes
        return array # Return the traversal of nodes
# Driver code
g1 = Graph(5) 
g1.addEdge(1, 0) 
g1.addEdge(0, 2) 
g1.addEdge(0, 3) 
g1.addEdge(3, 4)
print(g1.bfs(0)) # Output: [0, 1, 2, 3, 4]

I used a very basic example to help you understand BFS but now I want to give you a little puzzle. Following is one possible input and output scenario for the above given code:

# Test Case
g2 = Graph(5) 
g2.addEdge(1, 0) 
g2.addEdge(0, 2) 
g2.addEdge(2, 1) 
g2.addEdge(0, 3) 
g2.addEdge(3, 4)
print(g2.bfs()) # Output: [0, 1, 2, 3, 2, 4]

You have to figure out the reason for that suspicious looking output and comment below!
Hint: Refer to the previous blog to know about the various kinds of graphs.

I have used an Iterative approach to BFS and Adjacency List to represent the graph but you can definitely use Recursive approach to BFS and Adjacency Matrix to represent graphs

DFS or Depth First Search

In this algorithm we focus on exploring till the farthest node is reached and then backtrack to the closer ones. Let me explain it to you graphically:

One possible traversal for the given graph is as shown in the GIF, i.e A,B,C,D,F,G, and E. You can have a different traversal according to the code you use but the core logic is, you have to explore till the farthest node is reached.

If we had device an algorithm for the same, it would look something like this:

1. Select a root node and add it to a stack
2. Pop the top node. Add to output and mark as visited
3. Add the connected and unvisited nodes of the popped node to stack
4. Repeat steps 2-4 till queue is empty

Since we have got our algorithm out of the box, let’s bring it to life!

from collections import defaultdict

class Graph:
    def __init__(self, N):
        self.N = N
        self.graph = defaultdict(list)

    def addEdge(self, v, u):
        self.graph[v].append(u)
        self.graph[u].append(v)

    def dfs(self, k):
        visited = [False] * self.N # Array to keep track of visited nodes
        stack = [k] # Initializing stack
        array = [] # Output array
        while stack: # Execute till stack is empty
            node = stack.pop(-1) # Pop the top of stack
            array.append(node) # Add to output array
            visited[node] = True # Mark the node as visited
            for n in self.graph[node]:
                if not visited[n]:
                    stack.append(n) # Add the unvisited nodes to stack
        return array
# Driver Code
g1 = Graph(7) 
g1.addEdge(1, 0) 
g1.addEdge(0, 2) 
g1.addEdge(0, 3) 
g1.addEdge(3, 4)
g1.addEdge(2, 5)
g1.addEdge(1, 6)
print(g1.dfs(0)) # Output: [0, 3, 4, 2, 5, 1, 6]

Now What?

We have studied about the traversal algorithms but what about their applications? One of the most popular application is to check if the given structure is a graph or a tree. Trees are a subset of graphs in which no cycles are present and every node can be reached from the root node.

We’ll use DFS to solve this problem, but before clicking your keyboard get your pen and paper out and try to device an algorithm for the problem. *SPOILERS AHEAD*

Algorithm using recursive approach:

1. Start with root node and mark it as visited
2. For each child node:
   1. Mark it as visited
   2. Check if the child node is connected to a node which has been visited earlier; other than it’s parent.
   3. If not, then make the child node a new parent node and repeat Step 2

from collections import defaultdict

class Graph:
    def __init__(self, N):
        self.N = N
        self.graph = defaultdict(list)

    def addEdge(self, v, u):
        self.graph[v].append(u)
        self.graph[u].append(v)

    def isCycle(self, node, parent, visited):
        visited[node] = True # Mark as visited

        for n in self.graph[node]:
            if visited[n] == False:
                if self.isCycle(n, node, visited) == True: 
                    return True # If cycle exists for a child node, it exists in the graph
            elif n is not parent: 
                return True # Cycle exists if a node is connected to a node which has previously been visited and is not it's parent node
        return False

    def isTree(self):
        visited = [False] * self.N # Initializing array of visited nodes

        if self.isCycle(0, -1, visited) is True: # Start with root node
            return False
        
        for value in visited:
            if value == False:
                return False # If all nodes are not visited from the node, it is not a tree
# Driver code
g1 = Graph(7) 
g1.addEdge(1, 0) 
g1.addEdge(0, 2) 
g1.addEdge(0, 3) 
g1.addEdge(3, 4)
g1.addEdge(2, 5)
g1.addEdge(1, 6)

print(g1.isTree()) # False

g2 = Graph(5) 
g2.addEdge(1, 0) 
g2.addEdge(0, 2) 
g2.addEdge(2, 1) 
g2.addEdge(0, 3) 
g2.addEdge(3, 4) 

print(g2.isTree()) # True

The above program might look a bit confusing but there’s a high chance you will have to use this somewhere in your interview. In the next blog we’ll walk through on how to solve a problem using Graphs.