Failure is an option here. if things are not failing, you are not innovating.
— Elon Musk
This is the first post on my new blog. I’m just getting this new blog going, so stay tuned for more.
I plan to focus on blogs related to Data Structures, Algorithms and Personal Projects. I will write weekly blogs which will definitely help you in becoming a better developer. Most of my posts will be directly referenced from The Algorithm Design Manual by Steven S. Skiena. Python 3 is my choice of poison, which might be different for you but you will still be able to understand the underlying logic(Python is just indented English 😀 )
Subscribe below to get notified when I post new updates.
In the previous posts we learned about the traversal algorithms used on graphs: DFS and BFS. I am sure you have understood the algorithm and are eager to solve some questions using those algorithms.
In this post we will discover how to use the algorithms to solve problems. We will solve today is Bicoloring.
Go ahead and take a look at the question! Try to solve it first and then continue. It is immensely important that you must try yourself first before taking a look at my approach and solution. I will walk you through the process of understanding what the question demands and how to solve it.
The assumptions given are as follows:
no node will have an edge to itself.
the graph is nondirected. That is, if a node a is said to be connected to a node b, then you must assume that b is connected to a.
the graph will be strongly connected. That is, there will be at least one path from any node to any other node.
If we try to think how to solve it, these statements must come to your mind:
Every node is connected so we can traverse to every node easily
Every, parent and child node pair will definitely have different colors if the graph is BICOLORABLE.
A node can have more than one parent and thus must satisfy the second statement for every parent for the graph to be BICOLORABLE
It will not be a BICOLORABLE graph if the sibling of a node is also it’s parent, that is if two nodes are connected and they have a common immediate parent
Keeping these statements in mind let’s device an algorithm:
Store the input in an Adjacency List or an Adjacency Matrix.
Traverse the map and mark the levels for each node using BFS or DFS
Check if two nodes of same level are connected
If you find no such nodes then the graph is BICOLORABLE else it is NOT BICOLORABLE.
Let’s get put our brains to work and write a program for the above algorithm! I have come up with this:
from sys import stdin
from collections import defaultdict
while True:
v = int(stdin.readline())
if v > 0:
e = int(stdin.readline())
adj_list = [[] * v for _ in range(v)]
for _ in range(e):
e1, e2 = map(int, stdin.readline().split())
adj_list[e1].append(e2)
adj_list[e2].append(e1)
queue = [[0,0]]
clear = True
reached = [False] * v
heights = defaultdict(int)
heights[0] = 0
while queue:
node, height = queue.pop(0)
for n in adj_list[node]:
if not reached[n]:
queue.append([n,height+1])
heights[n] = height+1
reached[n] = True
if heights[n] == heights[node]:
clear = False
break
if clear:
print("BICOLORABLE.")
else:
print("NOT BICOLORABLE.")
else:
break
There can be multiple solutions to same problem so please do try solving the problem yourself and feel free to share your solutions!
I have only given you an example of how to use an algorithm to solve a problem and there are many more such questions which you can find online. Just like every muscle, your brain will also develop after you keep on brainstorming regularly. To become better at coding consistency is a major contributor so Happy Coding!
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.
Animation to show breadth
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:
Select the root node.
Add the directly connected nodes into a queue
Mark the root node as ‘visited’
Perform dequeue operation on the queue to pop the first node in the queue
Add the directly connected nodes, which are not marked as ‘visited’ into the queue
Mark the node as ‘visited’
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:
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:
Working of DFS
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:
Select a root node and add it to a stack
Pop the top node. Add to output and mark as visited
Add the connected and unvisited nodes of the popped node to stack
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:
Start with root node and mark it as visited
For each child node:
Mark it as visited
Check if the child node is connected to a node which has been visited earlier; other than it’s parent.
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.
Hi! In High School we have already studied graphs and how they are used to showcase our data but in Computer Science, Graphs as a Data Structure are a completely different concept. We use graphs to represent relationships between one or more entities. The nodes represent the entities and relationships are depicted by edges. A graph G is represented as (V, E) in which V is the set of vertices and E is the set of edges. Today, we’ll be exploring it out further.
An undirected graph
What you can see above is a simple undirected graph depicting the friendship(relationship) using edges between various people(nodes). What we can concur from the above graph is that Krishna is Divij’s and Ramesh’s friend, while Krishna’s friends are both Divij and Ramesh. What you might have noticed is I used the term undirected, and that should strike your curiosity that how many other types of graphs are possible? The answer to that question is:
Undirected and Directed
Weighted and Unweighted
Simple and Non-simple
Sparse and Dense
Cyclic and Acyclic
Embedded and Topological
Implicit and Explicit
Labelled and Unlabeled
I know I have listed a lot but we’ll not be going through each and every graph type in detail. We’ll only cover undirected, directed, weighted, unweighted, cyclic and acyclic graphs.
Undirected vs Directed: The edges of directed graph will imply the receiver and sender for the specified relationship, whereas in undirected graph both nodes act as receiver and sender.
Weighted vs Unweighted: The edges of weighted graph not only depict the relationship but also the strength of the relationship, and in various cases, the cost of the relationship. The unweighted graph only depicts the relationship.
Cyclic vs Acyclic: As the names might suggest, cyclic graph contains a cycle, whereas acyclic graphs do not.
Road Network II
Road Network I
Above you can see the two graphs representing the road network between various cities(A, B, C, D and E) with edges depicting the cost of toll on each road. In the first graph if you start from A, you will eventually end up on D but the cost you pay will depend on your decisions on which path to choose. Later on in this blog we will discuss an algorithm to find the path with minimal cost. Now, take a look at the second graph in which we have a cycle between nodes A, B and C. The cost will increase each time you re-enter the cycle and might occur infinitely depending on your code. Later on we will take a look at how to find these cycles in a graph.
After all this theory I hope the coder in you is still eager to open up your fav text editor and ready to encounter some errors! Before we move on to coding, I would like to explain one last thing which is how to represent Graphs in your code. There are two ways to represent graphs:
Adjacency Matrix
Adjacency List
For a graph G = (V,E) with n and m elements in V and E respectively, adjacency matrix will be a nxn matrix with each cell containing the weight of the edge connecting the two vertices. On the other hand, adjacency list contains a linked list corresponding to the vertex and shows the various vertices it is connected to.
Directed Weighted Graph
Undirected Unweighted graph
Let’s see if you grasp the concept or not. For the undirected and unweighted graph above, try to write the adjacency matrix and the adjacency list. Take your time! Following is the answer:
Adjacency Matrix for the undirected unweighted graph
Adjacency list for undirected unweighted graph
I have given you the solution to unweighted graphs but now try to make the Adjacency Matrix and Adjacency List for the weighted graph specified above. If you have any problems or doubts, feel free to reach out to me via comments or email me.
Let’s get our hands dirty with some code! As you might already know, every code will be in Python.
from collections import defaultdict #defaultdict is used for initializing the dictionary with empty list
class Graph:
def __init__(self, N):
self.N = N
self.graph = defaultdict(list)
def addEdge(self, v, u):
self.graph[v].append(u) # Node v is connected to node u
self.graph[u].append(v) # Node u is connected to node v
g1 = Graph(5)
g1.addEdge(1, 0)
g1.addEdge(0, 2)
g1.addEdge(0, 3)
g1.addEdge(3, 4)
print(g1.graph)
"""
Output:
defaultdict(<class 'list'>,
{1: [0],
0: [1, 2, 3],
2: [0],
3: [0, 4],
4: [3]})
"""
The above python program incorporates the Adjacency List approach to representing Graphs. If you notice, the program will only show connected graphs. If there are nodes which are not connected to any node, they will not be considered. Now I will show you the representation using Adjacency Matrix.
class Graph:
def __init__(self, N):
self.N = N
self.graph = [[0]*N for _ in range(N)] #initializing the matrix with 0s to specify that no nodes are yet connected
def addEdge(self, v, u):
self.graph[u][v] = 1 # Edge from u to v exists
self.graph[v][u] = 1 # Edge from v to u exists
g1 = Graph(5)
g1.addEdge(1, 0)
g1.addEdge(0, 2)
g1.addEdge(0, 3)
g1.addEdge(3, 4)
print(g1.graph)
"""
Output:
[[0, 1, 1, 1, 0],
[1, 0, 0, 0, 0],
[1, 0, 0, 0, 0],
[1, 0, 0, 0, 1],
[0, 0, 0, 1, 0]]
"""
In this approach every node is taken into consideration which makes the complexity of traversal θ(n^2) whereas the complexity of traversal in Adjacency List is θ(m+n). For a more detailed comparison you can take a look at The Algorithm Design Manual by Steven S Skiena but for the crux of it:
Extract from The Algorithm Design Manual by Steven S Skiena
In the next session, we’ll take a look at various algorithms used for traversing graphs and how they are used for solving problems.
Big-O Blog 