Sunday, October 24, 2010

Design Pattern-2

As it was not possible to cover all the pattern in the previous post. In this post I am going to summarize the other design patterns.
Structural Patterns
Adapter: This pattern is called Wrapper pattern as well. Using this pattern, one class is made compatible with another class. For example, interface X defines 2 methods get and put. Class LegacyClass has methods implementing the required functionality but as LegacyClass can not implement newly defined interface X. So there is a need to wrap LegacyClass with Interface. Adapter pattern will provide the solution to break the ice.
Bridge: This pattern is to provide encapsulation, inheritance and abstraction to the code. In this pattern one interface is given whose implementation can be provided at lower class hierarchy keeping it hidden from the client.
Composite: Composition of no of objects to form an object. This pattern suggests to use numerous objects to create one object.
Decorator: The decorator pattern can be used to make it possible to extend (decorate) the functionality of a certain object at runtime, independently of other instances of the same class, provided some groundwork is done at design time. This is achieved by designing a new decorator class that wraps the original class.
Facade: Provide one unified interface to a set of interfaces. This unified interface works at higher level and it makes it easy to use all the interfaces at once.
Flyweight: A flyweight is an object that minimizes memory use by sharing as much data as possible with other similar objects; it is a way to use objects in large numbers when a simple repeated representation would use an unacceptable amount of memory.
Private Class Data: This pattern primarily deals with encapsulation to hide the data.
Proxy: A proxy, in its most general form, is a class functioning as an interface to something else. The proxy could interface to anything: a network connection, a large object in memory, a file, or some other resource that is expensive or impossible to duplicate.

Behavioral patterns
Chain of responsibility pattern: This pattern is a source of command object and series of processing objects. Each processing object contains a set of logic that describes the types of command objects that it can handle, and how to pass off those that it cannot handle to the next processing object in the chain. A mechanism also exists for adding new processing objects to the end of this chain.
Command pattern: In this pattern object stores the information to invoke the method at later point of time. The information stored is method’s name. parameters and object to which method belongs to. There are 3 components of the pattern:
  • Client: Instantiate a command object and provide the information required to call the method at later point of time.
  • Invoker: Class which decides when to call the method.
  • Receiver: Object having method.
Interpreter pattern: Rules to identify the sentence in language. This pattern is generally used when someone needs to implement own parser.
Iterator pattern: There are aggregated data and there is need to access the data sequentially. So with exposing the internal DS, the same problem is solved by iterator patterns. Java collection API uses iterator pattern.
Mediator pattern: It is very similar facade patterns, where unified interface is exposed by extending numerous interfaces in the subsystem. This pattern is used in these circumstances.
  • Partition a system into pieces or small objects.
  • Centralize control to manipulate participating objects(a.k.a colleagues)
  • Clarify the complex relationship by providing a board committee.
  • Limit subclasses.
  • Improve objects re-usabilities.
  • Simplify object protocols.
  • The relationship between the control class and other participating classes is multidirectional.
Memento pattern: This pattern provide the ability to roll back. Here you will keep 2 states of an object one that is original i.e. anything before changes whereas other object will have latest copy with updates. This pattern is utilized in database updates.
Null Object pattern: Pattern just portrait the behavior of nothing.
Observer pattern: In this pattern a object keeps the list of its dependent, called observer. Whenever changes happened in the object its observer are notified by calling some methods. In general this pattern is used in event handling.
Weak reference pattern: A WeakReferencePattern is a structural pattern used when decoupling of an observer (a view) from an observable (a container) is necessary. A WeakReferencePattern encapsulates a reference to an object. Acquiring the reference is done through a message to the WeakReference (or WeakPointer) object. If the referenced object still exists, a real reference to it is returned. This reference is of course a temporary one.
State pattern: As the state of the object changes behavior is changed. Behavior is changes with if and else statements.

Strategy pattern: The strategy pattern is intended to provide a means to define a family of algorithms, encapsulate each one as an object, and make them interchangeable. The strategy pattern lets the algorithms vary independently from clients that use them. It is useful in the following situations
  • Encapsulate various algorithms to do more or less the same thing.
  • Need one of several algorithms dynamically.
  • The algorithms are exchangeable and vary independently
  • Configure a class with one of many related classes (behaviors).
  • Avoid exposing complex and algorithm-specific structures.
  • Data is transparent to the clients.
  • Reduce multiple conditional statements.
  • Provide an alternative to subclassing.
Specification pattern: In this pattern business logic can be recombined by chaining the business logic together using boolean logic.
Template method pattern: Two different components have significant similarities, but demonstrate no reuse of common interface or implementation. If a change common to both components becomes necessary, duplicate effort must be expended. Provide an abstract definition for a method or a class and redefine its behavior later or on the fly without changing its structure.
Visitor pattern: Define a new operation to deal with the classes of the elements without changing their structures. These are used in the following circumstance:
  • Add operations on a bunch of classes which have different interfaces.
  • Traverse the object structure to gather related operations
  • Easy to add new operations.
  • Crossing class hierarchies may break encapsulation.
Apart from above described patterns there are lot more patterns few of them are Single-serving visitor pattern, Hierarchical visitor pattern and Scheduled-task pattern. There are lot other than mentioned here so it is quite impossible to cover all of them. Hope this information will help all of us.


Source:

Sunday, October 17, 2010

Design Patterns

A design pattern in architecture and computer science is a formal way of documenting a solution to a design problem in a particular field of expertise.

The elements of this language are entities called patterns. Each pattern describes a problem that occurs over and over again in our environment, and then describes the core of the solution to that problem, in such a way that you can use this solution a million times over, without ever doing it the same way twice [Christopher Alexander]


Overview
Design pattern must explain the cause of the problem and state the reasons which will help to alleviate or tackle the problems. For example a window for a room is different on the basis of different rooms but window has specific utility and characteristics. In this case window pattern should state all the problems and their suitable solutions. Along with cause and solutions it should mention the applicability of the pattern.
Design patterns were inherited in computer science from the outside world. These were introduced to provide the solution template for the recurring problems. In computer science design patterns are described as language-independent strategies for solving common object-oriented design problems. When you make a design, you should know the names of some common solutions.


Why should we use design pattern?
Design patterns can speed up the development process by providing tested, proven development paradigms. Effective software design requires considering issues that may not become visible until later in the implementation. Reusing design patterns helps to prevent subtle issues that can cause major problems and improves code readability for coders and architects familiar with the patterns. Design patterns provide general solutions, documented in a format that doesn't require specifics tied to a particular problem. In addition, patterns allow developers to communicate using well-known, well understood names for software interactions. Common design patterns can be improved over time, making them more robust than ad-hoc designs [Source].
A design pattern is not a finished design that can be transformed directly into code. It is a description or template for how to solve a problem that can be used in many different situations.


Relationship among patterns
It is not possible to build whole software with the use of unique design pattern. We must use multiple design patterns. Along with this there are no strict rule to solve one problem with only one pattern. Several designer can use different patterns to solve same problem.
Usually:

  • Some patterns naturally fit together
  • One pattern may lead to another
  • Some patterns are similar and alternative
  • Patterns are discoverable and documentable
  • Patterns are not methods or framework
  • Patterns give you hint to solve a problem effectively [Source]
List and group of design patterns

Creational Patterns:
  • Abstract Factory – Provide an interface for creating families of related or dependent objects without specifying their concrete classes. This pattern provides the platform for independent and independence to choose own logic. It enhances the plug-ability of the software. 
  • Builder – Builds the whole object in smaller object. It is very similar to start a company. To start a company you to have a software but to build software you need lots of intermediate steps. So starting a company may include following steps. Get an office space, put furniture, hire few people to work, and start working on the product. There may be few intermediately steps but in builder all of these steps will be taken care one after another. There will not be any mix up between them.
  • Factory – In this onus of instantiating the class is with subclasses. Here a interface is provided and based on the requirement subclass is instantiated.
  • Lazy Initialization – As name suggest, don’t instantiate object until it is not needed.
  • Object Pool – In some cases it is quite an expensive process to initialize and destroy objects. To curtail down such expensive work, we create pool of objects and keep doing the task with the same pool again and again, instead of spawning new objects each time. Best example for the same is thread pool and connection pool.
  • Prototype - The prototype pattern is a creational design pattern used in software development when the type of objects to create is determined by a prototypical instance, which is cloned to produce new objects. This pattern is used to:
    Avoid subclasses of an object creator in the client application, like the abstract factory pattern does.
    Avoid the inherent cost of creating a new object in the standard way (e.g., using the 'new' keyword) when it is prohibitively expensive for a given application.
  • Resource Acquisition Is Initialization – This pattern is not very useful in java but for other languages it is similar de-allocation of the memory.
  • Singleton – This is the only pattern I know for a long time. In this pattern only instance of class. Whenever application tried to create a new class it request of creation is routed through one method which returns either already instantiated class or if not instantiated then it will instantiate and return the instance.
In the next section we will continue with the other type of Structural and behavioral design patterns..

Wednesday, October 13, 2010

Interview@X Company Data Structures – Part 2

In first part I could post only first question. My friend told me few more questions asked by interviewer.
Que 2: There are 2 link list given which may merge after some n, m number of nodes. Find if these link lists are merged or not?
Ans: Interviewer is not expecting to find out the node at which these 2 nodes are clubbed together. Question is just to find if they have matched.
If one node is common in 2 link lists then all the node after merged node are common in these 2 lists. In this case even if last node (Reference Pointer) of the lists are equal then both the lists have merged.
Solution: Traverse to the end of the linked list and match the reference of last elements of linked list. If those are equal, it implies both linked list were merged.

Sunday, October 10, 2010

ArrayList V/S Vector

ArrayList and Vector are widely known classes in Java world. Most of the interviewer start their discussion to explore differences between ArrayList and Vector (Sometime interviewer also forget no of differences also has limitations :(), and Just after answering this question candidates are pulled into the world of multithreading. Oh I am not going to talk about multithreading here, I will stick to title here.
Legacy Java code has used vector enormous time. For all general indexing purposes vector classes were used. But with the evolution of Java 5, vector classes lost its ground to ArrayList and Collections framework’s utility class SynchromizedList. Now it is really mandatory to know the similarity and differences between these Vector and ArrayList.

Inheritance and Hierarchy
Both the classes implements List, RandomAccess, Cloneable and Serializable interfaces. Along with that both of them extends AbstractList class.

Structure
In general both the classes have same work. Completion of the work is also quite common between both of them but still they have major differences also.


Constructor
ArrayList has 3 constructors whereas Vector has 4 constructors as shown below:

ArrayList() Vector() Default constructor instantiate an Array, containing 10 elements.
ArrayList(int capacity) Vector(int capacity)
Constructor instantiate an Array, containing Capacity elements.
Vector(int capacity, int loadfactor)

Constructor instantiate an Array containing Capacity elements. When someone adds more element than capacity, it re-instantiate the array. The new Array will have (Loadfactor + 1)*Capacity number of elements.

ArrayList(Collection) Vector(Collection) All the elements of the collection are copied to the array.


ArrayList does have user defined load factor which will impact performance when user is not aware of no of incoming elements. Reassignment of the elements will be more and more time consuming. For ArrayList load factor is 0.5 in case of Vector it is defaulted to 1.

Note: It is good practice to use LinkedList if number of elements are more and you are not doing any search operations on the basis of index.

Multithreading
Major difference is associated with Multithreading. All the method of the vector class are synchronized. When multiple threads are trying to access specific instance of vector class, then the calls will not cause any issue. Vector is a thread safe class but not ArrayList. Hence Vector class is slow performing class whereas array list access is faster.
Note: To use iterator on vector, you might need to synchronize the code.

Patterns
Adding and deletion in both the structures take O(1) time. It may take O(N) time just when array capacity has shoot the maximum size assigned. Indexing based search on both the APIs are similar as both of them use array internally.

Serialization
Array object in the ArrayList is a transient object, so while serializing the ArrayList it is required to serialize the object individually. For this reason ArrayList implements readObject and writeObject methods. In case of vector Array object is not transient. Vector implements only writeObject method.

Iterator
ArrayList has not provided any iterator whereas in vector is quipped with its own iterator/enumeration.

These were the differences I could make out from code and different geek sites. If you are aware of any other difference let me know.

Tuesday, October 5, 2010

Puzzle: 5 Greedy and Super Intelligent Pirates

 

Problem Statement

One group of 5 pirates looted one ship having 1000 gold coins. Each pirate is fearsome, super intelligent and greedy.

Conditions:

1. These pirates have hierarchy based on their age. Pirate, having superior age. has first right to take the decision.

2. Each of the pirate will vote on each decision and decision is accepted if and only if at least 50% people are in favor of the decision otherwise leader(one, who took the decision) of the group will be killed.

Senior most guy of the group took one decision in order to distribute the gold coins and he was not killed? What was his decision?

Solution

As pirates are greedy and intelligent, so they know what is best for them. We have to tackle the puzzle from SMALLER to BIGGER number.

Lets assume if there are only 2 pirates and pirate 4 is senior. Whatever decision pirate 4 will take, pirate 5 has to accept it. So he is at the loosing side. In this situation anyone can buy pirate no 5 in small amount of money.

Now lets assume if there are only 3 pirates and pirate 3 is the senior most guy. Pirate 3 has to convince only one guy and it is highly probable he will go to Pirate 5. As pirate 5 has a danger of not getting anything and pirate 4 will try to make most by killing 3. In this scenario an intelligent pirate 3 will not take risk to convince pirate 4. He will offer one coin to pirate 5 and will win his vote.

Lets assume 4 pirates are there on the ship. In this case pirate 4 will give one coin to pirate two and will not give anything to other 2 pirates. As it is quite evident pirate 4 will not deny 1 coin as he will not receive anything if pirate 4 dies.

Now lets come to actual problem. With the above four discussion it is quite obvious. Senior most guy will offer 1 coin each to 3rd and 5th guy and for other 2 he will offer his consolation.

So solution of this puzzle would be

998 coins will go to senior most person and he will give one to 3rd and one to 5th guy and everyone will be happy forever.

Interview Question: String Permutation

There are lot of question we encounter during an interview but there are few question which repeats in many interviews. But due to our lousy nature, every time we end up begging mercy to change the question. My friend has gone through such painful experience many time. But this time he can not resist himself to find the solution of the question. Though he could not find the solution and ask me to relieve his burden. So I thought of enlighten world with my half cooked knowledge.

Question: Find all the permutation of a string?
Condition A: Find if all characters of the string are unique?

Answer: How should be start writing the code? If you look at the permutation mechanism it has a certain pattern. Lets examine it with different possible combination of string ABC
   1: --- Start with A ---
   2: ABC
   3: ACB
   4: --- Start with B ---
   5: BAC
   6: BCA
   7: --- Start with C ---
   8: CAB
   9: CBA
Ok, it is still less clear can we look for a bigger example. Lets look for ABCD


   1: --- Starting with A---
   2: A BCD
   3: A BDC
   4: A CBD
   5: A CDB
   6: A DBC
   7: A DCB
   8:  
   9: --- Starting with B ---
  10: B ACD
  11: B ADC
  12: B CAD
  13: B CDA
  14: B DAC
  15: B DCA
  16:  
  17: --- Starting with C ---
  18: CABD
  19: CADB
  20: CBAD
  21: CBDA
  22: CDAB
  23: CDBA
  24:  
  25: ----Starting with D---
  26: DABC
  27: DACB
  28: DBAC
  29: DBCA
  30: DCAB
  31: DCBA
Now from above 2 code snippets it is clear puzzle for n can be broken into n-1 elements. If there are 4 elements then add 4th element to permutations of rest 3… Yes, you got the solution. It is a recursive process. Where we need to touch the bottom of the ocean and then return to water surface.

Code:


1: import java.util.ArrayList;

   2: import java.util.LinkedList;
   3: import java.util.List;
   4:  
   5: public class StringPermutations {
   6:  
   7:     List<String> strs = new LinkedList<String>();
   8:         
   9:     void printString(String str){
  10:         char[] charArray = str.toCharArray();
  11:         List<Character> charList = new ArrayList<Character>();
  12:         for(char ch: charArray){
  13:             charList.add(ch);
  14:         }
  15:         printCharacterArray(charList, new StringBuffer());
  16:         System.out.println(strs);
  17:     }
  18:  
  19:     private void printCharacterArray(List<Character> charList, StringBuffer temp) {
  20:         
  21:         StringBuffer savePoint = new StringBuffer(temp);
  22:         for(int index = 0; index <  charList.size(); index++){            
  23:             temp = new StringBuffer(savePoint);
  24:             temp.append(charList.get(index));
  25:             List<Character> tempChars = new ArrayList<Character>(charList);
  26:             tempChars.remove(index);
  27:             printCharacterArray(tempChars, temp);
  28:         }
  29:         if(charList.size() == 0){
  30:             strs.add(temp.toString());
  31:         }
  32:         temp = new StringBuffer();
  33:     }    
  34: }

Explanation:
In the above listing I have strs variable which keeps all the list.
printString method converts string into list of character and calls recursive function.
printCharacterScreen is a recursive method which iterate through the each element of the list and calls the same method again with list – element. The recursion breaks when there are no elements in the list then it adds the str to the list.
To run this code, copy the above code and save it to StringPermutations.java file. Add the following code of snippet.


1: public static void main(String[] args){

   2:     StringPermutations sp = new StringPermutations();
   3:     sp.printString("ABCD");
   4: }
Compile and run the class. It will print all combination of the ABCD string.

Condition B: if string has non-unique characters?
No issues, use java’s collection API well. Use Set instead of list to save all the string.

Disclaimer: The algo written here may not be performant. If you have some other algorithm which takes solves issue in lesser time complexity please let me know.

Sunday, August 22, 2010

Interview@X Company Data Structures – Part 1

My friend attended the Interview process at X company. He shared his experiences, his interview rounds and other information with me. Just thought of sharing the same information with the world.

His interview was scheduled@10 O’clock. The interview process was rapid and smooth. As soon as he reached the place he was called for the interview. He went through 3 rounds and was judges in 3 competencies i.e. Core Java, Data Structures and Puzzles.

I will put all the questions sent by him in few parts. I will start discussion with Data Structure questions as it will need least amount of googling for me :):).

There were very few simple questions from Data Structures side (I think, they were not looking for some super humans like Amazon, Google search :) ).

Que 1. You have given a link list, find the nth element of the element from the last…

gif_1

If input to the method is 2nd element, then D should be output of the method or program.

Ans: To solve this it is required to identify the end of the list and then traverse back from end. Or there should some other pointer which could suggest the element when other pointer has reached to end of the list.

As stated above there are 2 pointers required which will point to the start of the link list at the start.gif_1

Now Leading pointer will move to n-1 place first.

gif_1

After this will move the leading pointer and lagging pointer in the list until leading pointer reaches to null.

gif_1

Next step

gif_1

So Leading pointer has reached to Null and lagging pointer has reached to the output of the program.

Pseudo Code

   1: Struture Node{
   2:     char data;
   3:     Node *next;
   4: }
   5:  
   6: char findNFromLast(int n){
   7:     Node leadingPointer = Head;
   8:     Node laggingPointer = Head;
   9:     
  10:     for(int i =0 ; i < n-1; i++){
  11:         leadingPointer = leadingPointer->next;
  12:     }
  13:     
  14:     for(;leadingPointer->Next !=null;){
  15:         leadingPointer = leadingPointer->next;
  16:         laggingPointer = laggingPointer->next;
  17:     }
  18:     
  19:     return(laggingPointer->data);
  20:  
  21: }

This looks very simple and straight forward question. Complexity of the solution is o(n)… N is the number of nodes in the link list.


Disclaimer: This may not be the best optimal solution, if you guys have better solution then let me know.

Tuesday, August 3, 2010

SOP statements

During one of my friend's interview few questions were asked about SOP statements. Those are as follows.

How do you write message on standard output?
This is very trivial question and most of the Java developer have used SOPs several times while writing code,  debugging code or providing additional information to the user.

System.out.println("Write SOP Here");

In eclipse type Syso, and press CTRL+Enter, it will expand it to System.out.println. This was the very simple question to answer.

Sequel of the first question was, What do these components represent?
Few of us may know and few may not. So lets have a look on each of them.

There are 3 component of the statement.
System class can neither be instantiated nor be overridden as its default constructor which is marked as private. This class provide few utility important utility methods.

Out is the final and static instance of the PrintStream class. It is instantiated with the application and remain unchanged and log the data on the configuration of the system. PrintStream class belongs to java io package.

println is a method which flushes data and appends a New line character to printstream instance.

Sometime this information is not sufficient to answer this question efficiently. There is one more question that struck to my mind.

java.io have many other write streams also, so why was PrintStream chosen to write data on standard output?

Many of us may not know the answer. Lets start with what java doc has to say about it.

PrintStream adds functionality to another output stream, namely the ability to print representations of various data values conveniently. Two other features are provided as well. Unlike other output streams, a PrintStream never throws an IOException; instead, exceptional situations merely set an internal flag that can be tested via the checkError method. Optionally, a PrintStream can be created so as to flush automatically; this means that the flush method is automatically invoked after a byte array is written, one of the println methods is invoked, or a newline character or byte ('\n') is written.

As it does not throw any exception and data flushes after certain amount of bytes. This class provides suitable mechanism to use as a standard output stream to display all stack in exceptional scenarios as well.

After writing this entry my own fundamentals have improved about SOP and its components. I hope it helped you as well.

Disclaimer: All the material here is the result of research and understanding of other material. If there is some content which is either incorrect or inappropriate to the context of the article I am always open for discussion.

Saturday, July 24, 2010

Breadth First Search Algorithm

Here we will discuss one among the most important topic of DS i.e. Graphs. Breadth First Search Algorithm

BFS is the simplest algorithm to find a node in a graph.

Given a graph G = (V, E) and a vertex s to search, breadth first search algorithm finds all the elements reachable element from s, along with finding the element it computes the distance of the each reachable vertices and creates a BFT with root as s. For any vertex u reachable from s, the path in the BFT from s to u corresponds to the Shortest path in G.
Breadth First Search expands frontier between discovered and undiscovered uniformly across the breadth. i.e. As part of this algorithm first all the node at height K is discovered before discovering any node at depth k+1… BFS works both for directed and undirected graphs.

Algorithm

In this algo to keep track the progress, three colors will be used.
  • White: Initial stage of all the vertices.
  • Black: Vertex has been marked black if it does not have any white vertices next to it.
  • Grey: A vertex is marked grey if it has adjacent vertices of any color.
BFS constructs BFT having s as source. Whenever a white vertex v is discovered, in the course of scanning all adjacency vertices of u (Already discovered vertex), new edge(u,v) is added to tree. This is the way the whole graph will be accessed. To store grey vertices, queue data structure is used. Algo is using queue to use the vertices in the order they have been discovered.
Graphic display of the algorithm
G = (V,E)
V = {r, s, t , u, v, w, x, y};
E = {r-s, s-w, r-v, w-t, w-x, t-u, t-x, u-y, x-y}
First step: All the vertices are marked as white except source vertices. We will mark source vertex as Grey and add it into the queue.
bfs1
Second Step: It will retrieve one element from the queue and mark the fetched element as Black and will push its adjacent elements to the queue marking them as grey.
bfs2  \
here as you can see, s has been deleted from the queue and now marked as black. Adjacent element of s i.e. w and r are added to the queue.
Next: Second step will be followed till queue do not have any more elements. At each vertex level the distance of the vertex is also stored.
bfs9
 bfs3
 bfs4
bfs5
bfs6
bfs7
bfs8
Pseudo Code
Step 1: Assign white color to all the vertices, infinite for each vertex and to make it a tree it is necessary to have parent information, assign parent vertex as null to all vertices.
Step 2: Add source to the queue. Assign distance 0. Change the color of the source as grey.
Step 3: Retrieve first element from the queue. Mark the retrieved element as black.
    1. Find all the adjacent white vertices of the retrieve vertex.
    2. Mark them grey.
    3. Set the distance of the adjacent vertices to one more than the distance of existing vertex.
    4. Add them to queue.
Step 4: Repeat the step 3 until queue is empty.
Pseudo Code in programmatically
   1: BFS(G,s)
   2:  
   3: for each vertex u in V[G] - {s}
   4:     do  color[u] = white
   5:         dist[u] = inf
   6:         parent[u] = nil
   7:         
   8: color[s] = G
   9: dist[s] = 0
  10: parent[s] = nil
  11: Q.add(s)
  12:  
  13: while( Q is empty){
  14:     
  15:     do     u = delete(Q){
  16:         for each v in adj[u] {
  17:             
  18:             do if color[v] = w {
  19:                 
  20:                 color[v] = G
  21:                 parent[v] = u
  22:                 dist[v] = dist[u] + 1
  23:                 Q.add(v)
  24:                 
  25:             }
  26:             
  27:         }
  28:     }
  29:     
  30:     color[u] = B
  31:     
  32: }
Java Code
There is the Java code for the pseudo code mentioned above. I do not think there is need to explain this here.
   1: import java.util.HashMap;
   2: import java.util.List;
   3: import java.util.Map;
   4: import java.util.Queue;
   5: import java.util.Set;
   6: import java.util.concurrent.SynchronousQueue;
   7:  
   8:  
   9: public class BFS {
  10:  
  11:     Map<String, List<String>> graph;
  12:     BFTNode sourceNode;
  13:     Map<String, BFTNode> tree = new HashMap<String, BFTNode>();
  14:     
  15:     BFS(Map<String, List<String>> g, String source){
  16:         graph = g;
  17:         sourceNode = new BFTNode(source);
  18:     }
  19:     
  20:     void createBFTNodes(){
  21:         Set<String> vertices = graph.keySet();
  22:         for(String vertex : vertices){
  23:             tree.put(vertex, new BFTNode(vertex));
  24:             
  25:         }
  26:     }
  27:     
  28:     void algorithm(){
  29:         
  30:         createBFTNodes();
  31:         sourceNode.setColor(1);
  32:  
  33:         Queue<BFTNode> Q = new SynchronousQueue<BFTNode>();
  34:         Q.add(sourceNode);
  35:  
  36:         do{
  37:             
  38:             BFTNode node = Q.remove();
  39:             List<String> adjacentVertices = graph.get(node.getVertex());
  40:             
  41:             for(String adjacentVertex : adjacentVertices){
  42:                 
  43:                 BFTNode temp = new BFTNode(adjacentVertex);
  44:                 temp.setColor(1);
  45:                 temp.setDist(node.getDist() + 1);
  46:                 temp.setParent(node);
  47:                 Q.add(temp);
  48:                 tree.put(adjacentVertex, temp);
  49:                 
  50:             }
  51:             
  52:             node.setColor(2);
  53:             tree.put(node.getVertex(), node);
  54:             
  55:         }while(Q.size() > 0);
  56:         
  57:     }
  58:  
  59: }
  60:  
  61: //This class has getter/Setter method for all the property that a tree node require.
  62: class BFTNode{
  63:     
  64:     private int dist = 0;
  65:     private int color = 0;
  66:     private BFTNode parent = null;
  67:     private String vertex = "";
  68:     
  69:     public BFTNode(String name) {
  70:         vertex = name;
  71:     }
  72:     
  73:     public String getVertex() {
  74:         return vertex;
  75:     }
  76:  
  77:     public int getDist() {
  78:         return dist;
  79:     }
  80:  
  81:     public void setDist(int dist) {
  82:         this.dist = dist;
  83:     }
  84:  
  85:     public int getColor() {
  86:         return color;
  87:     }
  88:  
  89:     public void setColor(int color) {
  90:         this.color = color;
  91:     }
  92:  
  93:     public BFTNode getParent() {
  94:         return parent;
  95:     }
  96:  
  97:     public void setParent(BFTNode parent) {
  98:         this.parent = parent;
  99:     }
 100:  
 101:     public boolean equals(Object anotherObject){
 102:         if (anotherObject instanceof BFTNode){
 103:             return vertex.equals(((BFTNode)anotherObject).vertex);
 104:         }
 105:         return false;
 106:     }
 107:  
 108:     public int hashCode(){
 109:         return vertex.hashCode();
 110:     }
 111:     
 112:     public String toString(){
 113:         if(parent != null)
 114:             return ("Vertex:" + vertex + " Color:" + color + " Dist:" + dist + " Parent:" + parent.vertex);
 115:         else
 116:             return ("Vertex:" + vertex + " Color:" + color + " Dist:" + dist + " Parent: Null");
 117:     }
 118: }
Analysis
It is always mandatory to know how is the performance and resource utilization of the algorithm.
Time taken for the algorithm is O(V+E). This algorithm has linear time complexity which particularly depends upon the sum of the vertices and edges of the graph.
Other Algos implementing this algorithm internally
  1. Dijkstra’s Single Source Shortest Path Algorithm
  2. Prim’s Minimum Spanning tree Algorithm
Disclaimer: All the material here is the result of research and understanding of other material. If there is some content which is either incorrect or inappropriate to the context of the article I am always open for discussion.