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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s