directedGraph.py
1 class DirectedGraph(object): 2 def __init__(self,d): 3 if isinstance(d,dict): 4 self.__graph = d 5 else: 6 self.__graph = dict() 7 print('Sth error') 8 9 def __generatePath(self,graph,path,end,results): 10 curret = path[-1] 11 if curret == end: 12 results.append(path) 13 else: 14 for n in graph[curret]: 15 if n not in path: 16 self.__generatePath(graph,path+[n],end,results) 17 18 def searchPath(self,start,end): 19 self.__results = [] 20 self.__generatePath(self.__graph,[start],end,self.__results) 21 self.__results.sort(key=lambda x:len(x)) #按所有路径的长度进行排序 22 print('The path from ',self.__results[0][0],'to',self.__results[0][-1],'is:') 23 for path in self.__results: 24 print(path) 25 d={'A':['B','C','D'], 26 'B':['E'], 27 'C':['D','F'], 28 'D':['B','E','G'], 29 'E':['D'], 30 'F':['D','G'], 31 'G':['E']} 32 g=DirectedGraph(d) 33 g.searchPath('A','D') 34 g.searchPath('A','E') 35 36 '''输出结果 37 The path from A to D is: 38 ['A', 'D'] 39 ['A', 'C', 'D'] 40 ['A', 'B', 'E', 'D'] 41 ['A', 'C', 'F', 'D'] 42 ['A', 'C', 'F', 'G', 'E', 'D'] 43 The path from A to E is: 44 ['A', 'B', 'E'] 45 ['A', 'D', 'E'] 46 ['A', 'C', 'D', 'E'] 47 ['A', 'D', 'B', 'E'] 48 ['A', 'D', 'G', 'E'] 49 ['A', 'C', 'D', 'B', 'E'] 50 ['A', 'C', 'D', 'G', 'E'] 51 ['A', 'C', 'F', 'D', 'E'] 52 ['A', 'C', 'F', 'G', 'E'] 53 ['A', 'C', 'F', 'D', 'B', 'E'] 54 ['A', 'C', 'F', 'D', 'G', 'E'] 55 '''