Python_自定义有向图

             1
            class
             DirectedGraph(object):

             2
            def
            __init__
            (self,d):

             3
            if
             isinstance(d,dict):

             4             self.__graph = d
 5else:
 6             self.__graph = dict()
 7print(‘Sth error‘)
 8 9def__generatePath(self,graph,path,end,results):
10         curret = path[-1]
11if curret == end:
12            results.append(path)
13else:
14for n in graph[curret]:
15if n notin path:
16                     self.__generatePath(graph,path+[n],end,results)
1718def 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))   #按所有路径的长度进行排序22print(‘The path from ‘,self.__results[0][0],‘to‘,self.__results[0][-1],‘is:‘)
23for path in self.__results:
24print(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‘)
3536‘‘‘输出结果37The 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‘]
43The 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‘‘‘