Breadth First Traversal

When a dead end occurs in any iteration, the Breadth First Search (BFS) method traverses a graph in a breadthward motion and utilises a queue to remember to retrieve the next vertex to start a search.

Breadth First Traversal

As in the example given above, BFS algorithm traverses from A to B to E to F first then to C and G lastly to D. It employs the following rules.

  • Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in a queue.
  • Rule 2 − If no adjacent vertex is found, remove the first vertex from the queue.
  • Rule 3 − Repeat Rule 1 and Rule 2 until the queue is empty.
StepTraversalDescription
1Breadth First Search Step OneInitialize the queue.
2Breadth First Search Step TwoWe start from visiting S (starting node), and mark it as visited.
3Breadth First Search Step ThreeWe then see an unvisited adjacent node from S. In this example, we have three nodes but alphabetically we choose A, mark it as visited and enqueue it.
4Breadth First Search Step FourNext, the unvisited adjacent node from S is B. We mark it as visited and enqueue it.
5Breadth First Search Step FiveNext, the unvisited adjacent node from S is C. We mark it as visited and enqueue it.
6Breadth First Search Step SixNow, S is left with no unvisited adjacent nodes. So, we dequeue and find A.
7Breadth First Search Step SevenFrom A we have D as unvisited adjacent node. We mark it as visited and enqueue it.

At this point, there are no unmarked (unvisited) nodes. However, according to the algorithm, we must continue dequeuing in order to obtain all unvisited nodes. The program ends when the queue is empty.

0

43 thoughts on “Breadth First Traversal”

  1. With havin so much written content do you ever run into any problems of plagorism or copyright infringement?
    My website has a lot of exclusive content I’ve either
    written myself or outsourced but it looks like a lot of it is popping it up all over
    the internet without my agreement. Do you know any ways to help protect against content from being
    ripped off? I’d truly appreciate it.

    0
  2. I’m really impressed with your writing skills as well as with the layout on your blog.

    Is this a paid theme or did you modify it yourself? Anyway keep up the nice quality writing, it’s
    rare to see a great blog like this one these days.

    0
  3. Do you mind if I quote a few of your posts as long as I provide
    credit and sources back to your weblog? My blog site is in the
    very same niche as yours and my users would really benefit from a lot of the
    information you provide here. Please let me know
    if this alright with you. Appreciate it!

    0
  4. Hello There. I discovered your blog the use of msn. That is a very neatly written article.
    I will make sure to bookmark it and come back to learn extra of your helpful information.
    Thank you for the post. I will definitely comeback.

    0
  5. Hello there, I found your site by way of Google at the same time as looking
    for a similar topic, your site got here up, it seems great.
    I have bookmarked it in my google bookmarks.

    Hello there, simply become aware of your blog thru Google, and found that it’s truly informative.
    I’m gonna watch out for brussels. I will appreciate in the event
    you continue this in future. A lot of people will be benefited
    out of your writing. Cheers!

    0
  6. Fantastic beat ! I would like to apprentice while you amend your site,
    how can i subscribe for a blog site? The account helped me a acceptable deal.
    I had been a little bit acquainted of this your broadcast
    provided bright clear idea

    0
  7. I do not know if it’s just me or if everybody else
    encountering problems with your site. It looks like some
    of the written text on your posts are running off the screen. Can someone else please
    provide feedback and let me know if this is happening to them as well?
    This may be a problem with my internet browser because I’ve had this happen previously.

    Thanks

    0
  8. Aw, this was an exceptionally good post. Taking the time and actual effort to generate a
    really good article… but what can I say…
    I put things off a whole lot and never manage to get anything done.

    0

Leave a Comment

Your email address will not be published. Required fields are marked *

4 + two =