首页 > 代码库 > Python_自定义有向图

Python_自定义有向图

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_自定义有向图