Programs in Python for BFS

Posted on Updated on

Breadth-first search (BFS) is an algorithm used for traversing graph data structures. BFS implements a specific strategy for visiting all the nodes (vertices) of a graph. BFS starts with a node, then it checks the neighbours of the initial node, then the neighbours of the neighbours, and so on.

I’ve created a connected graph with 7 nodes and 8 edges. The edges are undirected and unweighted.  Distance between two nodes will be measured based on the number of edges separating two vertices.   I use the adjacency list to represent the above graph. An effective/elegant method for implementing adjacency lists in Python is using dictionaries. The keys of the dictionary represent nodes, the values have a list of neighbours.

1111

The following screen shot represents representation of the above graph and output shows the result of running Breadth First Search (BFS) algorithm.  Can you explain the output?  Can you write program in Python ?

Send your suggestions and comments to    mehtaashwin@vissicomp.in

Best answer will be rewarded.

22222

Created and edited by Dr. Ashwin I Mehta  at Vissicomp Technology

Please check the schedule or reach at http://www.vissicomp.com/

For more details Call us @9320957718 / 17

 

 

 

 

 

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

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

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s