BFS and DFS Algorithms

Standard

Graph Algorithms is an amazing and excited area to anyone who like Computer Science and a bit of logic and Mathematics. With this algorithms and  the abstractions which they can bring to us, we can figure out the World and imagine the World as a Global Graph! We are vertex and our relationships can be the edges between us.

When I was in my Third Semester in my graduation, I have the opportunity to get an overview about these algorithms, therefore I could imagine that in the end of this class, my vision had been changed, now I was with a global vision, I could imagine and model problems about the Real World, using only vertex and edges. It was amazing for me! If you check the Google Maps, or maybe your GPS you are probably using some Graph Algorithm!

The vision which I want to tell you is that the Graphs can be important things to open our mind and they can help us to model any problem in your real life.

Now, I’m starting my studies about Artificial Intelligence and I want to practice the knowledges which I could obtain a long time ago in my classes of Graph Algorithms.

The Search Algorithms may be used together with Graphs. We have a lot of special and good algorithms to find the shortest path and others amazing things. In this post my focus will be only in two important Search Algorithms the Breadth-First Search and the Depth-First Search. They are very similar, but we may check several differences between them too. Let us check ?

Firstly, When I was studying at first time these algorithms, I could not find the real difference between them! It was the something for me! With this in mind, I went to my computer and get started to implement them, with some searches on Google you can check that a main difference is that one search use a Queue and other use a stack. What is this?! Why they have this difference?! Now, I’m so more confused, you may thinking…

This is a sensitive difference, with this, with these two structures we can give their names: Breadth and Depth. So, The Breadth uses a Queue and the Depth uses a Stack. When you think in Depth, and you want to represent this in your mind, how could be a data structure which can represent it? Maybe, a Stack, did you remember that in a stack the Last In, First Out, this can get a notion of Depth, no? The Last Person to enter in your home will be the First to get out there, mainly if you are stacking these persons. Now you want a notion of Breadth and you may think that you will use a Queue. But why? If you remember, with the Queue, you get the notion First in, First Out, so, you are not stacking the persons who have been entered in your home, these persons are entering and geting out fastly, with this in mind a lot of others persons may enter in your home and you can “search” and to know more persons! Do you get it ? This is the main point of this post! With this two notions of Stack and Queue you will probably solve all your misunderstood problems about BFS and DFS!

Remembering… You have a house. You must to look persons, you want to look a lot of persons. How Data Structure you will utilize ? Of course a Queue! The First person to enter in your home will be the First person to get out there! And with this, you will “increase the flow of persons” entering and getting out your home.  Now you want to know more the persons who are inside your home, how do you get this? You must really have a depth knowledge of these persons. So, the Last Person to in will be the First person to get out your home, remembering that for a person get out, all of others must not be in the Stack, with this, the first person to enter will be the person who have spent more time inside your home! And you will have a depth knowledge of these persons!!

As in the Real Life, with the Graph Algorithms cannot be different. Your problem will depend on your structure and how you will model your problem, you can get a lot of variables and with this we can get a assurance in which search algorithm to use. But, to help us in your choice in which algorithm to our problem, we get some hints.

Applications

What can BFS do and DFS can’t?

Finding Shortest paths.

What can DFS and BFS can’t?

Finding out if a connected undirected graph is biconnected.

__________________________________________________________

Both these algorithms can find a spanning tree,connected components, find paths and cycles.

Shortest Paths we can use the BFS rather than DFS.

Biconnected components we can use DFS rather than BFS.

BFS can be used to test bipartiteness, by starting the search at any vertex and giving alternating labels to the vertices visited during the search. DFS is an uniformed search that progresses by expading the first child node of the search tree that appears and thus going deeper and deeper until goal node is found, or until it hits a node that has no children.

Depth-First Search

The time and space analysis of DFS will depend on the data structures used to simulate it, but in theoretical computer science, DFS is tipically used to traverse an entire graph, and takes time O(|V| + |E|), linear in the size of the graph.

Some applications:

  • To construct a DSF tree/forest from a graph
  • Directed Graph Strongly connected
  • To find the connected components of a graph

Breadth-First Search

When the number of vertices in the graph is know ahead of time, and additional data structures are used to determine which vertices have already been added to the queue, the space of

Some applications:

  • Finding all nodes within one connected component
  • Testing a graph for Bipartiteness
  • Others applications

Implementations

You can check my github to see some implemetantions

A quick analysis about Quicksort

Standard

If you are a computer scientist or a computer science student and you are studying Introduction to Algorithms you may have talked about Quicksort. A lot of people has talked about this sorting algorithm or maybe you professor has taught to you. With this post I’ll do some interesting things about this algorithm and We will think about how the persons does like so much Quicksort.

As like MergeSort(maybe i will talk about MergeSort in other posts) Quicksort is a divider and conquer algorithm. Maybe the main difference between them it’s about the divide phase. In MergeSort a recursive merging  is called, when We run Quicksort the divide phase can be translated for the Partition Algorithm, that can produce two subarrays in relation a pivot, ie, a recursive partition is called. The combine phase in quicksort is trivial, because when the partition algorithm has been called it combines itself. Since the subarrays are sorted in place, no work is needed to combine them.

 

The partition algorithm can divide the array A[p…r] in two subarrays as you can see on the above picture. The partition has a linear Time Ο(n). A[p…q-1] and A[q+1…r] such that each element of  A[p…q-1] is less than or equal to A[q], which is, in turn, less than or equal to each element of A[q+1…r]. Compute the index q as part of this partitioning procedure.

With the partition routine the Quicksort is easy.

If we will analyse the quicksort, what is your worst-case time ?

  • Input sorted or Reverse sorted
  • One side of partition has no elements.
T(n) =  T(0) + T(n-1) + θ(n)
         =  θ(1) + T(n-1) + θ(n)
         =  T(n-1)+ θ(n)
          = θ(n²)
Best-case analysis (intuition):
If we’re really luck, partition slipts the array on the middle.  We have:
T(n) = 2.T(n/2) + θ(n)
         = θ(n lg n)
Suppose, for example, that the partitioning routine always produce 9-to-1 proportional split. At first blush seems quite unbalanced. What do you think? Does the partition has lucky ? Or not ? We can analyze the recursion tree:
Thus, with a 9-to-1 proportional split at every level of recursion, which intuitively seems quite unbalanced, quicksort runs O(n lg n) time-assymptotically the same as if the splt were right down the middle.
You can see the lecture from Charles E. Leiserson – MIT  .

Non-Recursive Hanoi

Standard

A lot of people can think about how to do the Non-recursive Hanoi algorithm.

There is a Binary Solution(Binary Solution), and a version of a non-recursive on Wikipedia in others sites.

My algorithm was based on:

Hanoi Non-Recursive Solution (Wikipedia)

Moves Hanoi

The Algorithm:

Input: Number of disks(n = number of disks)
Output: Movements of Hanoi Tower

for ( i <- 1,...,2^n -1 )


if( n == even number)


if( i == odd number )
moveright();

else
movenormal();

else

if( i == oddnumber)
moveleft();

else
movenormal();

About the functions:

moveright();

This function moves the smaller disk in right direction.

moveleft();

This function moves the smaller disk in left direction.

movenormal();

This function moves the non-smaller disk in a movement that not involves the smaller disk.

The functions moveright() and moveleft() can be proved by induction.