----用教授的方式学习。
目录
12.1图的最优化问题
我们下面研究另一种最优化问题。假设你有一个航空公司航线的价格列表,其中包括美国任意两个城市之间的航班价格。假设有3个城市A、B和C,从A出发经过B到达C的价格是从A到B的价格加上从B到C的价格。你可能会有以下几个问题:
·某两个城市之间最少的停留次数是多少?
· 某两个城市之间最便宜的飞机票价是多少?
· 某两个城市之间,如果停留次数不超过两次,那么最便宜的飞机票价是多少?
· 如果想访问多个城市,那么最便宜的路线是什么?
所有这些问题(以及许多其他问题)都可以轻松转化为图的问题。
图是由边连接起来的节点对象的集合,边也可称为弧,节点也可称为顶点。如果边是单向的,则图称为有向图。在有向图中,从节点n1到n2有一条边,我们就称n1为源节点或父节点,n2为目标节点或子节点。
以下定义了几个类,分别实现了对应于节点、加权边和普通边的抽象类型。
class Node(object):
def __init__(self, name):
"""假设name是字符串"""
self.name = name
def getName(self):
return self.name
def __str__(self):
return self.name
class Edge(object):
def __init__(self, src, dest):
"""假设src和dest是节点"""
self.src = src
self.dest = dest
def getSource(self):
return self.src
def getDestination(self):
return self.dest
def __str__(self):
return self.src.getName() + '->' + self.dest.getName()
class WeightedEdge(Edge):
def __init__(self, src,
标签:__,src,12,第三册,self,dest,Python,节点,def
From: https://blog.csdn.net/weixin_38135241/article/details/139802480