Shanto-Mariam University of Creative Technology

F i r s t D e s i g n U n i v e r s i t y in T h e R e g i o n

ASSIGNMENT NO: 01
Subject Name : Analysis of Design and Algorithm Lab
Subject Code : CSE 2338

Submitted By:
Name:
Dep: B.S.C in CSE (Evening)
Batch: 8th
Semester: 4st
ID:

Submitted To:
Pelob Chakrowborty
Lecturer
Department Of CSE & CSIT
SMUCT

Date Of Submitted: 18-05-2020

1. Implement Red-Black Tree Insertion and Deletion algorithm.
(Include algorithm and code separately)
Red-Black Tree Insertion Algorithm
In the previous post, we discussed introduction to Red-Black Trees. In this post, insertion is
discussed.
In AVL tree insertion, we used rotation as a tool to do balancing after insertion caused
imbalance. In Red-Black tree, we use two tools to do balancing.
1) Recoloring
2) Rotation
We try recoloring first, if recoloring doesn’t work, then we go for rotation. Following is
detailed algorithm. The algorithms has mainly two cases depending upon the color of uncle.
If uncle is red, we do recoloring. If uncle is black, we do rotations and/or recoloring.
Color of a NULL node is considered as BLACK.
Let x be the newly inserted node.
1) Perform standard BST insertion and make the color of newly inserted nodes as RED.
2) If x is root, change color of x as BLACK (Black height of complete tree increases by 1).
3) Do following if color of x’s parent is not BLACK and x is not root.
a) If x’s uncle is RED (Grand parent must have been black from property 4)
(i) Change color of parent and uncle as BLACK.
(ii) color of grand parent as RED.
(iii) Change x = x’s grandparent, repeat steps 2 and 3 for new x.

b) If x’s uncle is BLACK, then there can be four configurations for x, x’s parent (p) and x’s
grandparent (g) (This is similar to AVL Tree)
i) Left Left Case (p is left child of g and x is left child of p)
ii) Left Right Case (p is left child of g and x is right child of p)
iii) Right Right Case (Mirror of case i)
iv) Right Left Case (Mirror of case ii)
Following are operations to be performed in four subcases when uncle is BLACK.
All four cases when Uncle is BLACK
Left Left Case (See g, p and x)

Left Right Case (See g, p and x)

Right Right Case (See g, p and x)

Right Left Case (See g, p and x)

Examples of Insertion

Red-Black Tree Insertion Code

#include <bits/stdc++.h>
usingnamespacestd;
enumColor {RED, BLACK};
structNode
{
    intdata;
    boolcolor;
    Node *left, *right, *parent;
    Node(intdata)
    {
       this->data = data;
       left = right = parent = NULL;
       this->color = RED;
    }
};
classRBTree
{
private:
    Node *root;
protected:
    voidrotateLeft(Node *&, Node *&);
    voidrotateRight(Node *&, Node *&);
    voidfixViolation(Node *&, Node *&);
public:
    RBTree() { root = NULL; }
    voidinsert(constint&n);
    voidinorder();
    voidlevelOrder();
};
voidinorderHelper(Node *root)
{
    if(root == NULL)
        return;
  inorderHelper(root->left);
    cout << root->data << "  ";
    inorderHelper(root->right);
}
Node* BSTInsert(Node* root, Node *pt)
{
    if(root == NULL)
       returnpt;
    if(pt->data < root->data)
    {
        root->left  = BSTInsert(root->left, pt);
        root->left->parent = root;
    }
    elseif(pt->data > root->data)
    {
        root->right = BSTInsert(root->right, pt);
        root->right->parent = root;
    }
    returnroot;
}
voidlevelOrderHelper(Node *root)
{
    if(root == NULL)
        return;
  
    std::queue<Node *> q;
    q.push(root);
  
    while(!q.empty())
    {
        Node *temp = q.front();
        cout << temp->data << "  ";
        q.pop();
  
        if(temp->left != NULL)
            q.push(temp->left);
  
        if(temp->right != NULL)
            q.push(temp->right);
    }
}
  
voidRBTree::rotateLeft(Node *&root, Node *&pt)
{
    Node *pt_right = pt->right;
  
    pt->right = pt_right->left;
  
    if(pt->right != NULL)
        pt->right->parent = pt;
  
    pt_right->parent = pt->parent;
  
    if(pt->parent == NULL)
        root = pt_right;
  
    elseif(pt == pt->parent->left)
        pt->parent->left = pt_right;
  
    else
        pt->parent->right = pt_right;
  
    pt_right->left = pt;
    pt->parent = pt_right;
}
  
voidRBTree::rotateRight(Node *&root, Node *&pt)
{
    Node *pt_left = pt->left;
    pt->left = pt_left->right;
    if(pt->left != NULL)
        pt->left->parent = pt;
    pt_left->parent = pt->parent;
    if(pt->parent == NULL)
        root = pt_left;
    elseif(pt == pt->parent->left)
        pt->parent->left = pt_left;
    else
        pt->parent->right = pt_left;
    pt_left->right = pt;
    pt->parent = pt_left;
}
voidRBTree::fixViolation(Node *&root, Node *&pt)
{
    Node *parent_pt = NULL;
    Node *grand_parent_pt = NULL;
  
    while((pt != root) && (pt->color != BLACK) &&
           (pt->parent->color == RED))
    {
  
        parent_pt = pt->parent;
        grand_parent_pt = pt->parent->parent;
        if(parent_pt == grand_parent_pt->left)
        {
            Node *uncle_pt = grand_parent_pt->right;
            if(uncle_pt != NULL && uncle_pt->color == RED)
            {
                grand_parent_pt->color = RED;
                parent_pt->color = BLACK;
                uncle_pt->color = BLACK;
                pt = grand_parent_pt;
            }
  
            else
            {
                if(pt == parent_pt->right)
                {
                    rotateLeft(root, parent_pt);
                    pt = parent_pt;
                    parent_pt = pt->parent;
                }
                rotateRight(root, grand_parent_pt);
                swap(parent_pt->color, grand_parent_pt->color);
                pt = parent_pt;
            }
        }
        else
        {
            Node *uncle_pt = grand_parent_pt->left;
            if((uncle_pt != NULL) && (uncle_pt->color == RED))
            {
                grand_parent_pt->color = RED;
                parent_pt->color = BLACK;
                uncle_pt->color = BLACK;
                pt = grand_parent_pt;
            }
            else
            {
                if(pt == parent_pt->left)
                {
                    rotateRight(root, parent_pt);
                    pt = parent_pt;
                    parent_pt = pt->parent;
                }
                rotateLeft(root, grand_parent_pt);
                swap(parent_pt->color, grand_parent_pt->color);
                pt = parent_pt;
            }
        }
    }
  
    root->color = BLACK;
}
voidRBTree::insert(constint&data)
{
    Node *pt = newNode(data);
    root = BSTInsert(root, pt);
    fixViolation(root, pt);
}
voidRBTree::inorder()     {  inorderHelper(root);}
voidRBTree::levelOrder()  {  levelOrderHelper(root); }
intmain()
{
    RBTree tree;
  
    tree.insert(7);
    tree.insert(6);
    tree.insert(5);
    tree.insert(4);
    tree.insert(3);
    tree.insert(2);
    tree.insert(1);
  
    cout << "Inoder Traversal of Created Tree\n";
    tree.inorder();
  
    cout << "\n\nLevel Order Traversal of Created Tree\n";
    tree.levelOrder();
  
    return0;
}
Output:
Inoder Traversal of Created Tree
1234567
Level Order Traversal of Created Tree
6472513

Red-Black Tree Deletion Algorithm

1) Perform standard BST delete. When we perform standard delete operation in BST,

we always end up deleting a node which is either leaf or has only one child (For an
internal node, we copy the successor and then recursively call delete for successor,
successor is always a leaf node or a node with one child). So we only need to handle
cases where a node is leaf or has one child. Let v be the node to be deleted and u be
the child that replaces v (Note that u is NULL when v is a leaf and color of NULL is
considered as Black).
2) Simple Case: If either u or v is red, we mark the replaced child as black (No
change in black height). Note that both u and v cannot be red as v is parent of u and
two consecutive reds are not allowed in red-black tree.

3) If Both u and v are Black.

3.1) Color u as double black.  Now our task reduces to convert this double black to
single black. Note that If v is leaf, then u is NULL and color of NULL is considered as
black. So the deletion of a black leaf also causes a double black.

3.2) Do following while the current node u is double black and it is not root. Let
sibling of node be s.
(a): If sibling s is black and at least one of sibling’s children is red, perform
rotation(s). Let the red child of s be r. This case can be divided in four subcases
depending upon positions of s and r.
(i) Left Left Case (s is left child of its parent and r is left child of s or both children of
s are red). This is mirror of right right case shown in below diagram.
(ii) Left Right Case (s is left child of its parent and r is right child). This is mirror of
right left case shown in below diagram.
(iii) Right Right Case (s is right child of its parent and r is right child of s or both
children of s are red)
 (iv) Right
Left Case (s is right child of its parent and r is left child of s)

(b): If sibling is black and its both children are black, perform recoloring, and recur
for the parent if parent is black.

In this case, if parent was red, then we didn’t need to recur for prent, we can simply
make it black (red + double black = single black)
…..(c): If sibling is red, perform a rotation to move old sibling up, recolor the old
sibling and parent. The new sibling is always black (See the below diagram). This
mainly converts the tree to black sibling case (by rotation) and  leads to case (a) or (b).
This case can be divided in two subcases.
(i) Left Case (s is left child of its parent). This is mirror of right right case shown in
below diagram. We right rotate the parent p.
(iii) Right Case (s is right child of its parent). We left rotate the parent p.

3.3) If u is root, make it single black and return (Black height of complete tree reduces
by 1).
below is the C++ implementation of above approach:
Red-Black Tree Deletion Code
#include <iostream>
#include <queue>
usingnamespacestd;
  
enumCOLOR { RED, BLACK };
  
classNode {
public:
  intval;
  COLOR color;
  Node *left, *right, *parent;
  
  Node(intval) : val(val) {
    parent = left = right = NULL;
    color = RED;
  }
  Node *uncle() {
    if(parent == NULL or parent->parent == NULL)
      returnNULL;
  
    if(parent->isOnLeft())
      returnparent->parent->right;
    else
      returnparent->parent->left;
  }
  boolisOnLeft() { returnthis== parent->left; }
  Node *sibling() {
    if(parent == NULL)
      returnNULL;
  
    if(isOnLeft())
      returnparent->right;
  
    returnparent->left;
  }
  voidmoveDown(Node *nParent) {
    if(parent != NULL) {
      if(isOnLeft()) {
        parent->left = nParent;
      } else{
        parent->right = nParent;
      }
    }
    nParent->parent = parent;
    parent = nParent;
  }
  
  boolhasRedChild() {
    return(left != NULL and left->color == RED) or
           (right != NULL and right->color == RED);
  }
};
  
classRBTree {
  Node *root;
  voidleftRotate(Node *x) {
    Node *nParent = x->right;
    if(x == root)
      root = nParent;
  
    x->moveDown(nParent);
    x->right = nParent->left;

    if(nParent->left != NULL)
      nParent->left->parent = x;
    nParent->left = x;
  }
  
  voidrightRotate(Node *x) {
    Node *nParent = x->left;
    if(x == root)
      root = nParent;
  
    x->moveDown(nParent);
    x->left = nParent->right;
    if(nParent->right != NULL)
      nParent->right->parent = x;
    nParent->right = x;
  }
  
  voidswapColors(Node *x1, Node *x2) {
    COLOR temp;
    temp = x1->color;
    x1->color = x2->color;
    x2->color = temp;
  }
  
  voidswapValues(Node *u, Node *v) {
    inttemp;
    temp = u->val;
    u->val = v->val;
    v->val = temp;
  }
  voidfixRedRed(Node *x) {
    if(x == root) {
      x->color = BLACK;
      return;
    }
    Node *parent = x->parent, *grandparent = parent->parent,
         *uncle = x->uncle();
  
    if(parent->color != BLACK) {
      if(uncle != NULL && uncle->color == RED) {
        parent->color = BLACK;
        uncle->color = BLACK;
        grandparent->color = RED;
        fixRedRed(grandparent);
      } else{
        if(parent->isOnLeft()) {
          if(x->isOnLeft()) {
            swapColors(parent, grandparent);
          } else{
            leftRotate(parent);
            swapColors(x, grandparent);
          }
          rightRotate(grandparent);
        } else{
          if(x->isOnLeft()) {
            rightRotate(parent);
            swapColors(x, grandparent);
          } else{
            swapColors(parent, grandparent);
          }
          leftRotate(grandparent);
        }
      }
    }
  }
  Node *successor(Node *x) {
    Node *temp = x;
  
    while(temp->left != NULL)
      temp = temp->left;
  
    returntemp;
  }
  Node *BSTreplace(Node *x) {
    if(x->left != NULL and x->right != NULL)
      returnsuccessor(x->right);

    if(x->left == NULL and x->right == NULL)

      returnNULL;
    if(x->left != NULL)
      returnx->left;
    else
      returnx->right;
  }
  voiddeleteNode(Node *v) {
    Node *u = BSTreplace(v);
    booluvBlack = ((u == NULL or u->color == BLACK) and (v->color == BLACK));
    Node *parent = v->parent;
  
    if(u == NULL) {
      if(v == root) {
        root = NULL;
      } else{
        if(uvBlack) {
          fixDoubleBlack(v);
        } else{
          if(v->sibling() != NULL)
            v->sibling()->color = RED;
        }
        if(v->isOnLeft()) {
          parent->left = NULL;
        } else{
          parent->right = NULL;
        }
      }
      deletev;
      return;
    }
  
    if(v->left == NULL or v->right == NULL) {
      if(v == root) {
        v->val = u->val;
        v->left = v->right = NULL;
        deleteu;
      } else{
        if(v->isOnLeft()) {
          parent->left = u;
        } else{
          parent->right = u;
        }
        deletev;
        u->parent = parent;
        if(uvBlack) {
          fixDoubleBlack(u);
        } else{
          u->color = BLACK;
        }
      }
      return;
    }
    swapValues(u, v);
    deleteNode(u);
  }
  
  voidfixDoubleBlack(Node *x) {
    if(x == root)
      return;
  
    Node *sibling = x->sibling(), *parent = x->parent;
    if(sibling == NULL) {
      fixDoubleBlack(parent);
    } else{
      if(sibling->color == RED) {
        parent->color = RED;
        sibling->color = BLACK;
        if(sibling->isOnLeft()) {
          rightRotate(parent);
        } else{
          leftRotate(parent);
        }
        fixDoubleBlack(x);
      } else{
        if(sibling->hasRedChild()) {
          if(sibling->left != NULL and sibling->left->color == RED) {
            if(sibling->isOnLeft()) {
              sibling->left->color = sibling->color;
              sibling->color = parent->color;
              rightRotate(parent);
            } else{
              sibling->left->color = parent->color;
              rightRotate(sibling);
              leftRotate(parent);
            }
          } else{
            if(sibling->isOnLeft()) {
              sibling->right->color = parent->color;
              leftRotate(sibling);
              rightRotate(parent);
            } else{
              sibling->right->color = sibling->color;
              sibling->color = parent->color;
              leftRotate(parent);
            }
          }
          parent->color = BLACK;
        } else{
          sibling->color = RED;
          if(parent->color == BLACK)
            fixDoubleBlack(parent);
          else
            parent->color = BLACK;
        }
      }
    }
  }
  voidlevelOrder(Node *x) {
    if(x == NULL)
      return;
    queue<Node *> q;
    Node *curr;
    q.push(x);
  
    while(!q.empty()) {
      curr = q.front();
      q.pop();
      cout << curr->val << " ";
      if(curr->left != NULL)
        q.push(curr->left);
      if(curr->right != NULL)
        q.push(curr->right);
    }
  }
  voidinorder(Node *x) {
    if(x == NULL)
      return;
    inorder(x->left);
    cout << x->val << " ";
    inorder(x->right);
  }
  
public:
  RBTree() { root = NULL; }
  
  Node *getRoot() { returnroot; }
  Node *search(intn) {
    Node *temp = root;
    while(temp != NULL) {
      if(n < temp->val) {
        if(temp->left == NULL)
          break;
        else
          temp = temp->left;
      } elseif(n == temp->val) {
        break;
      } else{
        if(temp->right == NULL)
          break;
        else
          temp = temp->right;
      }
    }
  
    returntemp;
  }
  voidinsert(intn) {
    Node *newNode = newNode(n);
    if(root == NULL) {
      newNode->color = BLACK;
      root = newNode;
    } else{
      Node *temp = search(n);
  
      if(temp->val == n) {
        // return if value already exists
        return;
      }
      newNode->parent = temp;
  
      if(n < temp->val)
        temp->left = newNode;
      else
        temp->right = newNode;
      fixRedRed(newNode);
    }
  }
  voiddeleteByVal(intn) {
    if(root == NULL)
      return;
  
    Node *v = search(n), *u;
  
    if(v->val != n) {
      cout << "No node found to delete with value:"<< n << endl;
      return;
    }
  
    deleteNode(v);
  }
  voidprintInOrder() {
    cout << "Inorder: "<< endl;
    if(root == NULL)
      cout << "Tree is empty"<< endl;
    else
      inorder(root);
    cout << endl;
  }
  voidprintLevelOrder() {
    cout << "Level order: "<< endl;
    if(root == NULL)
      cout << "Tree is empty"<< endl;
    else
      levelOrder(root);
    cout << endl;
  }
};
  
intmain() {
  RBTree tree;
  
  tree.insert(7);
  tree.insert(3);
  tree.insert(18);
  tree.insert(10);
  tree.insert(22);
  tree.insert(8);
  tree.insert(11);
  tree.insert(26);
  tree.insert(2);
  tree.insert(6);
  tree.insert(13);
  
  tree.printInOrder();
  tree.printLevelOrder();
  
  cout<<endl<<"Deleting 18, 11, 3, 10, 22"<<endl;
  tree.deleteByVal(18);
  tree.deleteByVal(11);
  tree.deleteByVal(3);
  tree.deleteByVal(10);
  tree.deleteByVal(22);
  
  tree.printInOrder();
  tree.printLevelOrder();
  return0;
}
Output:
Inorder: 2 3 6 7 8 10 11 13 18 22 26
Level Order:
10 7 18 3 8 11 22 2 26 13 26
Deleting: 18,11, 3, 10,22
Inorder:
2 6 7 8 13 26
Level Order:
13 7 26 6 8 2

2. Huffman Coding Algorithm- Description and Implementation.

Descripthion
Prefix Codes, means the codes (bit sequences) are assigned in such a way that the code
assigned to one character is not the prefix of code assigned to any other character. This
is how Huffman Coding makes sure that there is no ambiguity when decoding the
generated bitstream.
Let us understand prefix codes with a counter example. Let there be four characters a,
b, c and d, and their corresponding variable length codes be 00, 01, 0 and 1. This
coding leads to ambiguity because code assigned to c is the prefix of codes assigned to
a and b. If the compressed bit stream is 0001, the de-compressed output may be “cccd”
or “ccb” or “acd” or “ab”.
See this for applications of Huffman Coding.
There are mainly two major parts in Huffman Coding
1) Build a Huffman Tree from input characters.
2) Traverse the Huffman Tree and assign codes to characters.
Steps to build Huffman Tree
Input is an array of unique characters along with their frequency of occurrences and
output is Huffman Tree.
1. Create a leaf node for each unique character and build a min heap of all leaf nodes
(Min Heap is used as a priority queue. The value of frequency field is used to compare
two nodes in min heap. Initially, the least frequent character is at root)
2. Extract two nodes with the minimum frequency from the min heap.
3. Create a new internal node with a frequency equal to the sum of the two nodes
frequencies. Make the first extracted node as its left child and the other extracted node
as its right child. Add this node to the min heap.
4. Repeat steps#2 and #3 until the heap contains only one node. The remaining node is
the root node and the tree is complete.

Implementation-
Following is the C++ implementation of Huffman coding. The algorithmcan be
mapped to any programming language as per the requirement.

#include <iostream>
#include <vector>
#include <queue>
#include <string>

usingnamespace std;

classHuffman_Codes
{
struct New_Node
{
char data;
size_t freq;
New_Node* left;
New_Node* right;
New_Node(char data, size_t freq):data(data),
freq(freq),
left(NULL),
right(NULL)
{}
~New_Node()
{
delete left;
delete right;
}
};

struct compare
{
booloperator()(New_Node* l, New_Node* r)
{
return(l->freq > r->freq);
}
};

New_Node* top;

voidprint_Code(New_Node* root, string str)

{
if(root ==NULL)
return;

if(root->data =='$')
{
print_Code(root->left, str +"0");
print_Code(root->right, str +"1");
}

if(root->data !='$')
{
cout << root->data <<" : "<< str <<"\n";
print_Code(root->left, str +"0");
print_Code(root->right, str +"1");
}
}

public:
Huffman_Codes(){};
~Huffman_Codes()
{
delete top;
}
voidGenerate_Huffman_tree(vector<char>& data, vector<size_t>&
freq, size_t size)
{
New_Node* left;
New_Node* right;
priority_queue<New_Node*, vector<New_Node*>, compare >
minHeap;

for(size_t i =0; i < size;++i)

{
minHeap.push(newNew_Node(data[i], freq[i]));
}

while(minHeap.size()!=1)
{
left = minHeap.top();
minHeap.pop();

right = minHeap.top();
minHeap.pop();

top =newNew_Node('$', left->freq + right->freq);

top->left = left;
top->right = right;
minHeap.push(top);
}
print_Code(minHeap.top(),"");
}
};

intmain()
{
int n, f;
char ch;
Huffman_Codes set1;
 vector<char> data;
vector<size_t> freq;
cout<<"Enter the number of elements \n";
cin>>n;
cout<<"Enter the characters \n";
for(int i=0;i<n;i++)
{
cin>>ch;
data.insert(data.end(), ch);
}
cout<<"Enter the frequencies \n";
for(int i=0;i<n;i++)
{
cin>>f;
freq.insert(freq.end(), f);
}

size_t size = data.size();

set1.Generate_Huffman_tree(data, freq, size);

return0;
}
The program is executed using same inputs as that of the example explained above.
This will help in verifying the resultant solution set with actual output.
Output:

3. Application of BFS and DFS algorithm.

Applications of Depth First Search
Depth-first search (DFS) is an algorithm (or technique) for traversing a graph.
Following are the problems that use DFS as a building block.
1) For a weighted graph, DFS traversal of the graph produces the minimum spanning
tree and all pair shortest path tree.
2)Detecting cycle in a graph
A graph has cycle if and only if we see a back edge during DFS. So we can run DFS
for the graph and check for back edges.
3)Path Finding
We can specialize the DFS algorithm to find a path between two given vertices u and
z.
i) Call DFS(G, u) with u as the start vertex.
ii) Use a stack S to keep track of the path between the start vertex and the current
vertex.
iii) As soon as destination vertex z is encountered, return the path as the
contents of the stack
See this for details.
4) Topological Sorting
Topological Sorting is mainly used for scheduling jobs from the given dependencies
among jobs. In computer science, applications of this type arise in instruction
scheduling, ordering of formula cell evaluation when recomputing formula values in
spreadsheets, logic synthesis, determining the order of compilation tasks to perform in
makefiles, data serialization, and resolving symbol dependencies in linkers.
5) To test if a graph is bipartite
We can augment either BFS or DFS when we first discover a new vertex, color it
opposited its parents, and for each other edge, check it doesn’t link two vertices of the
same color. The first vertex in any connected component can be red or black!
See this for details.
6) Finding Strongly Connected Components of a graph A directed graph is called
strongly connected if there is a path from each vertex in the graph to every other
vertex. (See this for DFS based algo for finding Strongly Connected Components)
7) Solving puzzles with only one solution, such as mazes. (DFS can be adapted to
find all solutions to a maze by only including nodes on the current path in the visited
set.)

Applications of Breadth First Traversal

We have earlier discussed Breadth First Traversal Algorithm for Graphs. We have also
discussed Applications of Depth First Traversal. In this article, applications of Breadth
First Search are discussed.
1) Shortest Path and Minimum Spanning Tree for unweighted graph In an
unweighted graph, the shortest path is the path with least number of edges. With
Breadth First, we always reach a vertex from given source using the minimum number
of edges. Also, in case of unweighted graphs, any spanning tree is Minimum Spanning
Tree and we can use either Depth or Breadth first traversal for finding a spanning tree.
2) Peer to Peer Networks. In Peer to Peer Networks like BitTorrent, Breadth First
Search is used to find all neighbor nodes.
3) Crawlers in Search Engines: Crawlers build index using Breadth First. The idea is
to start from source page and follow all links from source and keep doing same. Depth
First Traversal can also be used for crawlers, but the advantage with Breadth First
Traversal is, depth or levels of the built tree can be limited.
4) Social Networking Websites: In social networks, we can find people within a
given distance ‘k’ from a person using Breadth First Search till ‘k’ levels.
5) GPS Navigation systems: Breadth First Search is used to find all neighboring
locations.
6) Broadcasting in Network: In networks, a broadcasted packet follows Breadth First
Search to reach all nodes.
7) In Garbage Collection: Breadth First Search is used in copying garbage collection
using Cheney’s algorithm. Refer this and for details. Breadth First Search is preferred
over Depth First Search because of better locality of reference:
8) Cycle detection in undirected graph: In undirected graphs, either Breadth First
Search or Depth First Search can be used to detect cycle. We can use BFS to detect
cycle in a directed graph also,
9) Ford–Fulkerson algorithm In Ford-Fulkerson algorithm, we can either use
Breadth First or Depth First Traversal to find the maximum flow. Breadth First
Traversal is preferred as it reduces worst case time complexity to O(VE2).
10) To test if a graph is Bipartite We can either use Breadth First or Depth First
Traversal.
11) Path Finding We can either use Breadth First or Depth First Traversal to find if
there is a path between two vertices.
12) Finding all nodes within one connected component: We can either use Breadth
First or Depth First Traversal to find all nodes reachable from a given node.
Many algorithms like Prim’s Minimum Spanning Tree and Dijkstra’s Single Source
Shortest Path use structure similar to Breadth First Search.
There can be many more applications as Breadth First Search is one of the core
algorithms for Graphs.
4. Disconnected Graph definition and example. Find out the BFS
solution of a disconnected graph.
Graphs- Definition
A graph is defined as an ordered pair of a set of vertices and a set of edges.
G = (V, E)
Here, V is the set of vertices and E is the set of edges connecting the vertices. 
Example-
 

 
In this graph,
V={A,B,C,D,E}
E = { AB , AC , BD , CD , DE }
BFS for Disconnected Graph
In previous post, BFS only with a particular vertex is performed i.e. it is assumed that
all vertices are reachable from the starting vertex. But in the case of disconnected
graph or any vertex that is unreachable from all vertex, the previous implementation
will not give the desired output, so in this post, a modification is done in BFS.

All vertices are reachable. So, for above graph simple BFS will work.

As in above graph a vertex 1 is unreachable from all vertex, so simple BFS wouldn’t
work for it.
// C++ implementation of modified BFS

#include<bits/stdc++.h>

using namespace std;

void addEdge(vector<int> adj[], int u, int v)

adj[u].push_back(v);

void BFSUtil(int u, vector<int> adj[],

vector<bool>&visited)

list<int> q;

visited[u] = true;

q.push_back(u);

while(!q.empty())

u = q.front();

cout << u << " ";

q.pop_front();

for (int i = 0; i != adj[u].size(); ++i)

if (!visited[adj[u][i]])

visited[adj[u][i]] = true;
 q.push_back(adj[u][i]);

void BFS(vector<int> adj[], int V)

vector<bool> visited(V, false);

for (int u=0; u<V; u++)

if (visited[u] == false)

BFSUtil(u, adj, visited);

int main()

int V = 5;

vector<int> adj[V];

addEdge(adj, 0, 4);

addEdge(adj, 1, 2);

addEdge(adj, 1, 3);

addEdge(adj, 1, 4);

addEdge(adj, 2, 3);

addEdge(adj, 3, 4);
 BFS(adj, V);

return 0;
}

Output:
04123

5. Elaborate ‘Graph Coloring’. Describe the process of detecting

cycle in a directed graph using colors.
Elaborate Graph Coloring
Graph coloring problem is to assign colors to certain elements of a graph subject to
certain constraints.
Vertex coloring is the most common graph coloring problem. The problem is, given
m colors, find a way of coloring the vertices of a graph such that no two adjacent
vertices are colored using same color. The other graph coloring problems like Edge
Coloring (No vertex is incident to two edges of same color) and Face
Coloring (Geographical Map Coloring) can be transformed into vertex coloring.
Detect Cycle in a directed graph using colors
Given a directed graph, check whether the graph contains a cycle or not. Your
function should return true if the given graph contains at least one cycle, else return
false.
Example:
Input: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Output: Yes
Explanation:
This diagram clearly shows a cycle 0 -> 2 -> 0.
Input:n = 4, e = 3
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 3
Output:No
Explanation:

This diagram clearly shows no cycle.

Recommended: Please try your approach on {IDE} first, before moving on to the
solution.
Solution

Approach: Depth First Traversal can be used to detect cycle in a Graph. DFS for a
connected graph produces a tree. There is a cycle in a graph only if there is a back
edge present in the graph. A back edge is an edge that is from a node to itself
(selfloop) or one of its ancestor in the tree produced by DFS. In the following graph,
there are 3 back edges, marked with cross sign. It can be observed that these 3 back
edges indicate 3 cycles present in the graph.
For a disconnected graph, we get the DFS forest as output. To detect cycle, we can
check for cycle in individual trees by checking back edges.In the previous post, we
have discussed a solution that stores visited vertices in a separate array which stores
vertices of the current recursion call stack.
In this post, a different solution is discussed. The solution is from CLRS book. The
idea is to do DFS of a given graph and while doing traversal, assign one of the below
three colours to every vertex.
WHITE : Vertex is not processed yet. Initially, all vertices are WHITE.
GRAY: Vertex is being processed (DFS for this vertex has started, but not finished
which means that all descendants (in DFS tree) of this vertex are not processed yet (or
this vertex is in the function call stack)
BLACK : Vertex and all its descendants are processed. While doing DFS, if an edge
is encountered from current vertex to a GRAY vertex, then this edge is back edge and
hence there is a cycle.

Algorithm:
1. Create a recursive function that takes the edge and color array (this can be also
kept as a global variable)
2. Mark the current node as GREY.
3. Traverse all the adjacent nodes and if any node is marked GREY then return
true as a loop is bound to exist.
4. If any adjacent vertex is WHITE then call the recursive function for that node.
If the function returns true. Return true.
5. If no adjacent node is grey or has not returned true then mark the current Node
as BLACK and return false.