FilesExpand file tree

 data-struct

/

graph.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

35 lines (31 loc) · 865 Bytes

 data-struct

/

graph.py

Top

File metadata and controls

• Code
• Blame

35 lines (31 loc) · 865 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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