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
_______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
