FazBrowse GitHub Viewer | Trending | | Home

Tools: [Download Repo ZIP] [View Raw Code] [Original HTTPS Page]

python/graph.py at data-struct · Onlykee/python · GitHub

35 lines (31 loc) · 865 Bytes

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

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

Back | FazBrowse Home | New Git URL