Python_自定义有向图，,directedGr

Python_自定义有向图，,directedGr

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 ‘‘‘

Python_自定义有向图