图的遍历应用之拯救007，python版本详细解析

编程入门行业动态更新时间:2024-10-27 12:34:13

图的<a href=https://www.elefans.com/category/jswz/34/1771029.html style= 遍历应用之拯救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