应用于Swift手游开发的广度优先搜索算法该语言实现了一些常用的算法和数据结构。每个月，SAC团队都会在www.raywenderlich.com网站上以教程的形式发布一个很酷的数据结构或算法。因此，如果你想深入了解Swift语言实现的算法和数据结构，可以随时关注本站。在本课程中，您将学习一种经典的搜索和寻路算法，称为广度优先搜索。广度优先搜索算法最初由ChrisPilcher(https://github.com/chris-pilcher)实现。在本教程中，我们将根据需要稍微重构其实现的格式方面。本教程假设您已经了解邻接表算法（https://www.raywenderlich.com/152046/swift-algorithm-club-graphs-adjacency-list）和队列算法（https://www.raywenderlich.com/148141/swift-algorithm-club-swift-queue-data-structure)，或具有类似的基础知识。注意，如果你对SwiftAlgorithmClub感兴趣并且是新手，可以访问这个地址https://www.raywenderlich.com/135533/join-swift-algorithm-club。入门在Swift图论邻接表算法（https://www.raywenderlich.com/152046/swift-algorithm-club-graphs-adjacency-list）中，我们提出了对图中每个对象的描述以及它们之间的关系他们的方法。在图中，每个对象表示为一个顶点，每个关系表示为一条边。例如，迷宫可以用图形来描述。迷宫中的每个路口都可以用顶点来描述，路口之间的每个通道都可以用边来描述。广度优先搜索是由E.F.Moore(https://en.wikipedia.org/wiki/Edward_F._Moore)在1950年发现的。这个算法不仅仅是在迷宫中寻找路径，而是寻找最短路径的算法迷宫中的路径。这种广度优先搜索算法背后的思想非常简单：搜索与来自某个源点的一组移动相对应的每个位置。然后，逐步修改此数字，直到找到目的地。下面我们来分析一个具体的例子。例如，假设你在迷宫的入口处，请参考下图。广度优先搜索算法的工作原理如下：1.搜索您的当前位置。如果这是目的地，则搜索停止。2.搜索您所在位置的邻居。如果其中任何一个是目的地，搜索就会停止。3.搜索这些位置的所有相邻点位置。如果其中任何一个是目的地，则搜索停止。4.***，如果有到目的地的路线，就说找到了一条路径，这条路径以从原点开始的最小移动步数存储。如果您已用完要搜索的位置，则没有通往目标的路径。【注】对于广度优先搜索算法，最短路径是指从一个位置到下一个位置的最少移动步数。在我们提供的迷宫示例中，广度优先搜索算法假设迷宫中房间之间的所有通道都具有相同的长度，当然这在实践中可能并非如此。您可以将穿过迷宫的最短路径视为最短方向的列表，而不是最短距离。在以后的教程中，我们将探索最短距离路径查找算法。Swift广度优先搜索算法下面我们来分析一下基于Swift语言的广度优先搜索算法。为此，请下载本教程的初始源代码（https://koenig-media.raywenderlich.com/uploads/2017/03/BreadthFirstSearch-Start.playground.zip），其中提供了邻接表和数据结构对于队列。【注意】如果想了解Swift语言实现的邻接表和队列的数据结构是如何工作的，可以使用命令View\Navigators\ShowProjectNavigator来分析相关代码。您还可以具体学习如何使用Swift语言构建这些邻接表和队列教程。首先，我们定义一个名为Graphable的协议；所有图形数据结构都必须符合该协议。然后我们扩展协议；这样，我们就可以将广度优先搜索应用于所有图类型。这是Graphable协议的样子：,weight:Double?)funcweight(fromsource:Vertex,todestination:Vertex)->Double?funcedges(fromsource:Vertex)->[Edge]?}最初在上面下载的示例项目的上半部分（在语句importXCPlayground之后），创建我们的扩展：extensionGraphable{publicfuncbreadthFirstSearch(fromsource:Vertex,todestination:Vertex)->[Edge]?{}}让我们总结这个函数签名：声明一个函数，它有两个顶点参数：第一个是源点，这是我们的起点；第二个是目的地点，也就是我们的目标。此函数以边对象的形式返回一条路线（从源到目的地）。如果路由存在，我们也希望它以有序的方式存储！路线中的第一条边将从源顶点开始，路线中的最后一条边将结束于目标顶点。对于路径中的每对相邻边，第一条边的目标点将与第二条边的源点相同。如果源点与目的点相同，则说明这条路线为空数组。如果路由不存在，函数应该返回nil。广度优先搜索依赖于以正确的顺序访问顶点。第一个访问的顶点总是对应于源点。之后，我们分析源点的邻居；然后，依此类推。每次我们访问一个顶点时，它的节点都会被添加到队列的后面。因为我们已经了解了队列的知识，所以这里可以直接使用！因此，我们可以将上述函数更新为以下内容：publicfuncbreadthFirstSearch(fromsource:Vertex,todestination:Vertex)->[Edge]?{varqueue=Queue>()queue.enqueue(source)//1whileletvisitedVertex=queue.dequeue(){//2ifvisitedVertex==destination{//3return[]}//TODO。..}returnil//4}接下来我们一步步分析上面的代码：1.首先创建一个顶点队列，将源点加入到队列中。2.从队列中取出一个顶点（只要队列不为空），并称其为已访问顶点。3.第一次迭代时，访问过的顶点为源，队列立即为空。但是，如果通过访问源节点添加了更多节点，搜索将继续。4.检查访问的顶点是否是目标顶点。如果是，搜索立即结束。在当前情况下，您将返回一个空列表——这与找到目标节点时相同。然后，将构建更详细的路线。5.如果队列中的顶点为空，则返回nil。这意味着没有找到目标节点；可能没有相对于它的路径。接下来，我们需要将访问节点的所有邻居节点添加到队列中。为此，您可以使用以下代码：letneighbourEdges=edges(from:visitedVertex)??[]//1foredgeinneighbourEdges{queue.enqueue(edge.destination)}//2让我们来做一个详细的分析：1.这里我们使用Graphable协议的edges(from:)函数获取被访问节点的边数组。请记住，edges(from:)函数返回一个可选的边数组。这意味着如果此数组为空或nil，则没有从该节点开始的边。因为（为了我们的搜索目的）一个空列表意味着与nil相同——没有邻居可以排队；因此，我们使用一个空列表来nil聚合可选数组，从而删除可选功能。2.现在，您可以安全地在边列表上迭代for循环，将每条边的目标节点排入队列。至此，我们的任务还没有完全完成。事实上，这个搜索算法有一个微妙的危险！如果您在此示例中运行搜索算法，会发生什么情况？在这里，我们可以忽略藏宝室与图上级没有联系的事实。让我们手工计算每次访问顶点时会发生什么。如果你运行这个例子中的搜索算法，你会遇到什么问题？答案如下：1.广度优先搜索算法会创建一个队列，将入口处的房间入队。2.当第一次进入while循环时，我们出队进入房间并访问它。玄关房间没有宝物，可以搜索玄关房间的所有相邻房间。进门房有隔壁房，蜘蛛房。因此，我们将其排队。3.第二次进入while循环时，我们将蜘蛛房出队，访问。因为蜘蛛房没有宝物，我们进一步搜索蜘蛛房的所有相邻房间。蜘蛛房有一个邻居房，入口房，所以我们将它入队。4.第三次进入while循环时，我们dequeue了入口房间...问题是：我们之前已经到过这个位置了！为了解决这个问题，我们需要记录我们访问过的顶点信息，以确保我们不会再次访问它们。有几种方法可以解决这个问题。您可以像这样更新代码：publicfuncbreadthFirstSearch(fromsource:Vertex,todestination:Vertex)->[Edge]?{varqueue=Queue>()queue.enqueue（来源)varenqueuedVertices=Set>()//1whileletvisitedVertex=queue.dequeue(){ifvisitedVertex==destination{return[]}letneighbourEdges=edges(from:visitedVertex)??[]foredgeinneighborEdges{if!enqueuedVertices.contains(edge.destination){//2enqueuedVertices.insert(visitedVertex)//3queue.enqueue(edge.destination)}}}returnnil}让我们回顾一下发生了什么变化：1.上面的代码将创建一个顶点数组，它描述了到目前为止您遇到的顶点列表。请记住，Vertex类型是Hashable，因此我们不需要做任何更多的工作来构建顶点集。2.每当检查相邻顶点时，首先检查之前是否遇到过该节点。3.如果之前没有遇到过该节点，则将其添加到两个队列中：要处理的顶点列表（队列结构）和遇到的顶点列表（enqueuedVertices）。这意味着，上述搜索算法是相当安全的。但是，现在您不能访问比开始时更多的图中的顶点，因此搜索最终必须终止。找到循环我们的算法就快完成了！到目前为止，您知道如果找不到目的地，您将返回一个nil值。但是，如果您找到了目的地，则需要找到返回的路。不幸的是，您访问的每个房间都已出队，没有留下如何找到目的地的记录！为了记录搜索信息，你需要用字典结构替换你搜索的顶点集，它需要包含你搜索过的所有顶点以及你如何到达那里的信息。把这想象成探索迷宫，使用带箭头的粉笔标记指向您探索过的所有房间-这样您就可以记住到达入口所需的所有信息。如果我们跟踪所有的箭头——对于我们访问过的任何房间，我们只能查找我们所遵循的到达它的边缘。这条边将通向我们之前访问过的房间。当然，我们也可以向上查找我们所遵循的边到达它，以此类推……直到最开始的边。让我们试试这个想法——创建以下Visit枚举类型。请注意，您必须在Graphable扩展之外创建此类型，因为Swift3不支持嵌套的泛型类型。enumVisit{casesourcecaseedge(Edge)}在我们的查找表中，***列中的每一项都是一个顶点，但第二列中的每一项并不总是一条边；顶点始终是源顶点；否则，就会出现严重错误，我们永远无法脱离图表！接下来，修改你的方法如下：)varvisits:[Vertex:Visit]=[source:.source]//1whileletvisitedVertex=queue.dequeue(){//TODO:Replacethis...ifvisitedVertex==destination{return[]}letneighborEdges=edges(from:visitedVertex)??[]foredgeinneighbourEdges{ifvisits[edge.destination]==nil{//2queue.enqueue(edge.destination)visits[edge.destination]=.edge(edge)//3}}}returnnil}让我们回顾一下上面的代码发生了什么变化：1.这创建了一个对应于Vertex键和Visit值的字典，并用源顶点作为来自“源点”的访问来初始化这个字典。2.如果字典中没有某个顶点对应的entry，说明这个顶点还没有加入队列。3.每当你入队一个顶点时，你不只是将它放入一个顶点集中，你还记录了相应的边可以到达它。***，您可以从目的地回溯到入口！并使用TODO注释中的实际代码更新if语句：ifvisitedVertex==destination{varvertex=destination//1varroute:[Edge]=[]//2whileletvisit=visits[vertex],case.edge(letedge)=visit{//3route=[edge]+routevertex=edge.source//4}returnroute//5}让我们分析一下上面的代码：1.首先创建一个New变量来存储属于路线一部分的每个顶点。2.同时创建一个变量来存储路线。3.创建一个while循环；只要访问字典有顶点条目并且只要该条目是边，循环就会继续。如果条目是源，则while循环将结束。4.将边添加到路线的起点并将顶点设置为边的源。现在，您离开始又近了一步。5.while循环结束；所以，你的路线现在也必须完成。至此，我们已经解决了所有的问题！可以在示例工程文件末尾添加如下代码进行测试：)")}}相应的，你应该在控制台观察到如下输出：Entrance->RatRat->Treasure基于Swift语言的广度优先搜索算法！在本教程中，我们扩展了所有Graphable数据类型的行为，因此您可以搜索从任何顶点到任何其他顶点的路径。更好的是，您得到的是步数最少的路线。您可以从URLhttps://koenig-media.raywenderlich.com/uploads/2017/03/BreadthFirstSearch-Final.playground.zip下载包含上述所有代码的修改示例项目源代码。您还可以在Swift算法俱乐部存储库中找到原始广度优先搜索算法的原始实现代码，并参与进一步的讨论。其实这个算法只是SwiftAlgorithmClub仓库的一小部分，有兴趣的读者可以进一步参考这些代码库（https://github.com/raywenderlich/swift-algorithm-club）。【翻译稿件，合作网站转载请注明原译者和出处.com】
