WAP to Insert Node in Circuler Linked List In Sorted Order

#include
#include

/* structure for a node */
struct node
{
int data;
struct node *next;
};

/* function to insert a new_node in a list in sorted way.
Note that this function expects a pointer to head_ref
as this can modify the head of the input linked list */
void sortedInsert(struct node** head_ref, struct node* new_node)
{
struct node* current = *head_ref;

if (current == NULL)
{
new_node->next = new_node;
*head_ref = new_node;
}

/* Special case for the head end */
else if (current->data >= new_node->data)
{
/* If value is smaller than head's value then
we need to change next of last node */
while(current->next != *head_ref)
current = current->next;
current->next = new_node;
new_node->next = *head_ref;
*head_ref = new_node;
}
else
{
/* Locate the node before the point of insertion */
while (current->next!= *head_ref && current->next->data < new_node->data)
current = current->next;

new_node->next = current->next;
current->next = new_node;
}
}

/* Function to print nodes in a given linked list */
void printList(struct node *start);

int main()
{
int arr[] = {12, 56, 2, 11, 1, 90};
int list_size, i;

/* start with empty linked list */
struct node *start = NULL;
struct node *temp;

/* Create linked list from the array arr[].
Created linked list will be 1->11->2->56->12 */
for(i = 0; i< 6; i++)
{
temp = (struct node *)malloc(sizeof(struct node));
temp->data = arr[i];
sortedInsert(&start, temp);
}

printList(start);
getchar();
return 0;
}

/* Function to print nodes in a given linked list */
void printList(struct node *start)
{
struct node *temp;

if(start != NULL)
{
temp = start;
printf("\n");
do {
printf("%d ", temp->data);
temp = temp->next;
} while(temp != start);
}
}



https://ideone.com/NdBum

Given a linked list, remove all the nodes which have a greater value on right side. Eg the list 12->15->10->11->5->6->2->3

Given a linked list, remove all the nodes which have a greater value on right side.

Eg the list 12->15->10->11->5->6->2->3

should be changed to 15->11->6->3


#include
#include

struct node
{
int data;
struct node *next;
};

void push(struct node **head_ref, int new_data)
{
struct node *new_node=(struct node *)malloc(sizeof(struct node));
new_node->data=new_data;
new_node->next=*head_ref;
*head_ref=new_node;
}

void reverseList(struct node **headref)
{
struct node *current=*headref;
struct node *prev=NULL;
struct node *next;
while(current!=NULL)
{
next=current->next;
current->next=prev;
prev=current;
current=next;
}
*headref= prev;
}

void printList(struct node *head)
{
while(head!=NULL)
{
printf("%d ",head->data);
head=head->next;
}
printf("\n");
}

void delLesserNodes(struct node *head)
{
struct node *current=head;
struct node *maxnode=head;
struct node *temp;
while(current!=NULL&¤t->next!=NULL)
{
if(current->next->datadata)
{
temp=current->next;
current->next=temp->next;
free(temp);
}
else
maxnode=current=current->next;

}
}

int main()
{
struct node *head=NULL;

push(&head,3);
push(&head,2);
push(&head,6);
push(&head,5);
push(&head,11);
push(&head,10);
push(&head,15);
push(&head,12);

reverseList(&head);
delLesserNodes(head);
reverseList(&head);

printList(head);
getchar();
return 0;
}

WAP for KMP String Search

e
#include
/* KMP algorithm for string Matching */
main()
{
char *p="This is my first post to this group";
char *T="to this group this is my post";
int len = strlen(p);
int len1 = strlen(T);
printf("len:%d len1:%d\n",len,len1);
int k = 0,i;
int array[40]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
/* Pre processing which takes O(m)*/
for(i = 2; i< len; i++)
{
while(k > 0 && p[k+1] != p[i])
{
k = array[k];
}

if(p[k+1] == p[i])
{
k++;
array[i] = k;
}
}

/* Matching which takes O(n) */
k = 1;
for(i = 0; i< len1; i++)
{

while(k > 0 && p[k+1] != T[i])
{
k = array[k];
}

if(p[k+1] == T[i])
{
k++;
printf("%d %d %c\n",k,i,p[k]);
if(k == 10)
{
printf("String Matched\n");
}
}
}
}

write a function to reverse every alternate k nodes in linked list

Given a linked list, write a function to reverse every alternate k nodes (where k is an input to the function) in an efficient way. Give the complexity of your algorithm.
Example:
Inputs: 1->2->3->4->5->6->7->8->9->NULL and k = 3
Output: 1->2->3->6->5->4->8->7->9->NULL.



#include
#include

/* Link list node */
struct node
{
int data;
struct node* next;
};

/* Reverses alternate k nodes and
returns the pointer to the new head node */
struct node *reverse (struct node *head, int k)
{
struct node* current = head;
struct node* next;
struct node* prev = NULL;
int count = 0;

/*reverse first k nodes of the linked list */
while (current != NULL && count < k)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
count++;
}
if(head != NULL)
head->next = current;

/* Do not reverse next k nodes */
count = 0;
while(count < k-1 && current != NULL )
{
current = current->next;
count++;
}

/* next is now a pointer to (k+1)th node
Recursively call for the list starting from current.
And make rest of the list as next of first node */
if(current != NULL)
{ current->next = reverse(current->next, k); }

/* prev is new head of the input list */
return prev;
}

/* UTILITY FUNCTIONS */
/* Function to push a node */
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */
new_node->next = (*head_ref);

/* move the head to point to the new node */
(*head_ref) = new_node;
}

/* Function to print linked list */
void printList(struct node *node)
{
int count = 0;
while(node != NULL)
{
printf("%d ", node->data);
node = node->next;
count++;
}
}

/* Drier program to test above function*/
int main(void)
{
/* Start with the empty list */
struct node* head = NULL;

// create a list 1->2->3->4->5...... ->20
for(int i = 20; i > 0; i--)
push(&head, i);

printf("\n Given linked list \n");
printList(head);
head = reverse(head, 3);

printf("\n Reversed Linked list \n");
printList(head);

getchar();
return(0);
}

Output:
Given linked list
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Reversed Linked list
3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19

Given a telephone number print or produce all the possible telephone words or combinations of letters that can represent the given telephone number

import java.util.*;

class PhoneMmemonics
{

/**
* Mapping between a digit and the characters it represents
*/
private static Map> numberToCharacters = new
HashMap>();

static {
numberToCharacters.put('0',new ArrayList(Arrays.asList('0')));
numberToCharacters.put('1',new ArrayList(Arrays.asList('1')));
numberToCharacters.put('2',new ArrayList(Arrays.asList('A','B','C')));
numberToCharacters.put('3',new ArrayList(Arrays.asList('D','E','F')));
numberToCharacters.put('4',new ArrayList(Arrays.asList('G','H','I')));
numberToCharacters.put('5',new ArrayList(Arrays.asList('J','K','L')));
numberToCharacters.put('6',new ArrayList(Arrays.asList('M','N','O')));
numberToCharacters.put('7',new ArrayList(Arrays.asList('P','Q','R')));
numberToCharacters.put('8',new ArrayList(Arrays.asList('T','U','V')));
numberToCharacters.put('9',new ArrayList(Arrays.asList('W','X','Y','Z')));
}

/**
* Generates a list of all the mmemonics that can exists for the number
* @param phoneNumber
* @return
*/
public static List getMmemonics(int phoneNumber) {

// prepare results
StringBuilder stringBuffer = new StringBuilder();
List results = new ArrayList();

// generate all the mmenonics
generateMmemonics(Integer.toString(phoneNumber), stringBuffer, results);

// return results
return results;
}

/**
* Recursive helper method to generate all mmemonics
*
* @param partialPhoneNumber Numbers in the phone number that haven't converted to characters yet
* @param partialMmemonic The partial word that we have come up with so far
* @param results total list of all results of complete mmemonics
*/
private static void generateMmemonics(String partialPhoneNumber, StringBuilder partialMmemonic, List results) {

// are we there yet?
if (partialPhoneNumber.length() == 0) {

// base case: so add the mmemonic is complete
results.add(partialMmemonic.toString());
return;
}

// prepare variables for recursion
int currentPartialLength = partialMmemonic.length();
char firstNumber = partialPhoneNumber.charAt(0);
String remainingNumbers = partialPhoneNumber.substring(1);

// for each character that the single number represents
for(Character singleCharacter : numberToCharacters.get(firstNumber)) {

// append single character to our partial mmemonic so far
// and recurse down with the remaining characters
partialMmemonic.setLength(currentPartialLength);
generateMmemonics(remainingNumbers, partialMmemonic.append(singleCharacter), results);
}
}

public static void main(String a[])
{
List results = new ArrayList();
results=getMmemonics(23);

Iterator it=results.iterator();
while(it.hasNext())
{

System.out.println(it.next());
}

}

}


General Formula is Product of (nCr) where n ={0...9} & r={ 1,2,3};
if n=23

AD
AE
AF
BD
BE
BF
CD
CE
CF

3c1 * 3c1=9

for n=234

ADG
ADH
ADI
AEG
AEH
AEI
AFG
AFH
AFI
BDG
BDH
BDI
BEG
BEH
BEI
BFG
BFH
BFI
CDG
CDH
CDI
CEG
CEH
CEI
CFG
CFH
CFI

3c1*3c1*3c1=27

and so on


Another Method

class Program
{
static void Main(string[] args)
{
int[] phoneNumber = new int[]{2,3,4};
List telephoneWords = GetTelephoneWords(phoneNumber, 0);
}

//get all the combinations / telephone words for a given telephone number
static List GetTelephoneWords(int[] numbers, int index)
{
List newWords = new List();
if (index == numbers.Length - 1)
{
newWords.AddRange(GetLetters(numbers[index]));
}
else
{
List wordsSoFar = GetTelephoneWords(numbers, index + 1);
string[] letters = GetLetters(numbers[index]);

foreach (string letter in letters)
{
foreach (string oldWord in wordsSoFar)
{
newWords.Add(letter + oldWord);
}
}
}
return newWords;
}

//gets the letters corresponding to a telephone digit
static string[] GetLetters(int i)
{
switch (i)
{
case 1: return new string[]{"1"};
case 2: return new string[] { "a", "b", "c" };
case 3: return new string[] { "d", "e", "f" };
case 4: return new string[] { "g", "h", "i" };
case 5: return new string[] { "j", "k", "l" };
case 6: return new string[] { "m", "n", "o" };
case 7: return new string[] { "p", "q", "r", "s" };
case 8: return new string[] { "t", "u", "v" };
case 9: return new string[] { "w", "x", "y", "z" };
case 0: return new string[]{"0"};
default: return new string[] { };
}
}
}

WAP to Find The Largest Prime Factor Number

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?


The solution to this problem is simple. But the main problem here is to construct a rock solid method that returns whether a given number is prime or not. A prime number is a number which divisible by itself and 1 only. Example of prime numbers are 2,3,11,4999. The following is the ruby code to find whether or not a number is prime or not. You may see that I have used a square root of the number as the upper bound, the simple reason being, there cannot be a number greater than the square root of that number being prime (you can get it if you think deep)

def is_prime(n)
return false if n <= 1
2.upto(Math.sqrt(n).to_i) do |x|
return false if n%x == 0
end
true
end

Now that we have written a method that returns whether or not a number is prime, the rest of the problem is fairly simple. Again, we have to use the square root property. It is enough if we run the prime number validation from the square root of the number. We will have to traverse all the way to 2 for this. The first occurring prime factor is ofcourse the solution to our problem.

Math.sqrt(600851475143).to_i.downto(2) do |n|
if is_prime(n) && 600851475143%n ==0
puts "Maximum prime factor for this number is #{n}"
break
end
end

WAP for Find Prime Factor Number (Prime Factors Only)

#include

double sqroot(const double s)
{

double xn = s / 2.0;
double lastX = 0.0;

// Looping this way ensures we perform only as many calculations as necessary.
// Can be replaced with a static for loop if you really want to.
while(xn != lastX)
{
lastX = xn;
xn = (xn + s/xn) / 2.0;
}
return xn;
}

int main()
{
int n=100,i;
int upper_bound=(int)sqroot(n);
for(i=2;i<=upper_bound;i++)
{
if(n%i==0)
{
printf("%d,",i);
n=n/i;
i--;
if(n==1)
break;
}
}

}

Time Complexity O(sqrt(n))
Space Complexity O(1)
Run Here https://ideone.com/ot5Y3

More Info http://mathworld.wolfram.com/PrimeFactor.html

WAP for Find One Elements Which Occurs Only Ones Except it All Occurs Thrice

Question: You are given an array that contains integers. The integers content is such that every integer occurs 3 times in that array leaving one integer that appears only once.

Fastest way to find that single integer
eg:
Input: [2,1,4,5,1,4,2,2,4,1]
Answer: 5

Answer: I couldn't solve this question myself at first go in O(n) with O(1) space. Searched for it and found an excellent answer here. Sharing the answer and explanation for that:

int main()
{
int B[] = {1,1,1,3,3,3,20,4,4,4};
int ones = 0 ;
int twos = 0 ;
int not_threes, x ;

for( i=0; i< 10; i++ )
{
x = B[i];
twos |= ones & x ;
ones ^= x ;
not_threes = ~(ones & twos) ;
ones &= not_threes ;
twos &= not_threes ;
}

printf("\n unique element = %d \n", ones );
return 0;
}



Explanation:
The code works in similar line with the question of "finding the element which appears once in an array - containing other elements each appearing twice". Solution is to XOR all the elements and you get the answer.

Basically, it makes use of the fact that x^x = 0. So all paired elements get XOR'd and vanish leaving the lonely element.
Since XOR operation is associative, commutative.. it does not matter in what fashion elements appear in array, we still get the answer.

Now, in the current question - if we apply the above idea, it will not work because - we got to have every unique element appearing even number of times. So instead of getting the answer, we will end up getting XOR of all unique elements which is not what we want.

To rectify this mistake, the code makes use of 2 variables.
ones - At any point of time, this variable holds XOR of all the elements which have
appeared "only" once.
twos - At any point of time, this variable holds XOR of all the elements which have
appeared "only" twice.

So if at any point time,
1. A new number appears - It gets XOR'd to the variable "ones".
2. A number gets repeated(appears twice) - It is removed from "ones" and XOR'd to the
variable "twice".
3. A number appears for the third time - It gets removed from both "ones" and "twice".

The final answer we want is the value present in "ones" - coz, it holds the unique element.

So if we explain how steps 1 to 3 happens in the code, we are done.
Before explaining above 3 steps, lets look at last three lines of the code,

not_threes = ~(ones & twos)
ones & = not_threes
twos & = not_threes

All it does is, common 1's between "ones" and "twos" are converted to zero.

For simplicity, in all the below explanations - consider we have got only 4 elements in the array (one unique element and 3 repeated elements - in any order).

Explanation for step 1
------------------------
Lets say a new element(x) appears.
CURRENT SITUATION - Both variables - "ones" and "twos" has not recorded "x".

Observe the statement "twos| = ones & x".
Since bit representation of "x" is not present in "ones", AND condition yields nothing. So "twos" does not get bit representation of "x".
But, in next step "ones ^= x" - "ones" ends up adding bits of "x". Thus new element gets recorded in "ones" but not in "twos".

The last 3 lines of code as explained already, converts common 1's b/w "ones" and "twos" to zeros.
Since as of now, only "ones" has "x" and not "twos" - last 3 lines does nothing.

Explanation for step 2.
------------------------
Lets say an element(x) appears twice.
CURRENT SITUATION - "ones" has recorded "x" but not "twos".

Now due to the statement, "twos| = ones & x" - "twos" ends up getting bits of x.
But due to the statement, "ones ^ = x" - "ones" removes "x" from its binary representation.

Again, last 3 lines of code does nothing.
So ultimately, "twos" ends up getting bits of "x" and "ones" ends up losing bits of "x".

Explanation for step 3.
-------------------------
Lets say an element(x) appears for the third time.
CURRENT SITUATION - "ones" does not have bit representation of "x" but "twos" has.

Though "ones & x" does not yield nothing .. "twos" by itself has bit representation of "x". So after this statement, "two" has bit representation of "x".
Due to "ones^=x", after this step, "one" also ends up getting bit representation of "x".

Now last 3 lines of code removes common 1's of "ones" and "twos" - which is the bit representation of "x".
Thus both "ones" and "twos" ends up losing bit representation of "x".

1st example
------------
2, 2, 2, 4

After first iteration,
ones = 2, twos = 0
After second iteration,
ones = 0, twos = 2
After third iteration,
ones = 0, twos = 0
After fourth iteration,
ones = 4, twos = 0

2nd example
------------
4, 2, 2, 2

After first iteration,
ones = 4, twos = 0
After second iteration,
ones = 6, twos = 0
After third iteration,
ones = 4, twos = 2
After fourth iteration,
ones = 4, twos = 0

Explanation becomes much more complicated when there are more elements in the array in mixed up fashion. But again due to associativity of XOR operation - We actually end up getting answer.

Implementing a Least-Recently-Used(LRU) Cache

Quickly i want to tell you about my approach , what DS we can use to implement in most efficient manner .

we can use Combination of Queue + HashMap  Data Structure OR

                                     LinkedList + HaspMap

Here algorithmic with explanation of DS

Why combination of two Data Structure ?  Let me tell you how LRU works : LRU caches have a maximum number of data items that they will hold and these items are usually arranged in a some data structure (list or queue). When an item is added to the cache, and every time it is accessed after that, it is automatically moved to the head of the list. If the cache is full and a slot is required for a new item, the cache makes room by discarding the entry at the tail of the list - the least-recently used item.  So we need to remove the Eldest entry from list/queue in the same in which inserted both queue and list provide this facility to , we need insert element at the  head of queue/list and remove the element from tail or queue/ list , since queue itself require list to be implement , we can directly use LinkedList . we can do insert and remove in O(1) .

Now , Before Inserting entry in list or queue , we need to check if that entry alraedy exist in Cache or not  , how we will do that , we need some DS again fro the same , HashMap is used for the same , that gurentte , get and set in O(1) .

As you asked in java , Java Provide the DS called  LinkedHashMap that has both feature.

An Important feature of LinkedHashMap is that it provides the methodremoveEldestEntry (Map.Entry e) that remove the eldest entry from the cache when it becmoe full and a new entry need to be inserted .

In this section, you will learn about th least-recently- used (LRU) cache in Java. LRU Cache helps you how to use the buffer and how to limit or fixed the size of buffer and how to manage storing and retrieving process of the buffer which size is limited.

In this section, you can create a LRU(least-recently-used) Cache and manage it efficiently. Here the given program takes a in numeric input to fix the size of the LRU Cache. If your entry exceeds the size of the LRU Cache the the eldest element with key is removed. LRU Cache is implemented through 

theLinkedHashMap class. LinkedHashMap holds values with unique key. You you store values with a duplicate key then the LinkedHashMap replace the old value of that key with the new value of the key.

Code Description:

This program shows the object keys and values by using the LRU cache. Many methods and APIs which have been used in the following program are explained as follows:

LinkedHashMap:This is the class of the java.util.*; package. This class is also used for the implementing 
the doubly linked list which tracks either insertion or access order. The put() method is used for the insertion process to the LinkedHashMap with the value and the unique key regarding the value.

put(Object key, Object value):This method has been used to add a value with it's unique key in the LRU Cache. This method of the LinkedHashMap class takes two argument in which first is the key and another is the value for the specified key.

Map.Entry:This interface returns the view of map of collection . The Map.Entry objects are valid only to the duration of the iteration. This is the nested class of the Map class from the java.util.*; package.

e.getKey():Above method of the Map.Entry class which returns the key corresponding to the value. Here 'e' is the instance of the Map.Entry class.

e.getValue():Above written is also a method of the Map.Entry class which returns the value corresponding to the key of the index of the LRU Cache. 

Here is the code of program:

Source :http://www.roseindia.net/java/example/java/util/LRUCacheExample.shtml

Breadth First Search(BFS) and Depth First Search(DFS) Traversal

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

 class Node
{
        public char label;
        public boolean visited=false;
        public Node(char l)
        {
            this.label=l;
        }
}


class Graph
{
       public Node rootNode;
       public ArrayList nodes=new ArrayList();
       public int[][] adjMatrix;//Edges will be represented as adjacency Matrix
       int size;
       public void setRootNode(Node n)
       {
           this.rootNode=n;
       }
      
       public Node getRootNode()
       {
           return this.rootNode;
       }
      
       public void addNode(Node n)
       {
           nodes.add(n);
       }
      
       //This method will be called to make connect two nodes
       public void connectNode(Node start,Node end)
       {
           if(adjMatrix==null)
           {
               size=nodes.size();
               adjMatrix=new int[size][size];
           }
  
           int startIndex=nodes.indexOf(start);
           int endIndex=nodes.indexOf(end);
           adjMatrix[startIndex][endIndex]=1;
           adjMatrix[endIndex][startIndex]=1;
       }
      
       private Node getUnvisitedChildNode(Node n)
       {
          
           int index=nodes.indexOf(n);
           int j=0;
           while(j<size)
           {
               if(adjMatrix[index][j]==1 && ((Node)nodes.get(j)).visited==false)
               {
                   return (Node)nodes.get(j);
               }
               j++;
           }
           return null;
       }
      
       //BFS traversal of a tree is performed by the bfs() function
       public void bfs()
       {
          
           //BFS uses Queue data structure
           Queue q=new LinkedList();
           q.add(this.rootNode);
           printNode(this.rootNode);
           rootNode.visited=true;
           while(!q.isEmpty())
           {
               Node n=(Node)q.remove();
               Node child=null;
               while((child=getUnvisitedChildNode(n))!=null)
               {
                   child.visited=true;
                   printNode(child);
                   q.add(child);
               }
           }
           //Clear visited property of nodes
           clearNodes();
       }
      
       //DFS traversal of a tree is performed by the dfs() function
       public void dfs()
       {
           //DFS uses Stack data structure
           Stack s=new Stack();
           s.push(this.rootNode);
           rootNode.visited=true;
           printNode(rootNode);
           while(!s.isEmpty())
           {
              Node n=(Node)s.peek();
               Node child=getUnvisitedChildNode(n);
               if(child!=null)
               {
                  child.visited=true;
                  printNode(child);
                  s.push(child);
              }
              else
              {
                 s.pop();
              }
          }
         //Clear visited property of nodes
          clearNodes();
      }
     
     
      //Utility methods for clearing visited property of node
      private void clearNodes()
      {
          int i=0;
         while(i<size)
          {
             Node n=(Node)nodes.get(i);
              n.visited=false;
              i++;
          }
      }
     
      //Utility methods for printing the node's label
     private void printNode(Node n)
      {
          System.out.print(n.label+" ");
      }
 
    
     
     
 
  }

public class Main {
  
       /**
        * @param args
        */
       public static void main(String[] args)
       {
          
           //Lets create nodes as given as an example in the article
           Node nA=new Node('A');
           Node nB=new Node('B');
           Node nC=new Node('C');
           Node nD=new Node('D');
           Node nE=new Node('E');
           Node nF=new Node('F');
  
           //Create the graph, add nodes, create edges between nodes
           Graph g=new Graph();
           g.addNode(nA);
           g.addNode(nB);
           g.addNode(nC);
           g.addNode(nD);
           g.addNode(nE);
           g.addNode(nF);
           g.setRootNode(nA);
          
           g.connectNode(nA,nB);
           g.connectNode(nA,nC);
           g.connectNode(nA,nD);
          
           g.connectNode(nB,nE);
           g.connectNode(nB,nF);
           g.connectNode(nC,nF);
          
          
           //Perform the traversal of the graph
           System.out.println("DFS Traversal of a tree is ------------->");
           g.dfs();
          
           System.out.println("\nBFS Traversal of a tree is ------------->");
           g.bfs();
          
          
          
          
       }
  
 }

   




Time Complexity O(M+N)m is no od edges & n no of nodes in case of connected graph
is will be O(M).
Space Complexity Depends on Implementation if Adjency matrix is Used then it will be O(MN)
else if adjency list is used then it will be equals to number of adjecent nodes of each node. it will O(M+N)

Application of BFS:
1.Finding Connected Components in Graph.
2.Check Graph is Bipartite or Not.
3.Finding interesting web pages (expanding from 
links). Breadth-first works very nicely and quickly 
finds pages with high PageRank R(p). PageRank 
is the scoring measure used by Google.
k is an index over all pages that link to page p; 
C(k) is the total number of links out of k;
R(k) is the PageRank for page k;
T is the total number of web pages on the internet;
d is a number 0 < d < 1.

Application of DFS
1.2-Edge Connectivity in Graph.
2. 2-node connectivity in graph.
3. Check Grap0h is planer or not.
4. solving Puzzles like mouse in the maze