python无向加权图-凯发k8官方网
一般来讲，实现图的过程中需要有两个自定义的类进行支撑：顶点(vertex)类，和图(graph)类。按照这一架构，vertex类至少需要包含名称(或者某个代号、数据)和邻接顶点两个参数，前者作为顶点的标识，后者形成顶点和顶点相连的边，相应地必须有访问获取和设定参数的方法加以包装。graph类至少需要拥有一个包含所有点的数据结构(列表或者map等)，相应地应该有新增顶点、访问顶点、新增连接边等方法。当然，为了实现dijkstra算法(一种基本的最短路径算法)，除了可以在graph类里增加一个执行dijkstra算法的方法以外，还需要在vertex类里增加用于dijkstra算法的一些参数：某一个顶点距离dijkstra搜索起点的距离，以及一旦完成dijkstra搜索需要回溯路径时，前驱顶点的信息。
在这里记录用python实现以上基本方法和dijkstra算法的代码，因为python中的现成的数据结构类型便于使用，比如字典dict类，很方便地能够构造一个类似于map的映射，而且python的sort方法也特别好用。首先是自定义类顶点(vertex)的代码，如上所述，为了满足bfs算法的执行和回溯的需要，vertex类一共有四个参数：id(标记)、connections(邻接顶点字典，键值为邻接顶点，对应值为权重或者边长)、前驱顶点pre和从起点的距离distance。这二者在dijkstra算法的执行过程中被赋值，在回溯时需要利用pre的信息。
vertex类的方法中多数为基本的访问参数(get)-设定参数(set)的方法对，比如访问/设定邻接顶点信息的 add_neighbour(neighbour, weight) 和 get_connection() ，访问/设定前驱顶点信息的 get_pre() 和 set_pre(prev) ，以及访问/设定从起点起距离的 get_distance() 和 set_distance(dist) 。除此之外重载了字符串化方法，即__str__，这便于print函数和str函数将vertex类转化为一个有意义的字符串。
1 classvertex:2 #初始化构造函数，name为字符串，connections字典为
3 #前驱顶点pre，从起点距离distance，在dijkstra执行赋值后有意义
4 def __init__(self, name):5 self.id =name6 self.pre =none7 self.distance = float('inf')8 self.connections =dict()9
10 #重载字符串化函数，返回字符串
11 def __str__(self):12 return str(self.id) "connected to:" str([x.id for x inself.connections])13
14 #增加相邻顶点，neighbour为vertex类，weight为浮点型边权重
15 def add_neighbour(self, neighbour, weight=0):16 self.connections[neighbour] =weight17
18 #获取顶点id函数
19 defget_id(self):20 returnself.id21
22 #获取顶点邻接点的函数，返回键值(vertex)列表
23 defget_connections(self):24 returnself.connections.keys()25
26 #获取顶点与邻接点边权重，传入vertex类对象neighbour，返回weight(fl)
27 defget_weight(self, neighbour):28 returnself.connections[neighbour]29
30 #获取顶点的距离(在bfs执行后使用)
31 defget_distance(self):32 returnself.distance33
34 #获取前驱顶点(在dijkstra执行后使用)
35 defget_pre(self):36 returnself.pre37
38 #设定顶点的距离(在dijkstra执行过程中调用)
39 defset_distance(self, dist):40 self.distance =dist41
42 #设定前驱顶点(在dijkstra执行过程中调用)
43 defset_pre(self, prev):44 self.pre = prev
图(graph)类：拥有两个参数：顶点字典(顶点id：顶点vertex类)和顶点数量。顶点数量这个参数似乎没什么用，除非是增加一个判断图是否为空的 isempty() 方法和 getsize() 方法可能用得着。
方法中包含新增顶点的 add_vertex(name) ，按照id获取顶点的 get_vertex(name) 。dict的数据结构给按照id访问顶点在空间上和时间上都创造了极大的方便，也为此参数中为顶点字典而不用顶点列表。添加边的方法 add_edge(vertex1, vertex2, weight) ，其中需要调用vertex类中设定邻接点的方法。除此之外，graph类还有一些重载的方法，比如重载contains，这个函数在类似于 3 in list(range(5)) 这样的语句中被调用，比如经常用的，判断某个元素是否在列表内等。重载迭代器__iter__，类似于 for item in list(range(10)): 这样的语句中被调用，有助于图中所有vertex的遍历。基于迭代器还可以重载字符串化方法__str__。
最后就是dijkstra算法。关于这个算法的信息准备记录在另一篇随笔中，基本思路是创建一个优先队列(即距离起始点路程从小到大的队列)，每次查看列表中路程最短的点a，观察在这个顶点a的邻接点中，是否有可能因为通过顶点a而使得该邻接点的路程缩减。每次这样一轮操作结束以后就从队列中删去这个点a，然后把队列重新排列一遍。在以前课上的学习中，优先队列使用的是二叉堆(binary heap)实现，在这里我直接调用了python内置的sort函数，虽然计算复杂度不敢保证，但是从后面用的实际例子的效率来说也没有任何影响。
1 classgraph:2 #无参数构造函数，vertex_dict为映射字典
3 def __init__(self):4 self.vertex_dict =dict()5 self.vertex_num =06
7 #增加顶点函数，传入新增顶点id
8 defadd_vertex(self, name):9 if name not inself.vertex_dict.keys():10 new_vertex =vertex(name)11 self.vertex_dict[name] =new_vertex12 self.vertex_num = self.vertex_num 1
13
14 #增加边函数， 传入顶点1名称、顶点2名称、权重
15 defadd_edge(self, vertex1, vertex2, weight):16 if vertex1 not inself.vertex_dict:17 self.add_vertex(vertex1)18 if vertex2 not inself.vertex_dict:19 self.add_vertex(vertex2)20 self.vertex_dict[vertex1].add_neighbour(self.vertex_dict[vertex2], weight)21 self.vertex_dict[vertex2].add_neighbour(self.vertex_dict[vertex1], weight)22
23 #按照id检索顶点函数，传入id，返回vertex类
24 defget_vertex(self, name):25 if name inself.vertex_dict.keys():26 returnself.vertex_dict[name]27 else:28 returnnone29
30 #重载contains方法，传入id，返回bool值
31 def __contains__(self, item):32 return item inself.vertex_dict33
34 #重载迭代器，返回对应迭代器
35 def __iter__(self):36 returniter(self.vertex_dict.values())37
38 #重载字符串化方法，返回字符串
39 def __str__(self):40 o_str =str()41 for item inself:42 o_str = o_str str(item) '\n'
43 returno_str44
45 #dijkstra算法，传入起点
46 defdijkstra_search(self, start):47 #优先队列priority
48 priority =list(self.vertex_dict.values())49 #起点距离置零
50 start.set_distance(0)51 #优先队列重排
52 priority.sort(key=lambda x: x.get_distance(), reverse=true)53 whilepriority:54 #重排标记changed，若存在顶点发生distance变化则标记为true
55 changed =false56 #弹出最高优先顶点current
57 current =priority.pop()58 #遍历current邻接顶点
59 for vertex_tmp incurrent.get_connections():60 dist_tmp = current.get_distance() current.get_weight(vertex_tmp)61 #若发现优势路径则更改邻接顶点的distance和前驱顶点pre
62 if dist_tmp
67 ifchanged:68 priority.sort(key=lambda x: x.get_distance(), reverse=true)
最后，和dijkstra算法配合还需要一个路径回溯的方法。本来把回溯作为图类的一个方法也可以，但是由于通过访问顶点的pre参数已经可以回溯到上一个vertex类，中间不涉及到图的操作，因此可以安全地把它写成一个静态方法的形式，即不放在graph类中：
1 #回溯路径函数，传入参数终点destination，返回路径列表list(vertex)
2 defreverse_trace(destination):3 current =destination4 trace =[destination]5 whilecurrent.get_pre():6 current =current.get_pre()7 trace.append(current)8 trace.reverse()9 return trace
这个函数返回的是一个路径中顺序出现的顶点vertex类列表。
作为图的一个练习和测试，我拿了北京市的地铁信息。首先我在某一个文件夹里新建了编号为line1到line10的10个.txt文件，录入了10条地铁线的信息。后来又新增了13号线和15号线的信息。这些txt里的信息是这样储存的：a)一行一个站名，表示起点站；b)一行一个站名 一个数字，表示一个站和前一站的距离；c)一行两个站名 一个数字，表示两个站之间的距离。然后可以写一个读入的函数，把这些信息读进来，每个站名就是一个id，形成一张图，选定一个起点s以后执行dijkstra算法，然后选定一个终点d回溯，就得到了从s到d的最短路径。
如果只是想得到站与站之间的最短距离，这个方法当然是合适的；不过，如果考虑到换乘因素，就会发现这个算法没有考虑到换乘的时间代价，这会使得搜索出一些需要换乘很多次的结果，而这在现实生活中并不是最快的。一个改进成本很小的方案是，把每个站所属的线路号码加在站名后面作为id的一部分，比如用“王府井1”作为一个id。同时，利用存储形式c来规定换乘站的间距，比如规定“海淀黄庄4”和“海淀黄庄10”的距离。这样一来就可以考虑换乘代价了。在这个思路下，graph类相应的读入函数：
1 classgraph:2 #读取顶点文件(适用于地铁路线例子的方法)，传入文件路径path和线路编号subway
3 defread_in(self, path, subway):4 with open(path, 'r') as file:5 #按行读取文件
6 line =file.readline()7 station =none8 whileline:9 info_list =line.split()10 #当行中仅含有1个元素时，仅创建
11 if len(info_list) == 1:12 station =info_list[0]13 station = station str(subway)14 self.add_vertex(station)15 #当行中含有2个元素时，第1个元素为车站名称，第2个元素为距上个车站距离
16 elif len(info_list) == 2:17 pre_station =station18 [station, distance] =info_list19 distance =int(distance)20 station = station str(subway)21 self.add_vertex(station)22 self.add_edge(pre_station, station, distance)23 #否则当行中含有3个元素，前2个元素为车站，第3个元素为前二者间距
24 else:25 [station1, station2, distance] =info_list26 distance =int(distance)27 self.add_edge(station1, station2, distance)28 line = file.readline()
最后是初始化函数和个人偏爱的交互式菜单代码，仅供参考：
1 #初始化函数(适用于地铁路线例子的方法)
2 #读入在file_path所示文件夹下的北京地铁线数据，返回生成的图
3 definitialize():4 graph =graph()5 file_path = 'd:\personal documents\project\beijingsubway\line'
6 for i in range(1, 11):7 path = file_path str(i) '.txt'
8 graph.read_in(path, i)9 path = file_path '13.txt'
10 graph.read_in(path, 13)11 path = file_path '15.txt'
12 graph.read_in(path, 15)13 returngraph14
15
16 #交互式菜单函数(适用于地铁路线例子的方法)，传入图
17 defroute_find_menu(graph):18 print('>> 寻找乘地铁最短路线，输入0退出')19 start = input('>> 输入起始站名 地铁线(如“王府井1”)：')20 while start != '0':21 graph.breadth_first_search(graph.get_vertex(start))22 destination = input('>> 输入终点站名 地铁线(如“王府井1”)：')23 if destination == '0':24 break
25 trace_list =reverse_trace(graph.get_vertex(destination))26 print([x.get_id() for x intrace_list])27 start = input('>> 输入起始站名：')
最后只要分别调用 graph1 = initialize() 创建实例，并且用 route_find_menu(graph1) 进入菜单即可。
总结
以上是凯发k8官方网为你收集整理的python无向加权图_图：无向图(graph)基本方法及dijkstra算法的实现 [python]的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇：
- 下一篇：