[Tutor] Breadth first search

[Kent Johnson]

Nicky Ng wrote:
> Hi,
>  
> I would like to implement a breadth first serach with Python and read 
> data from a text file with following file format
>  
> Could you give me any idea how to implement this search program with Python?

Hmm, sounds like homework to me.

The first thing I would do is pick a representation for the graph. One
way is to use a dictionary where the keys are the name of the start
vertex and the values are lists of ending vertices. In your case you
also need to find a way to store the weight of the edge.

Next you need to read the data file and create the chosen graph
representation for the data.

Finally you can implement the breadth-first search. A classic
breadth-first search uses a queue; you can use a list for this -
list.append() adds a new element, list.pop() removes an element from teh
other end.

Wikipedia calls breadth-first search on a weighted graph a uniform-cost
search and recommends using a priority queue instead of a FIFO. Python's
heapq module can help here.

Kent