遍历应用之拯救007,python版本详细解析"/>
图的遍历应用之拯救007,python版本详细解析
题目
给定一张图,007在图的一个顶点(岛)上,如果想要逃生就要通过跳到鳄鱼的头上,最终跳到岸上逃生。
设鳄鱼池是长宽为100米的方形,中心坐标为 (0, 0),且东北角坐标为 (50, 50)。池心岛是以 (0, 0) 为圆心、直径15米的圆。
给定池中分布的鳄鱼的坐标、以及007一次能跳跃的最大距离,判断007是否能够逃生。
分析:
其实就是图的遍历问题,一直递归查找,直到找到边缘。与普通遍历不同的是顶点之间是否有边需要自行计算。
整个程序抽象出几个方法:
- createGraph 构建有N个顶点的图
- insertEdge 判断两个顶点之间是否有边,有边的条件是,两点之间的距离是否在007的跳跃范围之内
- dfs或bfs算法
开始实现(伪代码,如需完整代码请留言)
第一步,根据题意,我们可以提取出几个要素来设计数据对象:
顶点对象,至少具有2个属性值,分别是横坐标和纵坐标,因此可以得下列数据结构
class GNode():"""图顶点 """def __init__(self, x=None, y=None):# 图的每个节点self.x = xself.y = y
边对象,至少需要3个属性值,起始顶点和终止顶点,边的距离,边是否有向等
class ENode(ABC):"""边"""DIRECTED = Nonedef __init__(self):self.weight = None # 权重self.v1 = None # 顶点1self.v2 = None # 顶点2
有N个顶点的图,至少需要一个数据结构存储每个顶点的坐标值,顶点之间的连通关系,因此可以得出下列数据结构(矩阵实现)
class Graph():"""图"""def __init__(self):# 邻接矩阵,存储顶点之间边的关系# 如G[0][1]=-1 表示顶点0和顶点1之间不连同# 如G[0][1]=8 表示顶点0和顶点1之间连同,距离为8self.G = [[]] # 存储顶点数据集,每个元素是顶点GNode实例self.data = []
游戏,至少包含一张图,小岛的位置,小岛半径,007的跳跃距离
class GameSave007():"""拯救007游戏"""def __init__():self.graph = None # 存储图self.islandPos = None # 小岛起始位置self.islandRadius None # 小岛的半径self.jumpDist = None # 007跳跃的距离
第二步,我们需要创建游戏图,包括几个数据操作:创建空图、创建边、插入边等
首先我们需要创建具有N个顶点的,没有边的图,在Graph对象中加一个创建空图操作。
class Graph():... # 省略def createGraph(self, vertexs:list):"""初始化一个没有边的图vertexNum 顶点集,每个元素是一个顶点"""# 由于没有边,所有位置初始化为-1self.G = [[-1 for i in range(vertexNum)] for j in range(vertexNum)]self.data = [ v for v in vertexs] # 存储顶点的坐标return self
其次填充边,找到图所有的边,在Graph加找边操作、插入边、判断两个顶点是否存在边等操作
class Graph():... # 省略def insertEdge(self, e: ENode):"""插入一条边"""self.G[e.v1][e.v2] = e.weight # 默认V1指向V2if not e.DIRECTED: # 如果是无向图,还需要v2指向v1self.G[e.v2][e.v1] = e.weightdef isEdge(self, v1, v2, jumpDist) -> int:"""判断两个顶点是否有边-1 没有边,>0 权重"""v1 = self.data[v1] # 获取顶点的坐标值v2 = self.data[v2]xdist = abs(v2.x - v1.x)ydist = abs(v2.y - v1.y)if (xdist*xdist + ydist*ydist <= (jumpDist*jumpDist)): return int(math.sqrt(xdist*xdist + ydist*ydist))return -1def findEdge(self, jumpDist): """找出图的所有边"""for i, val in enumerate(self.G): for j, val in enumerate(self.G[i][i+1:]):j = i+1+jweight = self.isEdge(i, j, jumpDist)if weight == -1:continuee = UnDirENode()e.v1 = ie.v2 = je.weight = weightself.insertEdge(e)
第三步,写核心图遍历算法(DFS 深度优先搜索)
如果找到一个顶点,可以直接连通“岸边”,那么007就得救了。连通岸边的条件是 x+=jumpDist大于50或者x+=10大于50。
class Save007DFSVisit(IVisitGraph):def isSave(self, g, v) -> bool:"""判断当前顶点v能否跳到岸上,step=1g:图对象v: 顶点下标"""# 分析 岸边顶点为 (-50,?) (?, 50) (50, ?) (?, -50)v = g.data[v]if ((abs(v.x)+g.jumpDist)>=50 or (abs(v.y)+g.jumpDist>=50)):# 成功脱逃return Truereturn Falsedef visit(self, g:GNode, v: int):"""DFS 深度优先搜索g:图对象v: 顶点下标"""self.visited[v] = True # 跳到这个鳄鱼上面ans = "NO"if self.isSave(g, v):# 判断当前鳄鱼头能否直接跳到岸上ans = "YES"else:# 不能跳到岸上,继续找下一个鳄鱼头for i, val in enumerate(g.G[v]):if (g.G[v][i]>0 and not self.visited[i]): # 判断是否还有其他连通的、未访问的鳄鱼头ans = self.visit(g, i)if ans == "YES":breakreturn ans
最后一步:从小岛出发,遍历所有在跳跃范围内的鳄鱼头,对这个鳄鱼头进行DFS,直到找到连通图。
if abs(g.jumpDist+self.IslandDir) >= 50:print("拯救007成功")exit()for i, val in enumerate(g.data): # 遍历所有顶点,直到找到连通图if ((not v.visited[i]) and self.firstJump(g, i)):ans = c.doVisit(v, g, i)if ans == 'YES':breakprint("回到起点")if ans == "YES":print("拯救007成功")
else:print("拯救007失败,呜呜呜")
def firstJump(self, g, v) -> bool:"""第一跳:确定是否能从孤岛上跳到v"""# 当前起点(0,0)v = g.data[v]r = self.jumpDist+self.islandRadiusif ((r*r) >= (v.x*v.x + v.y*v.y)):return Truereturn False
最后总结:
整个程序非常简单,也非常有趣。
先设置游戏参数,如小岛起始位置,小岛半径,007的跳跃距离等;
然后创建图,鳄鱼,关键点是边的查找;
最后,从岛上开始逃生,关键操作是图的遍历;
通过这个小游戏,我们可以很好的锻炼了图的遍历,甚至你可以提高难度,找出最短逃生路径,也就是图的最短路径问题。
更多推荐
图的遍历应用之拯救007,python版本详细解析
发布评论