For BFS(Breadth first search)

So, basically you have to use Queue as a data structure

Follow algorithm for BFS

1. Start with one node of graph. It may be travers from left to right.
2. So there are two factrors which are important for traversing .. first
that the node is visited or not and second one is there any adjecent
nodes for current node
3. If we are visiting current node then add node into queue
4. If the current node having adjecent nodes then add those nodes into
queue
5. If there are no more adjecent are found then print the current node
and place the pointer to first node of queue
6. Repeat these until all nodes get traversed.
For DFS(Depth First Search)

For implementation of DFS you must know Stack data structure

Follow these steps

1. In this traversal you must know the operation of stack

2. Start from one of the graph node it may be start from left to right
3. Visit the current node and push it to stack
4. Check the top of the stack having adjecent nodes
5. If yes then push the adjecent nodes into stack
6. If no then print the top of the stack and pop it from stack
7. Repeat these steps until you will visit all node
DFS algorithm
Traversal means visiting all the nodes of a graph. Depth first traversal or Depth first
Search is a recursive algorithm for searching all the vertices of a graph or tree data
structure. In this article, you will learn with the help of examples the DFS algorithm,
DFS pseudocode and the code of the depth first search algorithm with
implementation in C++, C, Java and Python programs.

DFS algorithm
A standard DFS implementation puts each vertex of the graph into one of two
categories:

1. Visited
2. Not Visited

The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.

The DFS algorithm works as follows:

1. Start by putting any one of the graph's vertices on top of a stack.

2. Take the top item of the stack and add it to the visited list.
3. Create a list of that vertex's adjacent nodes. Add the ones which aren't in the
visited list to the top of stack.
4. Keep repeating steps 2 and 3 until the stack is empty.

DFS example
Let's see how the Depth First Search algorithm works with an example. We use an
undirected graph with 5 vertices.

We start from vertex 0, the DFS algorithm starts by putting it in the Visited list and
putting all its adjacent vertices in the stack.
Next, we visit the element at the top of stack i.e. 1 and go to its adjacent nodes.
Since 0 has already been visited, we visit 2 instead.

Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the top of the stack
and visit it

After we visit the last element 3, it doesn't have any unvisited adjacent nodes, so we
have completed the Depth First Traversal of the graph.
DFS pseudocode (recursive implementation)
The pseudocode for DFS is shown below. In the init() function, notice that we run the
DFS function on every node. This is because the graph might have two different
disconnected parts so to make sure that we cover every vertex, we can also run the
DFS algorithm on every node.

DFS(G, u)
u.visited = true
for each v ∈ G.Adj[u]
if v.visited == false
DFS(G,v)

init() {
For each u ∈ G
u.visited = false
For each u ∈ G
DFS(G, u)
}
Traversal means visiting all the nodes of a graph. Breadth first traversal or Breadth
first Search is a recursive algorithm for searching all the vertices of a graph or tree
data structure. In this article, you will learn with the help of examples the BFS
algorithm, BFS pseudocode and the code of the breadth first search algorithm with
implementation in C++, C, Java and Python programs.

BFS algorithm
A standard DFS implementation puts each vertex of the graph into one of two
categories:

1. Visited
2. Not Visited

The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.

The algorithm works as follows:

1. Start by putting any one of the graph's vertices at the back of a queue.
2. Take the front item of the queue and add it to the visited list.
3. Create a list of that vertex's adjacent nodes. Add the ones which aren't in the
visited list to the back of the queue.
4. Keep repeating steps 2 and 3 until the queue is empty.

The graph might have two different disconnected parts so to make sure that we
cover every vertex, we can also run the BFS algorithm on every node

BFS example
Let's see how the Breadth First Search algorithm works with an example. We use an
undirected graph with 5 vertices.

We start from vertex 0, the BFS algorithm starts by putting it in the Visited list and
putting all its adjacent vertices in the stack.
Next, we visit the element at the front of queue i.e. 1 and go to its adjacent nodes.
Since 0 has already been visited, we visit 2 instead.

Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the back of the
queue and visit 3, which is at the front of the queue.
Only 4 remains in the queue since the only adjacent node of 3 i.e. 0 is already
visited. We visit it.

Since the queue is empty, we have completed the Depth First Traversal of the graph.

BFS pseudocode
create a queue Q

mark v as visited and put v into Q

while Q is non-empty

remove the head u of Q

mark and enqueue all (unvisited) neighbours of u

Kruskal's Algorithm
Kruskal's algorithm is a minimum spanning tree algorithm that takes a graph as input
and finds the subset of the edges of that graph which

 form a tree that includes every vertex

 has the minimum sum of weights among all the trees that can be formed from
the graph

How Kruskal's algorithm works

It falls under a class of algorithms called greedy algorithms which find the local
optimum in the hopes of finding a global optimum.

We start from the edges with the lowest weight and keep adding edges until we we
reach our goal.

The steps for implementing Kruskal's algorithm are as follows:

1. Sort all the edges from low weight to high

2. Take the edge with the lowest weight and add it to the spanning tree. If adding
the edge created a cycle, then reject this edge.
3. Keep adding edges until we reach all vertices.

Example of Kruskal's algorithm

Kruskal Algorithm Pseudocode
Any minimum spanning tree algorithm revolves around checking if adding an edge
creates a loop or not.

The most common way to find this out is an algorithm called Union FInd. The Union-
Find algorithm divides the vertices into clusters and allows us to check if two vertices
belong to the same cluster or not and hence decide whether adding an edge creates
a cycle.

KRUSKAL(G):
A = ∅
For each vertex v ∈ G.V:
MAKE-SET(v)
For each edge (u, v) ∈ G.E ordered by increasing order by
weight(u, v):
if FIND-SET(u) ≠ FIND-SET(v):
A = A ∪ {(u, v)}
UNION(u, v)
return A

Prim's Algorithm
Prim's algorithm is a minimum spanning tree algorithm that takes a graph as input
and finds the subset of the edges of that graph which

 form a tree that includes every vertex

 has the minimum sum of weights among all the trees that can be formed from
the graph

How Prim's algorithm works

It falls under a class of algorithms called greedy algorithms which find the local
optimum in the hopes of finding a global optimum.

We start from one vertex and keep adding edges with the lowest weight until we we
reach our goal.

The steps for implementing Prim's algorithm are as follows:

1. Initialize the minimum spanning tree with a vertex chosen at random.

2. Find all the edges that connect the tree to new vertices, find the minimum and
add it to the tree
3. Keep repeating step 2 until we get a minimum spanning tree
Example of Prim's algorithm
Prim's Algorithm pseudocode
The pseudocode for prim's algorithm shows how we create two sets of vertices U
and V-U. U contains the list of vertices that have been visited and V-U the list of
vertices that haven't. One by one, we move vertices from set V-U to set U by
connecting the least weight edge.

T = ∅;
U = { 1 };
while (U ≠ V)
let (u, v) be the lowest cost edge such that u ∈ U and v ∈ V
- U;
T = T ∪ {(u, v)}
U = U ∪ {v}
Dynamic Programming
Dynamic Programming is a technique in computer programming that helps to
efficiently solve a class of problems that have overlapping subproblems and optimal
substructure property.

Such problems involve repeatedly calculating the value of the same subproblems to
find the optimum solution.

Dynamic Programming Example

Take the case of generating the fibonacci sequence.

If the sequence is F(1) F(2) F(3)........F(50), it follows the rule F(n) = F(n-1) + F(n-2)

F(50) = F(49) + F(48)

F(49) = F(48) + F(47)

F(48) = F(47) + F(46)

...

Notice how there are overlapping subproblems, we need to calculate F(48) to

calculate both F(50) and F(49). This is exactly the kind of algorithm where Dynamic
Programming shines.

How Dynamic Programming Works

Dynamic programming works by storing the result of subproblems so that when their
solutions are required, they are at hand and we do not need to recalculate them.

This technique of storing value of subproblems is called memoization. By saving the

values in the array, we save time for computations of sub-problems we have already
come across.

var m = map(0 → 0, 1 → 1)

function fib(n)

if key n is not in map m

m[n] = fib(n − 1) + fib(n − 2)

 return m[n]

Dynamic programming by memoization is a top-down approach to dynamic

programming. By reversing the direction in which the algorithm works i.e. by starting
from the base case and working towards the solution, we can use also implement
dynamic programming in a bottom-up manner.

function fib(n)

if n = 0

return 0

else

var prevFib = 0, currFib = 1

repeat n − 1 times

var newFib = prevFib + currFib

prevFib = currFib

currFib = newFib

return currentFib

Recursion vs Dynamic Programming

Dynamic programming is mostly applied to recursive algorithms. This is not a
coincidence, most optimization problems require recursion and dynamic
programming is used for optimization.

But not all problems that use recursion can use Dynamic Programming. Unless there
is a presence of overlapping subproblems like in the fibonacci sequence problem, a
recursion can only reach the solution using a divide and conquer approach.

That is the reason why a recursive algorithm like Merge Sort cannot use Dynamic
Programming, because the subproblems are not overlapping in any way.
Greedy Algorithms vs Dynamic Programming
Greedy Algorithms are similar to dynamic programming in the sense that they are
both tools for optimization.

However, greedy algorithm look for locally optimum solution or in other words, a
greedy choice, in the hopes of finding a global optimum. Hence greedy algorithms
can make a guess that looks optimum at the time but becomes costly down the line
and do not guarantee a globally optimum.

Dynamic programming, on the other hand, find the optimal solution to subproblems
and then making an informed choice to combine the results of those subproblems to
find the most optimum solution.

NOTE:

In computer science, a problem is said to have optimal substructure if an optimal solution can
be constructed from optimal solutions of its subproblems. This property is used to determine the
usefulness of dynamic programming and greedy algorithms for a problem.[1]
Typically, a greedy algorithm is used to solve a problem with optimal substructure if it can be
proven by induction that this is optimal at each step. [1]Otherwise, provided the problem
exhibits overlapping subproblems as well, dynamic programming is used. If there are no
appropriate greedy algorithms and the problem fails to exhibit overlapping subproblems, often a
lengthy but straightforward search of the solution space is the best alternative.
In the application of dynamic programming to mathematical optimization, Richard
Bellman's Principle of Optimality is based on the idea that in order to solve a dynamic
optimization problem from some starting period t to some ending period T, one implicitly has to
solve subproblems starting from later dates s, where t<s<T. This is an example of optimal
substructure. The Principle of Optimality is used to derive the Bellman equation, which shows
how the value of the problem starting from t is related to the value of the problem starting from s.

MINIMUM SPANNING TREE

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges
of a connected, edge-weighted undirected graph that connects all the vertices together, without
any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose
sum of edge weights is as small as possible. More generally, any edge-weighted undirected
graph (not necessarily connected) has a minimum spanning forest, which is a union of the
minimum spanning trees for its connected components.

Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least

possible weight that connects any two trees in the forest. [1] It is a greedy algorithm in graph
theory as it finds a minimum spanning tree for a connected weighted graph adding increasing
cost arcs at each step.[1] This means it finds a subset of the edges that forms a tree that includes
every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not
connected, then it finds a minimum spanning forest (a minimum spanning tree for
each connected component).

1 A = ∅
KRUSKAL(G):

2 foreach v ∈ G.V:
3 MAKE-SET(v)
4 foreach (u, v) in G.E ordered by weight(u, v), increasing:
5 if FIND-SET(u) ≠ FIND-SET(v):
6 A = A ∪ {(u, v)}
7 UNION(u, v)
8 return A

Complexity[edit]
Kruskal's algorithm can be shown to run in O(E log E) time, or equivalently, O(E log V) time,
where E is the number of edges in the graph and V is the number of vertices, all with simple data
structures. These running times are equivalent because:
 E is at most and is .
 Each isolated vertex is a separate component of the minimum spanning forest. If we ignore
isolated vertices we obtain V ≤ 2E, so log V is .
PSEUDOCODE OF RADIX SORT
1
2
3 Radix-Sort(A, d)
//It works same as counting sort for d number of passes.
4 //Each key in A[1..n] is a d-digit integer.
5 //(Digits are numbered 1 to d from right to left.)
6 for j = 1 to d do
7 //A[]-- Initial Array to Sort
8 int count[10] = {0};
//Store the count of "keys" in count[]
9
//key- it is number at digit place j
10 for i = 0 to n do
11 count[key of(A[i]) in pass j]++
12
13 for k = 1 to 10 do
14 count[k] = count[k] + count[k-1]
15
16 //Build the resulting array by checking
//new position of A[i] from count[k]
17 for i = n-1 downto 0 do
18 result[ count[key of(A[i])] ] = A[j]
19 count[key of(A[i])]--
20
21 //Now main array A[] contains sorted numbers
22 //according to current digit place
for i=0 to n do
23
A[i] = result[i]
24
25 end for(j)
26 end func
27
28

ASYMPTOTIC ANALYSIS OF RADIX SORT

In this algorithm running time depends on intermediate sorting algorithm which is counting sort. If
the range of digits is from 1 to k, then counting sort time complexity is O(n+k). There are d
passes i.e counting sort is called d time, so total time complexity is O(nd+nk) =O(nd). As k=O(n)
and d is constant, so radix sort runs in linear time.

Worst Case Time complexity: O (nd)

Average Case Time complexity: O(nd)
Best Case Time complexity: O(nd)
Space Complexity: O(n+k)
 Data Structure: Array
Sorting In Place: No
Stable: Yes

Radix Sort
 TUTORIAL
 PROBLEMS
 VISUALIZERBETA


Prerequisite: Counting Sort

QuickSort, MergeSort, HeapSort are comparison based sorting algorithms.

CountSort is not comparison based algorithm. It has the complexity of O(n+k), where k is the
maximum element of the input array.
So, if k is O(n) ,CountSort becomes linear sorting, which is better than comparison based sorting
algorithms that have O(nlogn) time complexity. The idea is to extend the CountSort algorithm to
get a better time complexity when k goes O(n2). Here comes the idea of Radix Sort.

Algorithm:
For each digit i where i varies from the least significant digit to the most significant digit of a
number
Sort input array using countsort algorithm according to ith digit.

We used count sort because it is a stable sort.

Example: Assume the input array is:

10,21,17,34,44,11,654,123
Based on the algorithm, we will sort the input array according to the one's digit (least significant
digit).
0: 10
1: 21 11
2:
3: 123
4: 34 44 654
5:
6:
7: 17
8:
9:

So, the array becomes 10,21,11,123,24,44,654,17

Now, we'll sort according to the ten's digit:
0:
1: 10 11 17
2: 21 123
3: 34
4: 44
5: 654
6:
7:
8:
9:

Now, the array becomes : 10,11,17,21,123,34,44,654

Finally , we sort according to the hundred's digit (most significant digit):
0: 010 011 017 021 034 044
1: 123
2:
3:
4:
5:
6: 654
7:
8:
9:

The array becomes : 10,11,17,21,34,44,123,654 which is sorted. This is how our algorithm
works.

Implementation:
void countsort(int arr[],int n,int place)
{
int i,freq[range]={0}; //range for integers is 10 as digits
range from 0-9
int output[n];
for(i=0;i<n;i++)
freq[(arr[i]/place)%range]++;
for(i=1;i<range;i++)
freq[i]+=freq[i-1];
for(i=n-1;i>=0;i--)
{
output[freq[(arr[i]/place)%range]-1]=arr[i];
freq[(arr[i]/place)%range]--;
}
for(i=0;i<n;i++)
arr[i]=output[i];
}
void radixsort(ll arr[],int n,int maxx) //maxx is the maximum
element in the array
{
int mul=1;
while(maxx)
{
countsort(arr,n,mul);
mul*=10;
maxx/=10;
}
}

Complexity Analysis:
The complexity is O((n+b)∗logb(maxx)) where b is the base for representing numbers
and maxx is the maximum element of the input array. This is clearly visible as we
make (n+b) iterations logb(maxx) times (number of digits in the maximum element) .
If maxx≤nc,then the complexity can be written as O(n∗logb(n)).

Advantages :
1. Fast when the keys are short i.e. when the range of the array elements is less.
2. Used in suffix array constuction algorithms like Manber's algorithm and DC3 algorithm.

Disadvantages:
1. Since Radix Sort depends on digits or letters, Radix Sort is much less flexible than other sorts.
Hence , for every different type of data it needs to be rewritten.
2. The constant for Radix sort is greater compared to other sorting algorithms.
3. It takes more space compared to Quicksort which is inplace sorting.

The Radix Sort algorithm is an important sorting algorithm that is integral to suffix -array
construction algorithms. It is also useful on parallel machines.

Contributed by: Shubham Gupta