## Rotten oranges problem

Rotten oranges problem goes like: In a given grid, each cell can have one of three values:

• the value 0 representing an empty cell;
• the value 1 representing a fresh orange;
• the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten. Return the minimum number of minutes that must elapse until no cell has a fresh orange.  If this is impossible, return `-1` instead.

```Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten because rotting only happens 4-directionally.
``` ## Thoughts

Rotting oranges problem offers a unique perspective on identifying a graph search problem. At first glance, it seems like the solution to the problem lies in changing the status of the given grid on multiple time steps while counting the steps and making sure that we come to a conclusion to our iterations, akin to solving a sudoku puzzle, where the state of the entire grid matters.

On further inspection though, we can see that we do not need to worry about the state of the entire grid, just the fresh oranges adjacent newly rotting oranges at each time step. We can consider the oranges as nodes of a graph, and the fresh oranges around them as connected to these nodes. We do not know the entire state of the graph beforehand, but we know that the adjacent nodes will expose themselves as time passes. This pushes us towards the idea of a Breadth-First Search, where we topologically move level by level through a graph.

This problem also has some interesting edge cases, with it being necessary to parse the graph to identify such cases:

### Show me the implementation

```class Solution:
def orangesRotting(self, grid: List[List[int]]) -&gt; int:
# Make sure we have a valid grid
if len(grid) &lt; 1 or len(grid) &lt; 1:
return -1
sources = []
ones = 0
for i in range(len(grid)):
for j in range(len(grid[i])):
if grid[i][j] == 2:
sources.append((i, j))
elif grid[i][j] == 1:
ones += 1
if len(sources) == 0:
# In case of no rotten oranges, return value depending
# on the state of the grid
if ones == 0:
return 0
else:
return -1
directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
# Grid is initially at t = -1
count = -1
visited = set(sources)
# End the BFS when there are no new sources left
while len(sources) &gt; 0:
count += 1
newsources = []
for source in sources:
i, j = source
grid[i][j] = 2
for direction in directions:
row = i + direction
col = j + direction
# Make sure it is a valid row and column,
# It is not visited, and it is a fresh orange
if row &gt;= 0 and row &lt; len(grid) \
and col &gt;= 0 and col &lt; len(grid) \
and (row, col) not in visited and grid[row][col] == 1:
newsources.append((row, col))
visited.add((row, col))
sources = newsources
# Make sure there are no fresh oranges left in the grid
for i in grid:
for j in i:
if j == 1:
return -1
return count
```

The runtime complexity of BFS is O(V + E), which in our scenario translates to moving to every node, i.e. O(n * m) where n and m are dimensions of the grid. The space complexity of BFS is O(V), which similarly as time complexity translates into O(n*m)

This article is contributed by Khushman Patel

Posted on Categories Facebook interview questions, GraphLeave a comment on Rotten oranges problem

## Find friend groups

There are Nstudents in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if Ais a direct friend of B, and Bis a direct friend of C, then Ais an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.

Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the `i`th and `j`th students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students. For example,

```Input:
[[1,1,0,0,0,0],
[1,1,0,0,0,0],
[0,0,1,1,0,0],
[0,0,1,1,1,0],
[0,0,0,1,1,0],
[0,0,0,0,0,1]
]
Output: 3```

## Thought process

When we talk about the connections or relationships, we immediately will think of graph data structure. The node is the person and the edge is the relationship between two persons. So, first, we have to figure out whether it will be a directed graph or an undirected graph. In this problem, the friendship is a mutual relationship, thus the graph is undirected.

When you are reading this problem, the concept of Strongly Connected Components(SCC) will come into your mind. Ok, we will discuss why? If A is a friend of B, B is a friend of C, then A will be a friend of C. What does it mean? A is indirectly connected to C. It means that every friend can reach every other friend through a path if they are directly or indirectly connected. So in this way, they are forming a strong group or circle, in which every vertex is connected directly or indirectly in its group/circle. Notice that all friends (both direct and indirect), who should be in one friend circle are also in one connected component​ in the graph.

A particular group of friends is a single component. In this problem we are going to find out how many components are there in the graph. When you make a graph out of it. It will be like this(see below fig). It means there are 3 friends circles. We can solve this problem using 2 methods: depth first search and disjoint set method

## Using Depth first traversal method

Finding connected components for an undirected graph is very easy. We can do either BFS or DFS starting from every unvisited vertex, and we get all strongly connected components

```1. Initialize all nodes as not visited.
2. Initialize variable count as 1.
3. for every vertex 'v'.
(i) If 'v' is unvisited
Call DFS(v)
count=count+1
DFS(v)
1. Mark 'v' as visited.
2. Do following for every unvisited neighbor `u`
recursively call DFS(u)```

### DFS based approach implementation

```class Solution {
Public:
void DFS(int node,vector<vector<int>> edges,vecto<bool>visited)
{
int i;
visited[node]=true;
for(int i=0;i<edges[node].size();i++)
{
if(edges[node][i]==1 && node!=i && visited[i]==false)
{
DFS(i,edges,visited);
}
}
}

//Main Method
int findCircleNum(vector<vector<int>> edges) {
int i,j;

int n=edges.size();
int count=0;
vector<bool>visited(m);

//mark all the nodes as unvisited
for(i=0;i<n;i++)
{
visited[i]=false;
}

for(i=0;i<n;i++)
{
if(visited[i]==false)
{
DFS(i,edges,visited);
count=count+1;
}
}

return count;
}
};
```

Complexity

• Time Complexity: Since we just go along the edges and visit every node, it will be O(n).
• Space Complexity: O(n), to store the visited nodes.

## Using Disjoint Sets(Union Find)

So, how to think that this problem is solved by Disjoint Sets(union-find algorithm)?

The answer is simple because we need to keep track of the set of elements(here friends) partitioned into a number of non-overlapping subsets. Disjoint Sets(Union Find) always do this work very efficiently. We will use the Union by Rank algorithm to solve this problem.

If you haven’t heard of the Disjoint Sets. Go to this link and read about it.

To join two nodes, we will compare the rank of parents of both nodes.

• If the rank is equal, we can make any one of the parent’s node as a parent and increment the rank of the parent node by 1.
• If the rank is not same, then we can make the parent whose rank is greater than other. Let’s start solving this.

Union(1,2): 1 is a parent of itself and 2 is parent of itself. As both of them have different parents, so we have to connect them, and we will any of the parent as root, in this case we chose 1 and make it a parent. Union(2,1): 1 is a parent of itself and 1 is a parent of 2, as both of them have the same parents, already joined.

Union(3,4) :3 is a parent of itself and 4 is a parent of itself. Both of them have different parents, we need to join them. Union(4,3): 3 is parent of itself and 3 is the parent of 4. Both of them have the same parents, already joined.

Union(4,5):   3 is the parent node of 4 and 5 is the parent node of 5. Since parents are different, we have to compare the rank of the parents of both 4 and 5 nodes. 3 has higher rank then 5, it will be parent of 5 .(Used Path Compression) as shown in the below fig. Union(5,4): As now, 4 and 5 have the same parents, already joined. Last is the node 6 which connected to itself. So, nothing to do there. At the end of this exercise, we found that there are three different sets in the graph, and that is our answer of number of groups of friends in this graph or matrix.

### Disjoint set based approach implementation

```class Solution {
public:
class Node
{
public:
int data;
Node*parent;
int rank=0;
};
//make a set with only one element.
void make(int data)
{
Node*node=new Node();
node->data=data;
node->parent=node;
node->rank=0;
mapy[data]=node;
return;
}
map<int,Node*> mapy;
//To return the address of the particular node having data as `data`
Node*find(int data)
{
auto k=mapy.find(data);
if(k==mapy.end())
{
//There is no any node created, create the node
make(data);
return mapy[data];
}
else
{
return mapy[data];
}
return NULL;
}
/*Find the representative(parent) recursively and does path compression
as well*/
Node*parents(Node*node)
{
if(node->parent==node)
{
return node;
}
return node->parent = parents(node->parent);
}
//Main Method
int findCircleNum(vector<vector<int>>edges) {
int i,j;

vector<int> v;
int m=edges.size();
int n=edges.size();
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(edges[i][j]==1)
{
int a=i;
int b=j;

Node*A=find(a);
Node*B=find(b);

Node*PA=parents(A);
Node*PB=parents(B);

if(PA==PB)
{
}
else
{
if(PA->rank>=PB->rank)
{
//increment rank if both sets have Same rank
PA->rank=(PA->rank==PB->rank)?PA->rank+1:PA->rank;
PB->parent=PA;
}
else
{
PA->parent=PB;
}
}

}
}
}

int number=0;
for(auto k: mapy)
{
if(k.second->parent==k.second)
{
number=number+1;
}
}
return number;
}
};
```

Complexity

• Time Complexity: For each of the edge, we need to find the parents  and do the union, which is O(mlogn).
• Space Complexity: We used a map to store the parent information, O(n).

This post is contributed by Monika Bhasin
Posted on Categories Algorithms, Amazon Interview questions, GraphLeave a comment on Find friend groups

## Tarjan’s Algorithm to find strongly connected components

Tarjan Algorithm is a very useful algorithm in finding strongly connected components in a directed graph. What is a strongly connected component?

## What is Strongly Connected Component?

A directed graph is said to be strongly connected if we can reach any node from every other node in the graph. A strongly connected component of a directed graph is a subset of the nodes in the graph such that any two nodes of this subset are reachable from each other.
For any two nodes u and v in graph, if they are part of a strongly connected component, there exists a path from u to v and vice-a-versa.

For example, in the graph given below, there are 4 strongly connected components. There are two algorithms to strongly connected components one is Kosaraju’s algorithm and another one is the Tarjan algorithm.
Tarjan algorithm requires only one depth-first search traversal to find out all strongly connected components present in the graph. It is efficient as compared to Kosaraju’s algorithm as the other requires two DFS traversal.
An important thing to known to understand Tarjan’s algorithm is that depth-first traversal creates a DFS tree, meaning when we traverse a graph, it does traversal in a manner that a node is not visited again.

## Tarjan’s algorithm to find Strongly Connected Component?

Fundamental is very simple: From a node u if we can reach to any of its ancestors for any of its descendants (including itself), then there must be a cycle containing this node, all these nodes should be part of the same connected component.

For example, if x is the root of the tree and y is the descendant of x and there is an edge from y to another node z that is an ancestor of x, then we can say that edge y – Z together with the paths in the DFS tree from z to x and from x to z form a cycle, which must all be part of the same component. The edge from y to z is called back edge.

How can we know if there is a back-edge from a node to another? We keep track of two things for each node v of the graph:

```tin[v]: Represents the number of node visited before v in DFS.
low[v]: Represents smallest tin[x] of a node reachable by a back edge from the subtree of v.
```

The below figure displays tin[i] for each node. In the simplest way, it can be calculated as in-time of the node in depth-first traversal. The interesting part is how to calculate low[i]? To start with, low[i] is the node the node i itself. Going forward, for each node u, go through its neighbors:
1. If the neighbor v not already visited, that means, it is not a back edge. We will go forward and do the DFS on the v. Once DFS is finished, we will update the low[u] as follows:

low[u] = min(low[u], low[v]).

2. If the node v is already visited, that means there is a back edge from node v to any of the ancestor of node u. In that case, low[u] will be defined as follows

low[u] = min(low[u], tin[v]) For node v, if tin[v] == low[v], v is then the root of the next connected component. If you want to print nodes in strongly connected components, keep track of them on the stack. As soon as we get a node with low[i] == tin[i], pop all the nodes from the stack till we get the node i. All of these nodes belong to same SCC.

If low[v] > tin[u], we can say that node u and v belong to different SCCs and edge (u,v) is a bridge edge.

### Tarjan's algorithm to find strongly connected components

```package AlgorithmsAndMe;

import java.util.*;

public class TarjansAlgorithm {

Set<Integer> visited = new HashSet<>();
/* This map stores the time when the
current node is visited
*/
int [] tin;
/*
low will store minimum on
tin[v]
tin[p] for all p for which (v,p) is a back edge
low[to] for all to for which (v,to) is a tree edge
*/
int [] low;

//To maintain monotonic increasing order.
int timer;

void dfs(Graph g, int u, int parent, Stack<Integer> stack) {
visited.add(u);

//Put the current timer.
tin[u] = timer;
//Low is the time of entry to start with
low[u] = timer;

stack.push(u);
timer++;

/*
Go through all the neighbors
*/
for (int to : g.getNeighbors(u)) {
//If it is parent, nothing to be done
if (to == parent) continue;

/* If the neighbor was already visited
get the minimum of the neighbor entry time
or the current low of the node.
*/
if (visited.contains(to)) {
low[u] = Math.min(low[u], tin[to]);
} else {
//Else do the DFS
dfs(g, to, u,stack);
/*
Normal edge scenario,
take the minimum of low of the parent and the child.
*/
low[u] = Math.min(low[u], low[to]);
}
}

System.out.println();
if (low[u] == tin[u]){
//Print the stack.
while(!stack.isEmpty() && stack.peek() != u){
System.out.print(stack.pop() + " ");
}
System.out.print(u + " ");
stack.pop();
}
}

public void findConnectedComponents(Graph g) {
timer = 0;
Stack<Integer> stack = new Stack<>();
Iterator it = g.getNodes().iterator();

tin = new int[g.getSize() + 1];
low = new int[g.getSize() + 1];
Arrays.fill(tin, Integer.MAX_VALUE);
Arrays.fill(low, Integer.MAX_VALUE);

while(it.hasNext()){
int i = (int) it.next();
if (!visited.contains(i))
dfs(g, i, -1, stack);
}
}
}
```

As we can see from the code that we only need one DFS traversal,therefore compexity of the algorithm will be O(|V| + |E|), where V and E are total number of vertex and edges present in the graph.

### Problems solved using algorithm

Please write to us if you need coaching for your interview preparations.

Posted on Categories GraphLeave a comment on Tarjan’s Algorithm to find strongly connected components

## Critical Connections in a Network

There are n servers numbered from 0 to n-1 connected by undirected server-to-server connections forming a network where connections[i] = [a, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network.
critical connection is a connection that, if removed, will make some server unable to reach some other server.
For example,
Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted. Before going through this solution, I would strongly recommend reading Tarjan’s algorithm and find bridges in a graph problem.

```class Solution {
int timer;

List<List<Integer>> g;

boolean [] visited;
/* This map stores the time when the
current node is visited
*/
int [] tin;
int [] low;

void dfs(int u, int parent,
List<List<Integer>> res ) {
visited[u] = true;

//Put the current timer.
tin[u] = timer;
//Low is the time of entry to start with
low[u] = timer;

timer++;

/*
Go through all the neighbors
*/
for (int to : g.get(u)) {
//If it is parent, nothing to be done
if (to == parent) continue;

/* If the neighbor was already visited
get the minimum of the neighbor entry time
or the current low of the node.
*/
if (visited[to]) {
low[u] = Math.min(low[u], tin[to]);
} else {
//Else do the DFS
dfs(to, u, res);
/*
Normal edge scenario,
take the minimum of low of the parent
and the child.
*/
low[u] = Math.min(low[u], low[to]);

/* If low of the child node is less than
time of entry of current node, then
there is a bridge.
*/
if (low[to] > tin[u]){
//List<Integer> l = new ArrayList<>();
List<Integer> l =
Arrays.asList(new Integer[]{u, to});
res.add(l);
}
}
}

}

public void findBridges(List<List<Integer>> res) {
timer = 0;
for(int i=0; i<g.size(); i++){
if (!visited[i])
dfs(i, -1, res);
}
}

public List<List<Integer>> criticalConnections(int n,
List<List<Integer>> connections) {

g = new ArrayList<>();

visited = new boolean[n];
/* This map stores the time when the
current node is visited
*/
tin = new int[n];
low = new int[n];

Arrays.fill(visited, false);
Arrays.fill(tin, n);
Arrays.fill(low, n);

for(int i=0; i<n; i++){
g.add(new ArrayList<>());
}
for(List<Integer> l : connections){
g.get(l.get(0)).add(l.get(1));
g.get(l.get(1)).add(l.get(0));
}

List<List<Integer>> res = new ArrayList<>();
findBridges(res);

return res;

}
}
```

The complexity of this code is O(V + E) where V is number of vertices and E is number of edges in the graph.

If you want help with interview preparations, please feel free to book a free demo session with us.

Posted on 1 Comment on Critical Connections in a Network

## Matrix and graph traversals

Today, we will discuss an approach that can be used to solve quite a few problems with matrices. Problem structure is quite similar, you have a matrix, where cells represent real-world entities like land and water or oranges or walls and gates, etc. and we are asked to find something in that matrix. An example problem statement would be island problem. (taken from leetcode):

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. In this example, there are three islands.

Most of the time these problems have two entities, in the above example, its water and land. At first sight, this problem does not give any hint that it is a graph problem. For a problem to be a graph problem, it must have nodes and edges.

What are the nodes and edges of the graph?

One hint is to the relationship between the cells of the matrix. For example, in the island problem, 0s are water, and 1s are land. Land can be connected to land only which is adjacent to the land and a piece of land is isolated if surrounded by water from all four sides.

In this case, nodes seem to be the cells with value 1(land). Most of the time, in these kinds of problems, each cell of the matrix with a certain value is a node. If we have an n x m matrix, we are looking at n x m possible nodes. Also, here be aware that we are not interested in all the cells. Based on the problem statement, we can discard some cells. For example, in the island problem, we are interested in the cells which represent the land.

Now, what will be the edges? In these kinds of problems, a statement is given like an island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. It means that a cell with value 1 is connected to neighbor cells only if they also contain 1.

Now that we know that cells containing 1 in the matrix are nodes of the graphs and connected to neighbors in they are also 1. To count the number of islands, all we have to do is find connected components in the graph. We reduced a matrix problem to a graph problem after all. Should we create an entire graph? Well no, at any point in time, we do not need the entire graph.

Traversals of graphs like DFS or BFS need a node and its neighbors.

If we are at a particular cell of a matrix, we already know the node. With the problem definition, we can know which other cells can be a neighbor of this node. So, we do not need to actually convert the matrix to a graph but just mimic the getNeighbor(Node u) function of a graph.

## Number of islands

The problem statement is given above as an example, we already identified the nodes and edges of the graph implicit in the matrix. We also know that to find the number of islands in the matrix, we have to find the number of connected components in the graphs as explained above. Which traversal can we use to find the number of connected components of a graph? It is a depth-first search problem.

```  public int numIslands(char[][] grid) {
int count = 0;
Set<Integer> visited = new HashSet<>();

int n = grid.length;

if(n <=0) return 0;
int m = grid.length;

for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
int cell = i * m + j;
if(!visited.contains(cell) && grid[i][j] == '1'){
count++;
dfs(i, j, visited, grid);
}
}
}
return count;
}

void dfs(int i, int j, Set<Integer> visited, char[][] a){

//Check if the node we are traversing is actually a valid node.
if(i<0 || i>=a.length
|| j<0 || j>=a.length
|| a[i][j] == '0') return;

int cell = i * a.length + j;
if(visited.contains(cell)) return;
visited.add(cell);

//Visit neighbors
dfs(i+1, j, visited, a);
dfs(i-1, j, visited, a);
dfs(i, j+1, visited, a);
dfs(i, j-1, visited, a);
}
```

## Number of closed islands

There is another leetcode problem called Number of closed islands, it goes like:

Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s. Return the number of closed islands.

Again, the similar structure of the problem, a matrix, cells representing the land and water. The only difference is now we have to find which land pieces are connected to the corners. Cells with 0s are lands, so cells with value 0 are our nodes. We will do a DFS starting from each of these nodes and see if we hit boundaries of the matrix, in that case, the node all these nodes cannot be closed islands.

```  int numClosedIslands(int[][] g){
int count = 0;
for(int i = 0;i < g.length;i++){
for(int j = 0;j < g.length;j++){
/* Our node is all the cells with
value zero, we will do a DFS from each node
*/
if(g[i][j] == 0){
count += dfs(g,i,j);
}
}
}
return count;
}

private int dfs(int[][] g,int row,int col){
//if we meet the edge return 0;
if(row < 0 || row >= g.length
|| col < 0 || col >= g.length){
return 0;
}
//if we meet 1 return 1;
if(g[row][col] == 1){
return 1;
}

/* This is to make sure that
we do not visit same node again and again
*/
g[row][col] = 1;

/* Make sure that we do not reach to the boundaries
doing DFS. */
int up = dfs(g,row-1,col);
int down = dfs(g,row+1,col);
int left = dfs(g,row,col-1);
int right = dfs(g,row,col+1);

//any of the sides meet the edge, is not an island;
return up & down & left & right;
}
```

## Walls and gates problem

There is another problem which falls under the same criteria, the problem is known as walls and gates problem

Given a m x n 2D grid initialized with these three possible values. -1 – A wall or an obstacle. 0 – A gate. INF – Infinity means an empty room. We use the value 231 – 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.  Walls and gates solutions

In this problem, we have to find the distance to the room from gates and fill it with the minimum distance. Question number one, what are our nodes? In this problem, all the cells except the walls are nodes of the graph. Why walls are not nodes? Because one cannot go through the obstacles, so the cannot be part of the path of nodes, hence they cannot be considered as a node.

We can traverse horizontal and vertical, that means nodes at (i+1, j), (i-1, j), (i, j+1) and (i, j-1) are neighbors of cell (i,j) if they are a room or a gate.

To find the minimum distance from gates to a room, start a DFS from each gate and update the distance of the room with minimum distance seen so far. All we have to do it keep track of distance while starting from a gate.

```package AlgorithmsAndMe;

import java.util.HashSet;
import java.util.Set;

public class WallsAndGates {

public int[][] wallsAndGates(int[][] grid){

int n = grid.length;
if(n<=0) return new int;

int m = grid.length;

Set<Integer> visited = new HashSet<>();

for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
//This is our gate
if(grid[i][j] == 0){
dfs(i, j, grid, 0, visited);
}
}
}

return grid;
}

private void dfs(int x, int y, int[][] grid,
int distance, Set<Integer> visited){

int cellId = x*grid.length + y;
if(x<0 || x>=grid.length
|| y<0 || y>grid.length
|| grid[x][y] == -1
|| visited.contains(cellId)){
return;
}

//Mark as visited for this round.
visited.add(cellId);

//update the distance
grid[x][y] = Math.min(grid[x][y], distance);

dfs(x+1, y, grid, distance+1,visited);
dfs(x-1, y, grid, distance+1, visited);
dfs(x, y+1, grid, distance+1, visited);
dfs(x, y-1, grid, distance+1, visited);

//Mark unvisited for the next round.
visited.remove(cellId);

}
}
```

## Surrounded Regions

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’. A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

In this problem, again all the cells with zero are nodes, and edges are between the horizontal and vertical neighbors nodes. To capture all the nodes which are not connected to the edge of the matrix, first, find out which all are actually connected to the edge and mark them. Once we know all the nodes which are connected to the edge of the matrix, we can capture the nodes which are not connected.
To do so, we will start with nodes at the edge of the matrix and find the connected component of it and mark all the nodes in that connected component.

``` public void solve(char[][] grid) {
int n = grid.length;
if(n<=0) return;

int m = grid.length;

//Cover the first and last rows.
for(int j=0; j<m; j++){
if(grid[j] == 'O') dfs(0, j, grid);
if(grid[n-1][j] == 'O') dfs(n-1, j, grid);
}

//Cover the first and last columns.
for(int i=0; i<n; i++){
if(grid[i] == 'O') dfs(i, 0, grid);
if(grid[i][m-1] == 'O') dfs(i, m-1, grid);
}

for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(grid[i][j] == 'O') grid[i][j] = 'X';
if(grid[i][j] == '1') grid[i][j] = 'O';
}
}

return;
}

private void dfs(int x, int y, char[][] grid){

/* If we reach the edge of the node, return
Or we hit 'X', in that case, we cannot move
further in that direction.
*/
if(x<0 || x>=grid.length
|| y<0 || y>=grid.length
|| grid[x][y] == 'X'){
return;
}

if(grid[x][y] == 'O') {
grid[x][y] = '1';

dfs(x + 1, y, grid);
dfs(x - 1, y, grid);
dfs(x, y + 1, grid);
dfs(x, y - 1, grid);
}
}

```

The time complexity of all the solutions mentioned above is O(n * m) where n and m are rows and columns of the matrix. Because we will visit each cell at least once.
Please share if there is something wrong or missing. If you are preparing for an interviews and need help with it, please book a free session with us.

Posted on Categories Data Structures, GraphLeave a comment on Matrix and graph traversals

## Cycle in undirected graph using disjoint set

In post disjoint set data structure, we discussed the basics of disjoint sets. One of the applications of that data structure is to find if there is a cycle in a directed graph.

In graph theory, a cycle is a path of edges and vertices wherein a vertex is reachable from itself.

For example, in the graph shown below, there is a cycle formed by path : 1->2->4->6->1. Disjoint-set data structure has two operations: union and find. Union operation merges two sets into one, whereas find operation finds the representative of the set a given element belongs to.

### Using disjoint set to detect a cycle in directed grah

How can use the data structure and operations on it to find if a given directed graph contains a cycle or not?

We use an array A, which will store the parent of each node. Initialize the array with the element itself, that means to start with every node is the parent of itself.

Now, process each `edge(u,v)` in the graph and for each edge to the following: Get the root of both vertices u and v of the edge. If the roots of both nodes are different, update the root of u with the root of v. If roots are same, that means they belong to the same set and hence this edge creates a cycle.

How can we find the root of a vertex? As we know A[i] represents the parent of i; we start with i= u and go up till we find A[i] = i. It means there is no node parent of i and hence i is the root of the tree to which u belongs.

Let’s take an example and see how does it work. Below is the given directed graph and we have to if there is a cycle in it or not? To start with, we initialize array A with the elements themselves. Now, we process each node of the graph one by one. First is `edge(1,2)`. The root of `node(1)` is 1 and the root of `node(2)` is 2. Since the roots of two vertices are different, we update the parent of the root of 2 which is A to the root of 1 which is 1. Next, we process `edge(2,3)`, here root of the `node(2)` is 1, whereas the root `node(3)` is 3. Again they differ, hence update A[root of 3] with root 2, i.e A = 1; Now, process `edge(2,4)`, it will end up with A = 1, can you deduce why? And similarly `edge(4,6)` will also lead to update A = 1. Now, we process the `edge(6,1)`. Here, root of `node(6)` is 1 and also the root of `node(1)` is 1. Both the nodes have same root, that means there is a cycle in the directed graph. #### To detect a cycle in direct graph : Implementation

```package com.company.Graphs;

import java.util.*;

/**
* Created by sangar on 21.12.18.
*/
public class AdjacencyList {
private Map<Integer, ArrayList<Integer>> G;
private boolean isDirected;
private int count;

public AdjacencyList(boolean isDirected){
this.G = new HashMap<>();
this.isDirected = isDirected;
}

public void addEdge(int start, int dest){

if(this.G.containsKey(start)){
this.G.get(start).add(dest);
}else{
this.G.put(start, new ArrayList<>(Arrays.asList(dest)));
}

if(!this.G.containsKey(dest)) {
this.G.put(dest, new ArrayList<>());
}
//In case graph is undirected
if(!this.isDirected) {
this.G.get(dest).add(start);
}
}

public boolean isEdge(int start, int dest){
if(this.G.containsKey(start)){
return this.G.get(start).contains(dest);
}

return false;
}

public boolean isCycleWithDisjointSet() {
int[] parent = new int[this.G.size() + 1];

for (int u = 1; u < this.G.size() + 1; u++) {
//Process edge from each node.

//Find root of u
int i, j;

//Worst complexity is O(V)
for(i=u; i != parent[i]; i = parent[i]);

/*This loop will run for O(E) times for all
the vertices combined. */
for(int v: this.G.get(u)){
for(j=v; j != parent[j]; j = parent[j]);

if(i == j){
System.out.println("Cycle detected at
("+ u + "," + v + ")");
return true;
}

parent[i] = j;
}
}
return false;
}
}
```

Test cases

```package test.Graphs;

import com.company.Graphs.AdjacencyList;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
* Created by sangar on 21.12.18.
*/
public class AdjacencyListTest {
@Test
public void detectCycleInDirectedGraphTest() {

AdjacencyList tester = new AdjacencyList(false);

tester.addEdge(1,5);
tester.addEdge(3,4);
tester.addEdge(2,4);
tester.addEdge(1,3);
tester.addEdge(3,5);
tester.addEdge(5,2);

assertEquals(true, tester.isEdge(3,4));
assertEquals(false, tester.isEdge(1,4));

assertEquals(true, tester.isCycleWithDisjointSet());

}
}

```

Complexity of this algorithm is `O(EV)` where E is number of edges and V is vertices, where as union function in disjoint set can take linear time w.r.t to vertices and it may run for number of edge times.

Please share if there is something wrong or missing. If you are preparing for interview and interested in personalized coaching, please signup for free demo class.

Posted on Categories GraphLeave a comment on Cycle in undirected graph using disjoint set

## Disjoint set data structure

A disjoint set data structure or union and find maintains a collection 𝑆 = { 𝑆1, 𝑆2, ⋯ , 𝑆𝑛 } of disjoint dynamic sets. Subsets are said to be disjoint if intersection between them is NULL. For example, set {1,2,3} and {4,5,6} are disjoint sets, but {1,2,3} and {1,3,5} are not as intersection is {1,3} which is not null. Another important thing about the disjoint set is that every set is represented by a member of that set called as representative.

Operations on this disjoint set data structure:
1. Make Set: Creates a new set with one element x, since the sets are disjoint, we require that x not already be in any of the existing sets.
2. Union: Merges two sets containing x and y let’s say Sx and Sy and destroys the original sets.
3.Find: Returns the representative of the set which element belongs to.

Let’s take an example and see how disjointed sets can be used to find the connected components of an undirected graph.

To start with, we will make a set for each vertex by using make-set operation.

```for each vertex v in G(V)
do makeSet(v)
```

Next process all the edges in the graph (u,v) and connect set(u) and set(v) if the representatives of the set which contains u and set which contains v are not same.

```for each edge (u,v) in 𝐺(E)
do if findSet(u) != findSet(v)
then union(u, v)
```

Once above preprocessing steps have run, then we can easily find answer if two vertices u and v are part of same connected component or not?

```boolean isSameComponent(u, v)
if findSet(u)==findSet(v)
return True
else
return False
```

To find how many components are there, we can look at how many disjoint sets are there and that will give us the number of connected components in a graph. Let’s take an example and see how it works. Below table shows the processing of each edge in the graph show figure above. Now, how can we implement sets and quickly do union and find operations? There are two ways to do it.

### Disjoint set representation using an array

Simple implementation of disjoint set is using an array which maintains their representative of element i in A[i]. To this implementation to work, it is must that all the element in the set are in range 0 to N-1 where N is size of the array.

Initially, in makeSet() operation, set `A[i]=i`, for each i between 0 and N-1 and create the initial versions of the sets. ```for (int i=0; i<N; i++) A[i] = i;
```

Union operation for the sets that contain integers u and v, we scan the array A and change all the elements
that have the value A[u] to have the value A[v]. For example, we if want to connect an edge between 1 and 2 in the above set, the union operation will replace A with A. Now, if want to add an edge between 3 and 1. In this case, u = 3 and v = 1. A = 3 and A = 1. So, we will replace all the indices of A where A[i] = 1. So final array looks like this. Similarly, if want to add an edge from 6 to 7. ```//change all elements from A[u] to A[v].
void union(int A[], int u, int v){
int temp = A[u];
for(int i=0; i<A.length; i++){
if(A[i] == temp)
A[i] = A[v];
}
}
```

findSet(v) operation returns the value of A[v].

```int findSet(int A[], int v){
return A[v]
}
```

The complexity of makeSet() operation is `O(n)` as it initializes the entire array. Union operation take every time `O(n)` operations if we have to connect n nodes, then it will be `O(n2)` operations. FindSet() operation has constant time complexity.

We can represent a disjoint set using linked list too. In that case, each set will be a linked list, and head of the linked list will be the representative element. Each node contains two pointers, one to its next element it the set and other points to the representative of the set.

To initialize, each element will be added to a linked list. To union (u, v), we add the linked list which contains u to end of the linked list which contains v and change representation pointer of each node to point to the representation of list which contained v.

The complexity of union operation is again `O(n)`. Also, find operation can be `O(1)` as it returns the representative of it.

### Disjoint set forest

The disjoint-forests data structure is implemented by changing the interpretation of the meaning of the element of array A. Now each A[i] represents an element of a set and points to another element of that set. The root element points to itself. In short, A[i] now points to the parent of i.

Makeset operation does not change, as to start with each element will be the parent of itself.
Union operation will change, if we want to connect u and v with an edge, we update A[root of u] with the root of v. How to find the root of an element? As we have the relationship that A[i] is the parent of i, we can move up the chain until we find a case where `A[i] == i`, that case, i is the root of v.

```//finding root of an element
int root(int A[],int i){
while(A[i] != i){
i = A[i];
}
return i;
}

/*Changed union function where we connect
the elements by changing the root of
one of the elements
*/

int union(int A[] ,int u ,int v){
int rootU = root(A, u);
int rootV = root(A, v);
A[rootU] = rootV ;
}
```

This implementation has a worst-case complexity of `O(n)` for union function. And also we made the worst complexity of findSet operation as `O(n)`.

However, we can do some ranking on the size of trees which are being connected. We make sure that always root of smaller tree point to the root of the bigger tree.

```void union(int[] A, int[] sz, u, v){

//Finding roots
for (int i = u; i != A[i]; i = A[i]) ;
for (int j = v; j != A[j]; j = A[j]) ;

if (i == j) return;
//Comparing size of tree to put smaller tree root under
// bigger tree's root.
if (sz[i] < sz[j]){
A[i] = j;
sz[j] += sz[i];
}
else {
A[j] = i;
sz[i] += sz[j];
}
}
```

In the next few posts, we will be discussing applications of this method to solve different problems on graphs.
Please share if there is something wrong or missing. If you are preparing for an interview, and want coaching sessions to prepare for it, please signup for free demo session.

Posted on Categories Algorithms, Graph1 Comment on Disjoint set data structure

## Breadth First traversal

In the last post, we discussed depth first traversal of a graph. Today, we will discuss another way to traverse a graph, which is breadth first traversal. What is breadth first traversal? Unlike depth-first traversal, where we go deep before visiting neighbors, in breadth-first search, we visit all the neighbors of a node before moving a level down. For example, breadth first traversal of the graph shown below will be [1,2,5,3,4,6] In breadth first search, we finish visiting all the nodes at a level before going further down the graph. For example, the graph used in the above example can be divided into three levels as shown. We start with a node in level 1 which is `node(1)`. Then visit all the nodes which are one level below `node(1)` which are `node(2)` and `node(5)`. Then we visit all the node at level 3 which are `node(3)`, `node(4)` and `node(6)`.

### Breadth First Traversal: algorithm

1. Start with the given node u, put node u to queue
2. While queue is not empty, repeat below steps:
1. Dequeue fro queue and print node u.
2. For each neighbor of u, node v
3. If v is not visited already: add v to the queue
4. mark v as visited

Let’s take an example and see how it works. Below is the graph and we have to find BFS for this graph. We start from `node(1)`, and put it in the queue. While the queue is not empty, we should pop from it and print the node. In this case, `node(1)` will be printed. Next, we go through all the neighbors of `node(1)` and put all the unvisited node on the queue. `node(2)` and `node(5)` will go on to the queue and marked as visited. Traversal = {1} Again, we dequeue from the queue and this time we get `node(2)`. We print it and go for all the neighbor node, `node(3)` and `node(4)` and mark them as visited. Traversal = {1,2} `node(5)` is dequeued next and printed. Here, even though `node(4)` is a neighbor of `node(5)`, it is already visited and hence not put on to the queue again. But `node(6)` is not yet visited, so put it on to the queue. Traversal = {1,2,5} Now, we pop `node(3)` and print it, however, `node(4)` is already visited. Hence, nothing is added to the queue. Traversal = {1,2,5,3} Next, `node(4)` is taken out from queue and printed, nothing goes on to queue. Traversal = {1,2,5,3,4} Last, we pop `node(6)` and print it. Traversal = {1,2,5,3,4,6}. At this point, the queue is empty and we stop traversal.

#### Breadth first traversal: implementation

```public ArrayList<Integer> breadthFirstTraversal(){

boolean[] visited = new boolean[this.G.length];
ArrayList<Integer> traversal = new ArrayList<>();

Queue<Integer> q = new LinkedList<>();

//This is start node
q.add(1);
visited = true;

while(!q.isEmpty()){
int u = (int)q.remove();
traversal.add(u);

for(int i=1; i< this.G.length; i++){
if(this.G[u][i] && !visited[i]){
q.add(i);
visited[i]= true;
}
}
}
System.out.println(traversal);
return traversal;

}
```

The complexity of this code is `O(V2)` as at least V nodes will go in queue and for each nodes internal for loop runs V times.

Implementation of breadth-first search on graph represented by adjanceny list

```  public ArrayList<Integer> breadthFirstTraversal(){

boolean[] visited = new boolean[this.G.size()];
ArrayList<Integer> traversal = new ArrayList<>();

Queue<Integer> q = new LinkedList<>();

//This is start node
q.add(1);
visited = true;

//This loop will run for V times, once for each node.
while(!q.isEmpty()){
int u = (int)q.remove();
traversal.add(u);

/*This loop has a worst-case complexity of O(V), where
node has an edge to every other node, but
the total number of times this loop will run is E times
where E number of edges.
*/
for(int v : this.G.get(u)){
if(!visited[v]){
q.add(v);
visited[v]= true;
}
}
}
System.out.println(traversal);
return traversal;

}
```

The complexity of Breadth First Search is `O(V+E)` where V is the number of vertices and E is the number of edges in the graph.

The complexity difference in BFS when implemented by Adjacency Lists and Matrix occurs due to this fact that in Adjacency Matrix, to tell which nodes are adjacent to a given vertex, we take `O(|V|)` time, irrespective of edges. Whereas, in Adjacency List, it is immediately available to us, takes time proportional to adjacent vertices itself, which on summation over all vertices |V| is |E|. So, BFS by Adjacency List gives `O(|V| + |E|)`.

StackOverflow

When a graph is strongly connected, `O(V + E)` is actually `O(V2)`

### Applications of Breadth first traversal

1. To find shortest path between two nodes u and v
2. To test bipartite-ness of a graph
3. To find all nodes within one connected component

Please share if there is something wrong or missing. If you are preparing for an interview and want a free coaching session to guide you through it, please reach out to us at [email protected]

Posted on Categories Algorithms, Data Structures, Graph3 Comments on Breadth First traversal

## Topological sorting in a graph

Given a directed acyclic graph G (V,E), list all vertices such that for all edges (v,w), v is listed before w. Such an ordering is called topological sorting and vertices are in topological order. For example, topological sort for below graph would be: 1,2,3,5,4,6 A topological ordering is not unique and a DAG can have more than one topological sort. For example, for above graph, 1,5,2,3,6,4 is also correct topological sort.

### How to do a topological sort on a graph?

To start topological sort, we need a node which has zero incoming edges. If there is no such node in the graph, the graph is not directed acyclic graph, DAG. DAG will have at least one such node. Let’s G0 is the graph and V0 is the vertex with zero incoming node. So, V0 becomes the first vertex in order.
Now if we take out V0 and all the edges coming out from it, it leaves a graph G1, there must be a vertex V1 in G1 which has zero incoming edges. V1 is added to topological order.
TheV1 is removed from G1 which leaves us with G2 with TheV2 as candidate node. This goes on until there is no nodes remaining in the original graph G.

At any point in time, we cannot move forward, when there is no node with zero incoming nodes, it means there is a cycle in the graph and given graph is not a DAG.

Above description actually gives away the implementation detail too. We look for a vertex with zero incoming edges and take that. Then we remove all the edges coming out of that node from the graph, which will decrease the number of edges coming on to the neighbor nodes. Again select a node which has zero incoming edges and continues by removing edges.

Let’s take an example and work it out. #### Topological sort: implementation

```package com.company.Graphs;

import java.util.*;

/**
* Created by sangar on 21.12.18.
*/
public class AdjacencyMatrix {
private boolean [][] G;
private boolean isDirected;

public AdjacencyMatrix(int numNodes, boolean isDirected){
this.G  = new boolean[numNodes+1][numNodes+1];
this.isDirected = isDirected;
}

public void addEdge(int start, int dest){
this.G[start][dest] = true;
if(!isDirected){
this.G[dest][start] = true;
}
}

public boolean isEdge(int start, int dest){
return this.G[start][dest];
}

public ArrayList<Integer> topologicalSort(){

int[] inDegree = new int[this.G.length];
boolean[] visited = new boolean[this.G.length];
ArrayList<Integer> toplogicalOrder = new ArrayList<>();

//Complexity of O(n^2)
for(int i=1; i<this.G.length; i++) {
for (int j = 1; j < this.G.length; j++) {
if (this.G[i][j]) {
inDegree[j] += 1;
}
}
}
/* We will traverse each node */
for(int i=1; i<this.G.length; i++){
/* find a node with zero in degree */
int u  = findNextNode(inDegree, visited);
/* If there is no node with zero in degree,
topological sort not possible */
if(u != -1){
toplogicalOrder.add(u);
visited[u] = true;
/* decrease in degree of each node adjacent
to node wih zero in degree */
for(int v=1; v<this.G.length; v++) {
if (this.G[u][v]) {
inDegree[v]--;
}
}
}
else{
System.out.println("\n Topological sort no possible");
return toplogicalOrder;
}
}
return toplogicalOrder;
}

private int findNextNode(int indegree[], boolean[] visited){
for( int i=1; i< this.G.length; i++){
if(indegree[i] == 0 && !visited[i]){
return i;
}
}
return -1;
}
}
```

The complexity of topological sort implementation with adjacency matrix representation is O(V2). For each vertex we find the vertex with zero in-degree, hence the quadratic time.

Topological sort adjacency list represented graph

```package com.company.Graphs;

import java.util.*;

/**
* Created by sangar on 21.12.18.
*/
public class AdjacencyList {
private Map<Integer, ArrayList<Integer>> G;
boolean isDirected;

public AdjacencyList(boolean isDirected){
this.G = new HashMap<>();
this.isDirected = isDirected;
}

public void addEdge(int start, int dest){

if(this.G.containsKey(start)){
this.G.get(start).add(dest);
}else{
this.G.put(start, new ArrayList<>(Arrays.asList(dest)));
}

if(!this.G.containsKey(dest)) {
this.G.put(dest, new ArrayList<>());
}
//In case graph is undirected
if(!this.isDirected) {
this.G.get(dest).add(start);
}
}

public boolean isEdge(int start, int dest){
if(this.G.containsKey(start)){
return this.G.get(start).contains(dest);
}

return false;
}

public ArrayList<Integer> topologicalSort(){

int[] inDegree = new int[this.G.size()+1];
boolean[] visited = new boolean[this.G.size()+1];
ArrayList<Integer> topologicalOrder = new ArrayList<>();

//Complexity of O(V + E)
for(int u: this.G.keySet()){
for (int v : this.G.get(u)){
inDegree[v] += 1;
}
}

/* We will traverse each node */
for(int i=1; i<this.G.size()+1; i++){
/* find a node with zero in degree */
int u  = findNextNode(inDegree, visited);
/* If there is no node with zero in degree,
topological sort not possible */
if(u != -1){
topologicalOrder.add(u);
visited[u] = true;
/* decrease in degree of each node adjacent
to node wih zero in degree */
for(int v : this.G.get(u)) {
inDegree[v]--;
}
}
else{
System.out.println("\n Topological sort no possible");
return topologicalOrder;
}
}
return topologicalOrder;
}

private int findNextNode(int inDegree[], boolean[] visited){
for( int i=1; i< this.G.size()+1; i++){
if(inDegree[i] == 0 && !visited[i]){
return i;
}
}
return -1;
}
}

```

The complexity of this implementation is also `O(V2)` as still we scan all vertices to find the vertex with zero indegree.

Whenever we are updating the in-degree of all the adjacent node, we can store all the vertices for which in-degree becomes zero in a queue. So we don’t need to separately search for the node with zero in-degree, we can simply take the front of the queue, which will reduce the time complexity to `O(V + E)` with an additional space complexity of `O(V)`. This is called Kahn’s algorithm.

Below is the code for topological sorting using Depth First traversal. We are using a global variable here count. Idea is that all the nodes which are descendant of node u will come after vertex u in topological order. If we fill the array in reverse order, all the descendants will be filled up first and then the starting node.

```    private void topologicalSortDFS( int u, boolean[] visited,
int[] topologicalOrder) {
// Do a DFS starting from u
if ( ! visited[u] ) {
visited[u] = true;
for (int v: this.G.get(u)) {
topologicalSortDFS(v, visited, topologicalOrder);
}
this.count++;
topologicalOrder[ this.G.size() + 1 - this.count ] = u;
}
}

public void topologicalOrder() {

boolean[] visited = new boolean[this.G.size() + 1];
int[] topologicalOrder = new int[this.G.size() + 1];

for (int i = 1; i < this.G.size() + 1; i++) {
if (!visited[i]) {
topologicalSortDFS(i, visited, topologicalOrder);
}
}
Arrays.stream(topologicalOrder).forEach(i -> System.out.println(i));
}
```

The complexity of above implementation is `O(V + E)` with adjacency list represented graph.

Please share if there is something wrong or missing. If you are preparing for an interview and want to have personalized coaching for your preparation, please signup for free demo class.

Posted on Categories Algorithms, Data Structures, GraphLeave a comment on Topological sorting

# Dijkstra’s Algorithm to find shortest path

Given a graph, directed or undirected and two nodes, find the shortest path between these two nodes.
This is a standard problem and we don’t need to figure out what to do. We will have an adjacency list representation of the graph. The algorithm is widely published and is as below.

1. Initialize distance of all nodes from start node as INFINITE and all nodes as not finalized.
2. Take source node to start with, let’s say u.  Distance from source or start node to itself will be zero.
3. Mark u as considered and distance finalized.
4. Now for all neighbor nodes v of it, update the distance if the current distance is more than the distance of u + weight of (u,v).
For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6 + 2 = 8. If B was previously marked with a distance greater than 8 then change it to 8. Otherwise, keep the current value. {From Wikipedia}
5. Now select a node for which distance is not finalized and distance is minimum till now and make it u. Go to step 3.

Let’s work out an example and see how it works. Input graph is

To figure out the path which was followed to reach the destination from source, we can have an array to keep track of the parent node whenever distance to the node is updated. By reverse tracking parents from destination to source, we can figure out the path.

## Dijkstrat’s algorithm to find shortest path : Implementation

```#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define NUM_NODE 7
#define NUM_WORDS 10
#define NUM_CHAR 4
#define true 1
#define false 0

#define INFINITE 1000

typedef struct node{
int value;
int wt;
struct node *next;
}Node;

Node *graph[NUM_NODE + 1];

void add_edge_2(int i, int j, int wt);

int find_minimum_node(int visited[], int dist[]){
int min = INFINITE;
int index = -1;
int i;
for(i=1; i<= NUM_NODE; i++){
if(visited[i] == false && min>dist[i]){
min = dist[i];
index = i;
}
}
return index;
}

void dijstras(Node * graph[], int start, int end ){
int i;
int parent[NUM_NODE +1];
int distance[NUM_NODE+1];
int visited[NUM_NODE+1];

for(i=1; i<=NUM_NODE; i++){
visited[i] = false;
distance[i] = INFINITE;
parent[i] = -1;
}
// Mark distance of start as 0.
distance[start] =0;
for(i=1; i<=NUM_NODE; i++){
int index  = find_minimum_node(visited, distance);
if(index != -1){
Node * node = graph[index];
Node * current  = node->next;

while(current){
/*If neihbour node is not visited and its current distance is
more than distance of current node + cost of edge between
current node and this node, update the distance */
if(visited[current->value] == false && distance[current->value] >
distance[node->value] + current->wt){

distance[current->value] = distance[node->value] + current->wt;
parent[current->value] = node->value;
}
current = current->next;
}
visited[node->value] = true;
if(node->value == end)
break;
}
else{
break;
}
}

printf("\nDistance between %d and %d : %d", start , end, distance[end]);

// Printing path in reverse order,using stack, we can print it normal order to.
printf("\nPath is  (In reverse order): ");
int cur_parent =0;
while(cur_parent != -1){
printf("%d ", end );
cur_parent = parent[end];
end = cur_parent;
}
printf("\n");
}

Node *createNode(int j, int wt){

Node * new_node = (Node *)malloc(sizeof(Node));
if(new_node){
new_node->value = j;
new_node->next = NULL;
new_node->wt = wt;
}
else{
printf("\n Node cannot be allocated");
}
return new_node;
}

void addEdge(int i, int j, int wt){

Node * temp = graph[i];
if(temp == NULL){
graph[i] = createNode(j, wt);
}
else{
while(temp->next){
temp = temp->next;
}
temp->next = createNode(j, wt);
}
}

//driver program
int main(){

int i,j;
for(i=1; i<=NUM_NODE; i++){
graph[i] = createNode(i,0);
}
// creating graph with weighted edges.
addEdge(1,2,4);
addEdge(1,3,8);
addEdge(2,3,9);
addEdge(2,4,9);
addEdge(3,4,2);
addEdge(2,5,10);
addEdge(3,6,1);
addEdge(4,5,7);
addEdge(4,6,9);
addEdge(5,6,6);
addEdge(6,7,2);
addEdge(7,5,5);

dijstras(graph, 1, 6);

return 0;
}
```

The complexity of the above code is O(V2) where V is the number of vertices in the graph. This can be reduced to O(E log V) by using heaps. Heaps will reduce the complexity of searching minimum weight cost from O(V) to O(log V).
Limitation of algorithm1. It does not work with negative weights.

Please share if there is anything wrong or missing.

Posted on Categories Algorithms, Data Structures, Graph, Greedy1 Comment on Dijkstra’s Algorithm to find shortest path