python/data_struct/graph.py at data-struct · wangpanjun/python · GitHub

35 lines (31 loc) · 865 Bytes

def searchGraph(graph,start,end):

results=[]

generatePath(graph,[start],end,results)

results.sort(lambda x,y:cmp(len(x),len(y)))

return results

def generatePath(graph,path,end,results):

state=path[-1]

if state == end:

results.append(path)

else:

for arc in graph[state]:

if arc not in path:

generatePath(graph,path+[arc],end,results)

if __name__ == "__main__":

Graph={

'A':['B','C','D'],

'B':['E'],

'C':['D','F'],

'D':['B','E','G'],

'E':[],

'F':['D','G'],

'G':['E']

}

r = searchGraph(Graph,'A','D')

print "A to D"

for i in r:

print i

r=searchGraph(Graph,'A','E')

print "A to E"

for i in r:

print i

Expand file tree