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

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.

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

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

//This is start node
visited = true;

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

for(int i=1; i< this.G.length; i++){
if(this.G[u][i] && !visited[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.

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

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

//This is start node
visited = true;

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

/*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]){
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 communications@algorithmsandme.com

## 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.
*/
private boolean [][] G;
private 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){
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");
}
}
}

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.
*/
private Map<Integer, ArrayList<Integer>> G;
boolean isDirected;

this.G = new HashMap<>();
this.isDirected = isDirected;
}

public void addEdge(int start, int dest){

if(this.G.containsKey(start)){
}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) {
}
}

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){
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");
}
}
}

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.

## Connected components in graph

Given an undirected graph, find the number of connected components in it.

A connected component of an undirected graph is a maximal set of nodes such that each pair of nodes is connected by a path

Every vertex of the graph lies in a connected component that consists of all the vertices that can be reached from that vertex, together with all the edges that join those vertices. If an undirected graph is connected, there is only one connected component. Every graph has at least one connected component that is the graph itself.

For example in below graph, there are two connected components {1,2,3,4} and {5, 6}. ### How to find the number of connected components in a graph?

We can find the number of Connected components in a graph by traversing the graph, either depth first traversal or breadth first traversal.

If we start from a node v and do a traversal of the graph, we will be able to reach all the nodes which are connected to this node through any path. These are the vertices which are part of this connected component.
Now, if there are some vertices still unvisited, then there must be another component of the graph. We start traversal again with the first unvisited vertex. We continue this until all the vertices are visited.

In the following implementation, we are using Depth First traversal of the graph to find the number of components.

#### Connected components of a graph: implementation

Implementation with adjacency list representation of graph

```package com.company.Graphs;

import java.util.*;

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

this.G = new HashMap<>();
this.isDirected = isDirected;
}

public void addEdge(int start, int dest){

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

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

private void DFS(int node, boolean[] visited,
ArrayList<Integer> traversal){
if(!visited[node]){
visited[node] = true;

this.G.get(node).forEach(v -> DFS(v, visited, traversal));
}
}

public int connectedComponents(){

boolean[] visited = new boolean[this.G.size()];
int components = 0;

for(int i=1; i<this.G.size(); i++) {
ArrayList<Integer> traversal = new ArrayList<>();
if(!visited[i]) {
DFS(i, visited, traversal);
System.out.println(traversal);
components++;
}
}

return components;
}
}
```

Implementation using adjacency matrix representation of graph

```package com.company.Graphs;

import java.util.ArrayList;
import java.util.Queue;
import java.util.Stack;

/**
* Created by sangar on 21.12.18.
*/
private boolean [][] G;
private 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;
}
}

private void DFS(int node, boolean[] visited,
ArrayList<Integer> traversal){
if(!visited[node]){
visited[node] = true;

for(int i=1; i< this.G.length; i++){
if(this.G[node][i]){
DFS(i, visited, traversal);
}
}
}
}

public int connectedComponents(){

boolean[] visited = new boolean[this.G.length];
int components = 0;

for(int i=1; i<this.G.length; i++) {
ArrayList<Integer> traversal = new ArrayList<>();
if(!visited[i]) {
DFS(i, visited, traversal);
System.out.println(traversal);
components++;
}
}
return components;
}
}
```

If an adjacency list representation is used, the for loop will run for i from 0
to V each time it is executed, so the runtime for the adjacency list representation is O(V2).

For an adjacency list representation of a graph, run time for the algorithm is `O(V + E)`.

Please share if there is something wrong or missing. If you are preparing for an interview and want to get a free coaching session, please reach out to us at communications@algorithmsandme.com

## Detect cycle in undirected graph

Given an undirected graph, find if there is a cycle in that undirected graph. For example, below graph has cycles as 2->3->4->2 and 5->4->6->5 and a few more. A simple definition of a cycle in an undirected graph would be: If while traversing the graph, we reach a node which we have already traversed to reach the current node, then there is a cycle in the graph.

How can we detect the above condition? It’s an application of Depth First Search. Do a depth-first traversal of a graph. In depth first traversal, we visit the current node and go deep to one of its unvisited neighbors. If a neighbor of the current node is already visited, that means there is a possibility of a cycle. However, make sure that the already visited neighbor is not the parent of the current node, otherwise, there will be always a cycle of two nodes in an undirected graph.

While depth first traversing a graph, keep track of the nodes which are on the stack at present. If there is an edge from the current node to any one of the nodes which are on recursion stack, we say there is a cycle in undirected graph.

To avoid additional space, we can pass the parent pointer to the recursive call and check if the visited node is the parent.

#### Detect cycle in undirected graph: implementation

```
package com.company.Graphs;

import java.util.*;

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

this.G = new HashMap<>();
this.isDirected = isDirected;
}

public void addEdge(int start, int dest){

if(this.G.containsKey(start)){
}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) {
}
}

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

return false;
}

private boolean isCycleUtil(int u, boolean[] visited, int parent){

for(int v: this.G.get(u)) {
if(!visited[v]){
visited[v] = true;
return isCycleUtil(v, visited, u);
}
else if(v != parent){
return true;
}
}

return false;
}

public boolean isCycle(){
boolean[] visited = new boolean[this.G.size() + 1];

for(int i = 1; i < this.G.size() + 1; i++) {
if (!visited[i]) {
return isCycleUtil(i, visited, -1);
}
}
return false;
}
}
```

The complexity of the DFS approach to finding a cycle in an undirected graph is `O(V+E)` where V is the number of vertices and E is the number of edges.

Please share if there is something wrong or missing. If you are preparing for an interview, please singup for free interview preparation material.

## Depth first traversal of a graph

In the last post, we discussed how to represent a graph in a programmatic way using adjacency matrix and adjacency list representation. Let’s discuss now, how to traverse a graph. There are two ways to traverse a graph: Depth First traversal, commonly called DFS and Breadth First traversal, commonly called as BFS.

### What is Depth First Traversal (DFS) ?

Depth First search or traversal is a technique in which we go as deep in the graph as possible and explore nodes, that is we move down the graph from one node to another till we can. Once we reach a node where we cannot go further down, we backtrack and move to node one before and so on.
A depth-first traversal of a graph is a very good example to understand how backtracking works.

Let’s see how do we traverse a graph depth first.

2. If u is already visited, return.
3. Mark `visited[u] = true`.
4. For all neighbors v of u.
5. v is now new u, so `u=v` and go back to step 2
6. When all neighbors are processed, backtrack to parent of current u.

When we reach at start node S again and there is no edge to be explored at S, that would be the end of traversal.

Let’s take an example and see how it works. Given the graph below, let’s trace how depth first search will go. We start with `node(1)`, and mark it as visited. Now, we pick neighbor of `node(1)`, and go down to `node(2)` and mar it as visited too. Next, we move to the neighbor of `node(2)`, which is `node(3)`. After marking `node(3)` visited, we move to `node(4)`. Next, we move to `node(6)`. At this point, we have no neighbors to visit from `node(6)`. So, we start backtracking. At `node(2)`, we have another neighbor called `node(4)`, however, node(4) is already visited when we went deep from node(3). So nothing happens, we move further back. At `node(1)`, we have neighbor node(5).
Since `node(5)` is not visited, we mark it as visited. At this point, there is no node with neighbor not traversed, so end of depth-first traversal.

#### Depth first traversal : implementation

```package com.company.Graphs;

import java.util.ArrayList;

/**
* Created by sangar on 21.12.18.
*/
private boolean [][] G;
private 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];
}

private void DFS(int node, boolean[] visited,
ArrayList<Integer> traversal){
if(!visited[node]){
visited[node] = true;

//Complexity of this loop is O(V * E)
for(int i=1; i< this.G.length; i++){
if(this.G[node][i]){
//This will be called E times (number of edges)
DFS(i, visited, traversal);
}
}
}
}
public ArrayList<Integer> depthFirstTraversal(){

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

DFS(1, visited, traversal);

System.out.println(traversal);
return traversal;

}
}

```

The complexity of the above implementation is `O(V * E)`.

Depth first traversal when the graph is represented using adjacency list.

```package com.company.Graphs;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

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

this.G = new HashMap<>();
this.isDirected = isDirected;
}

public void addEdge(int start, int dest){

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

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

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

return false;
}

private void DFS(int node, boolean[] visited,
ArrayList<Integer> traversal){
if(!visited[node]){
visited[node] = true;

this.G.get(node).forEach(v -> DFS(v, visited, traversal));
}
}
public ArrayList<Integer> depthFirstTraversal(){

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

DFS(1, visited, traversal);

System.out.println(traversal);
return traversal;

}
}

```

The complexity of the above implementation is `O(V + E)`.

Both above implementations are recursive implementation. We can use a stack to replace recursion. Algorithm remains the same, for each node visited, put all the adjacent nodes into the stack. Take next node from the stack, mark it as visited and put all the adjacent nodes to stack. Repeat the process till stack is not empty.

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

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

Stack s = new Stack();
s.push(1);
visited = true;

while(!s.isEmpty()){
int currentNode = (int)s.pop();

for(int i=1; i< this.G.length; i++){
if(this.G[currentNode][i] && !visited[i]){
s.push(i);
visited[i] = true;
}
}
}

System.out.println(traversal);
return traversal;

}
```

This implementation of dept first traversal or DFS works only if the graph has only one connected component. If there are multiple connected components in the graph, this will not work. For example, above implementation will not work for below graph.

It can be easily fixed. All we need to do is that we try to start DFS from each node of the graph. Check if a node is not already visited for earlier DFS run, then start another DFS from that node. Below is the changed code.

```  private void DFS(int node, boolean[] visited,
ArrayList<Integer> traversal){
if(!visited[node]){
visited[node] = true;

for(int i=1; i< this.G.length; i++){
if(this.G[node][i]){
DFS(i, visited, traversal);
}
}
}
}
public ArrayList<Integer> depthFirstTraversal(){

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

for(int i=1; i<this.G.length; i++) {
if(!visited[i])
DFS(i, visited, traversal);
}

System.out.println(traversal);
return traversal;
}
```

### Applications of DFS

1. Minimum spanning tree
2. To check if graph has a cycle.
3. Topological sorting
4. To find strongly connected components of graph
5. To find bridges in graph

Please share if there something wrong or missing. Please reach out to communications@algorithmsandme.com if you need personalized coaching for an interview.