【51CTO.com快譯】Swift算法俱樂(lè)部(https://github.com/raywenderlich/swift-algorithm-club)是一個(gè)開(kāi)放源碼項(xiàng)目，其目的是使用Swift語(yǔ)言實(shí)現(xiàn)一些常用的算法和數(shù)據(jù)結(jié)構(gòu)。

在每個(gè)月份，SAC團(tuán)隊(duì)都會(huì)在www.raywenderlich.com網(wǎng)站上以教程形式公布一個(gè)很酷的數(shù)據(jù)結(jié)構(gòu)或算法。因此，如果您想要了解更多關(guān)于Swift語(yǔ)言實(shí)現(xiàn)的算法和數(shù)據(jù)結(jié)構(gòu)，您可以一直關(guān)注這個(gè)網(wǎng)站。

在本教程中，你將學(xué)習(xí)一種經(jīng)典的搜索和尋路算法，即廣度優(yōu)先搜索算法。

廣度優(yōu)先搜索算法最初是由克里斯·皮爾策(Chris Pilcher，https://github.com/chris-pilcher)實(shí)現(xiàn)的。在本教程中，我們將根據(jù)需要對(duì)其實(shí)現(xiàn)格式方面稍加重構(gòu)。

本教程假定您已經(jīng)了解基于Swift語(yǔ)言實(shí)現(xiàn)的圖論中的鄰接表算法(https://www.raywenderlich.com/152046/swift-algorithm-club-graphs-adjacency-list)和隊(duì)列算法(https://www.raywenderlich.com/148141/swift-algorithm-club-swift-queue-data-structure)，或具有相類似的基礎(chǔ)知識(shí)。

注意，如果您對(duì)Swift算法俱樂(lè)部感興趣并且是新手，您可以訪問(wèn)這個(gè)地址https://www.raywenderlich.com/135533/join-swift-algorithm-club。

入門(mén)

在Swift圖論鄰接表算法(https://www.raywenderlich.com/152046/swift-algorithm-club-graphs-adjacency-list)中，我們提出了一種描述圖中的各對(duì)象及其間關(guān)系的方法。在一個(gè)圖中，每個(gè)對(duì)象表示為一個(gè)頂點(diǎn)，而每個(gè)關(guān)系表示為一條邊。

例如，可以用圖來(lái)描述一個(gè)迷宮。在迷宮中的每個(gè)接合點(diǎn)可以由一個(gè)頂點(diǎn)來(lái)描述，而接合點(diǎn)之間的每個(gè)通道可以使用邊來(lái)描述。

廣度優(yōu)先搜索是在1950年被E. F. Moore(https://en.wikipedia.org/wiki/Edward_F._Moore)發(fā)現(xiàn)的，這種算法并不只是為了尋找一條穿過(guò)迷宮的通路，而是為了尋找穿越迷宮的最短路徑的算法。此廣度優(yōu)先搜索算法背后的想法倒是很簡(jiǎn)單的︰

• 搜索圍繞從某一源點(diǎn)出發(fā)的一組移動(dòng)對(duì)應(yīng)的每一個(gè)位置。
• 然后，以增量步長(zhǎng)方式修改這個(gè)數(shù)字，直到找到目的地。

下面，讓我們來(lái)分析一下具體的例子。

舉例

假設(shè)你是在一個(gè)迷宮的入口處，請(qǐng)參考下圖。

廣度優(yōu)先搜索算法以如下方式工作︰

1. 搜索你的當(dāng)前位置。如果這是目的地，則停止搜索。

2.搜索您所在位置的鄰點(diǎn)位置。如果其中任何之一是目的地，則停止搜索。

3.搜索這些位置的所有鄰接點(diǎn)位置。如果任何其中之一是目的地，則停止搜索。

4.***，如果存在一條到達(dá)目的地的路線，則稱發(fā)現(xiàn)了一條通路，并以從原點(diǎn)出發(fā)的最少移動(dòng)步數(shù)存儲(chǔ)起這條通道。如果你已經(jīng)用完了要搜索的位置，則說(shuō)明不存在一條到達(dá)目標(biāo)的的通路。

【注】就廣度優(yōu)先搜索算法而言，最短路線是指從一個(gè)位置到達(dá)下一個(gè)位置的最少移動(dòng)步數(shù)。

在我們提供的迷宮例子中，廣度優(yōu)先搜索算法認(rèn)為迷宮中房間之間的所有通道都具有相同的長(zhǎng)度，當(dāng)然是實(shí)際中這可能不是真實(shí)的。你可以把通過(guò)迷宮的最短路線看作最短方向列表，而不是最短的距離。

在未來(lái)的教程中，我們將探索最短距離的路徑尋找算法。

Swift廣度優(yōu)先搜索算法

從現(xiàn)在開(kāi)始，讓我們具體分析一下基于Swift語(yǔ)言實(shí)現(xiàn)的廣度優(yōu)先搜索算法。

為此，請(qǐng)先下載本教程的初始源碼(https://koenig-media.raywenderlich.com/uploads/2017/03/BreadthFirstSearch-Start.playground.zip)，其中提供了基于Swift語(yǔ)言實(shí)現(xiàn)的鄰接表和隊(duì)列的數(shù)據(jù)結(jié)構(gòu)。

【注意】如果你想了解Swift語(yǔ)言實(shí)現(xiàn)的鄰接表和隊(duì)列的數(shù)據(jù)結(jié)構(gòu)是如何工作的，你可以使用命令View\Navigators\ Show Project Navigator來(lái)分析有關(guān)代碼。您還可以具體學(xué)習(xí)如何使用Swift語(yǔ)言構(gòu)建這些鄰接表和隊(duì)列教程。

首先，我們定義一個(gè)名為Graphable的協(xié)議;所有的圖形數(shù)據(jù)結(jié)構(gòu)都要遵從該協(xié)議。然后，我們要擴(kuò)展該協(xié)議;這樣一來(lái)，我們可以將廣度優(yōu)先搜索應(yīng)用于所有的圖類型中。

下面是Graphable協(xié)議看起來(lái)的樣子︰

public protocol Graphable { 
  associatedtype Element: Hashable 
  var description: CustomStringConvertible { get } 
  
  func createVertex(data: Element) -> Vertex<Element> 
  func add(_ type: EdgeType, from source: Vertex<Element>, to destination: Vertex<Element>, weight: Double?) 
  func weight(from source: Vertex<Element>, to destination: Vertex<Element>) -> Double? 
  func edges(from source: Vertex<Element>) -> [Edge<Element>]? 
}  

在上面下載的初始示例工程的較靠上的位置(在語(yǔ)句 import XCPlayground的后面即可)，創(chuàng)建我們的擴(kuò)展：

extension Graphable { 
  public func breadthFirstSearch(from source: Vertex<Element>, to destination: Vertex<Element>)  
  -> [Edge<Element>]? { 
  
  } 
}  

讓我們概括一下此函數(shù)簽名︰

• 其中聲明了一個(gè)函數(shù)，它接收兩個(gè)頂點(diǎn)參數(shù)：***個(gè)是源點(diǎn)，即我們的出發(fā)點(diǎn);第二個(gè)是目標(biāo)點(diǎn)，即我們的目標(biāo)。此函數(shù)返回一條以邊對(duì)象形式組成的路線(從源點(diǎn)出發(fā)直到目標(biāo)位置)。
• 如果路線存在，我們還指望它以排序方式存儲(chǔ)!路線中的***條邊將從源頂點(diǎn)開(kāi)始，而路線中的***一條邊將以目標(biāo)頂點(diǎn)終結(jié)。對(duì)于路線中的每一對(duì)相鄰邊，***條邊的目的點(diǎn)將與第二條邊的源點(diǎn)成為同一頂點(diǎn)。
• 如果源點(diǎn)與目的點(diǎn)是一樣的，則說(shuō)明這條路線是一個(gè)空數(shù)組。
• 如果路線不存在，該函數(shù)應(yīng)返回nil。

廣度優(yōu)先搜索依賴于按正確的順序訪問(wèn)的頂點(diǎn)。要訪問(wèn)的***個(gè)頂點(diǎn)總是對(duì)應(yīng)于源點(diǎn)。之后，我們會(huì)分析源點(diǎn)的鄰結(jié)點(diǎn);然后，以此類推下去。我們每訪問(wèn)一個(gè)頂點(diǎn)，便將其結(jié)點(diǎn)添加到隊(duì)列的后面。

因?yàn)槲覀兇饲耙呀?jīng)了解了隊(duì)列知識(shí)，所以這里我們可以直接使用它!

于是，我們可以把上面的函數(shù)更新成下面這樣︰

public func breadthFirstSearch(from source: Vertex<Element>, to destination: Vertex<Element>)  
 -> [Edge<Element>]? { 
  
 var queue = Queue<Vertex<Element>>() 
  queue.enqueue(source) // 1 
  
  while let visitedVertex = queue.dequeue() { // 2 
    if visitedVertex == destination { // 3 
      return [] 
    } 
    // TODO... 
  } 
  return nil // 4 
  
}  

下面，我們來(lái)逐步分析一下上面的代碼：

1. 首先，創(chuàng)建一個(gè)頂點(diǎn)隊(duì)列，并把源點(diǎn)加入隊(duì)列。

2. 從隊(duì)列中出列一個(gè)頂點(diǎn)(只要隊(duì)列非空)，并稱之為訪問(wèn)頂點(diǎn)。

3. 在***迭代中，訪問(wèn)頂點(diǎn)將是源點(diǎn)，而且隊(duì)列會(huì)立即為空。然而，如果訪問(wèn)源結(jié)點(diǎn)添加更多的結(jié)點(diǎn)，則搜索會(huì)繼續(xù)進(jìn)行下去。

4. 檢測(cè)是否訪問(wèn)頂點(diǎn)是目標(biāo)頂點(diǎn)。如果是，則立即結(jié)束搜索。目前情況下，你將返回一個(gè)空的列表——這與目標(biāo)結(jié)點(diǎn)找到時(shí)是一樣的情況。然后，將構(gòu)造一條更為細(xì)致的線路。

5. 如果隊(duì)列中頂點(diǎn)為空，則返回nil。這意味著，目標(biāo)結(jié)點(diǎn)沒(méi)有找到;有可能不存在相對(duì)于它的一條通路。

接下來(lái)，我們需要把訪問(wèn)結(jié)點(diǎn)的所有鄰居結(jié)點(diǎn)加入隊(duì)列中。為此，可以使用如下代碼：

let neighbourEdges = edges(from: visitedVertex) ?? [] // 1 
for edge in neighbourEdges { 
  queue.enqueue(edge.destination) 
} // 2  

再讓我們作細(xì)致的分析：

1.這里使用Graphable協(xié)議的edges(from:)函數(shù)來(lái)取得訪問(wèn)結(jié)點(diǎn)的邊數(shù)組。記住，edges(from:)函數(shù)返回的是一個(gè)可選的邊數(shù)組。這意味著，如果此該數(shù)組為空，或者nil，則不存在以此結(jié)點(diǎn)開(kāi)始的邊。

因?yàn)?為了我們的搜索目的)空表和nil意思一樣——沒(méi)有鄰結(jié)點(diǎn)可入隊(duì)列;所以，我們使用一個(gè)空列表來(lái)nil聚合可選數(shù)組，從而去掉可選功能。

2.現(xiàn)在，你可以在邊列表上安全地進(jìn)行for循環(huán)迭代，從而把每一個(gè)邊的目標(biāo)結(jié)點(diǎn)入隊(duì)列。

到此，我們的任務(wù)還沒(méi)有完全完成。事實(shí)上，在此搜索算法中還存在一處微妙的危險(xiǎn)!如果你在此示例中運(yùn)行搜索算法會(huì)遇到什么問(wèn)題呢?在此，我們可以不考慮這樣一個(gè)事實(shí)，即寶物房間沒(méi)有關(guān)連到圖上。

我們不妨去手工方式推算一下每當(dāng)我們?cè)L問(wèn)一個(gè)頂點(diǎn)時(shí)將會(huì)發(fā)生什么。

如果你在此示例中運(yùn)行搜索算法會(huì)遇到什么問(wèn)題呢?答案如下：

1. 寬度優(yōu)先搜索算法將創(chuàng)建一個(gè)隊(duì)列，并把入口處房間入隊(duì)列。

2. 當(dāng)***次進(jìn)入到while循環(huán)時(shí)，我們把入口房間出隊(duì)列并訪問(wèn)它。入口房間中不存在寶物，這樣我們可以搜索入口房間的所有鄰居房間。入口房間有一個(gè)鄰居房間，即蜘蛛房間。于是，我們把它入隊(duì)列。

3. 當(dāng)?shù)诙芜M(jìn)入到while循環(huán)時(shí)，我們把蜘蛛房間出隊(duì)列并訪問(wèn)它。因?yàn)橹┲敕块g中也沒(méi)有寶物，所以我們進(jìn)一步搜索蜘蛛房間的所有鄰居房間。蜘蛛房間有一個(gè)鄰居房間，即入口房間，于是我們把它入隊(duì)列。

4. 當(dāng)?shù)谌芜M(jìn)入到while循環(huán)時(shí)，我們把入口房間出隊(duì)列……

問(wèn)題是：我們以前已經(jīng)達(dá)到過(guò)這個(gè)位置了!

為了修正這個(gè)問(wèn)題，我們需要記下我們?cè)?jīng)訪問(wèn)過(guò)的頂點(diǎn)信息，以便我們確保不會(huì)第二次訪問(wèn)它們。

有好幾種辦法可以解決這個(gè)問(wèn)題。你可以像如下這樣更新你的代碼：

public func breadthFirstSearch(from source: Vertex<Element>, to destination: Vertex<Element>) -> [Edge<Element>]? { 
  var queue = Queue<Vertex<Element>>() 
  queue.enqueue(source) 
  var enqueuedVertices = Set<Vertex<Element>>() // 1 
  
  while let visitedVertex = queue.dequeue() { 
    if visitedVertex == destination { 
      return [] 
    } 
   let neighbourEdges = edges(from: visitedVertex) ?? [] 
    for edge in neighbourEdges { 
      if !enqueuedVertices.contains(edge.destination) { // 2 
        enqueuedVertices.insert(visitedVertex) // 3 
        queue.enqueue(edge.destination) 
      } 
    } 
  } 
  return nil 
}  

讓我們回顧一下發(fā)生了什么變化︰

1.上面的代碼將創(chuàng)建一個(gè)頂點(diǎn)數(shù)組，用來(lái)描述到目前為止你遇到過(guò)的頂點(diǎn)的列表。請(qǐng)記住，Vertex類型是Hashable，所以我們不需要做任何更多的工作來(lái)構(gòu)建一個(gè)頂點(diǎn)集。

2.每當(dāng)檢查相鄰的頂點(diǎn)，都要首先檢查此前是否遇到過(guò)該結(jié)點(diǎn)。

3.如果你以前沒(méi)有遇到過(guò)該結(jié)點(diǎn)，則將它添加到兩個(gè)隊(duì)列中：要處理的頂點(diǎn)列表(隊(duì)列結(jié)構(gòu))和遇到的頂點(diǎn)列表(enqueuedVertices)。

這意味著，上面的搜索算法是相當(dāng)安全的。但是，現(xiàn)在你還不能訪問(wèn)比開(kāi)始的那個(gè)圖中更多的頂點(diǎn)，因此搜索最終必須終止。

發(fā)現(xiàn)回路

我們的算法快要成功了!

到目前為止，你已經(jīng)知道如果找不到目的地，你會(huì)返回一個(gè)nil值。但是，如果你找到了目的地，你需要找到你的往回走的線路。不幸的是，每個(gè)你訪問(wèn)過(guò)的房間都已經(jīng)出隊(duì)列了，對(duì)于如何找到目的地沒(méi)有留下任何記錄信息!

為了記錄下搜索信息，你需要使用一個(gè)字典結(jié)構(gòu)來(lái)替換你搜索過(guò)的頂點(diǎn)集合，其中需要包含所有您搜索過(guò)的頂點(diǎn)信息和你如何到達(dá)該頂點(diǎn)的信息。我們不妨把這想像為探索一個(gè)迷宮，使用一個(gè)帶箭頭的粉筆標(biāo)記指向所有你探索過(guò)的房間——通過(guò)這種方式來(lái)記憶下到達(dá)入口處的所有信息。

如果我們保持跟蹤所有的箭頭——針對(duì)我們?cè)L問(wèn)過(guò)的任何房間，我們只可以查找我們沿著到達(dá)它的邊緣。這個(gè)邊將引回到我們?cè)缧r(shí)候訪問(wèn)過(guò)的房間。當(dāng)然，我們也可以查找我們沿著到達(dá)它的邊，如此下去……直到開(kāi)頭的那一條邊。

讓我們來(lái)試試這種想法——創(chuàng)建下面的Visit枚舉類型。注意，你必須在Graphable擴(kuò)展的外部創(chuàng)建這個(gè)類型，因?yàn)镾wift 3不支持嵌套泛型類型。

enum Visit<Element: Hashable> { 
  case source 
  case edge(Edge<Element>) 
}  

在我們的查詢表中，***列中的每個(gè)項(xiàng)都是一個(gè)頂點(diǎn)(Vertex)，但第二列中的每個(gè)項(xiàng)并不都是一條邊(Edge);一個(gè)頂點(diǎn)(Vertex)總是源頂點(diǎn);否則，就會(huì)出現(xiàn)嚴(yán)重的錯(cuò)誤，從而導(dǎo)致我們永遠(yuǎn)走不出圖去!

接下來(lái)，按照如下所示修改您的方法︰

public func breadthFirstSearch(from source: Vertex<Element>, to destination: Vertex<Element>) -> [Edge<Element>]? { 
  var queue = Queue<Vertex<Element>>() 
  queue.enqueue(source) 
  var visits : [Vertex<Element> : Visit<Element>] = [source: .source] // 1 
  
  while let visitedVertex = queue.dequeue() { 
    // TODO: Replace this... 
    if visitedVertex == destination { 
     return [] 
    } 
    let neighbourEdges = edges(from: visitedVertex) ?? [] 
    for edge in neighbourEdges { 
      if visits[edge.destination] == nil { // 2 
        queue.enqueue(edge.destination) 
        visits[edge.destination] = .edge(edge) // 3 
      } 
    } 
  } 
  return nil 
}  

讓我們回顧一下上面的代碼中發(fā)生了什么變化︰

1. 這將創(chuàng)建一個(gè)對(duì)應(yīng)于Vertex鍵和Visit值的字典，并使用源頂點(diǎn)作為從“源點(diǎn)”處的訪問(wèn)來(lái)初始化這個(gè)字典。

2. 如果字典里沒(méi)有對(duì)應(yīng)于某一個(gè)頂點(diǎn)的入口，那么說(shuō)明此頂點(diǎn)還沒(méi)有加入隊(duì)列。

3. 每當(dāng)你入隊(duì)一個(gè)頂點(diǎn)時(shí)，你并不只是把它放進(jìn)一個(gè)頂點(diǎn)集合中，還要記錄下到達(dá)它對(duì)應(yīng)的邊。

***，你可以從目標(biāo)到入口進(jìn)行回溯!并且使用TODO注釋處的實(shí)際代碼來(lái)更新if語(yǔ)句︰

if visitedVertex == destination { 
  var vertex = destination // 1 
  var route : [Edge<Element>] = [] // 2 
  
  while let visit = visits[vertex], 
    case .edge(let edge) = visit { // 3 
  
    route = [edge] + route 
    vertex = edge.source // 4 
  
  } 
  return route // 5 
}  

讓我們分析一下上面的代碼︰

1.首先創(chuàng)建一個(gè)新的變量，用來(lái)存儲(chǔ)作為路線的一部分的每個(gè)頂點(diǎn)。

2.還要?jiǎng)?chuàng)建一個(gè)變量來(lái)存儲(chǔ)路線。

3.創(chuàng)建一個(gè)while循環(huán);只要訪問(wèn)字典有一個(gè)頂點(diǎn)入口并且只要此入口是一條邊，則該循環(huán)將會(huì)繼續(xù)下去。如果該入口是一個(gè)源點(diǎn)，則該while循環(huán)將結(jié)束。

4.把邊添加到你的路線的開(kāi)頭，并把頂點(diǎn)設(shè)置為該邊的源點(diǎn)。現(xiàn)在，你距離開(kāi)始處更接近了一步。

5.while循環(huán)結(jié)束;所以，你的路線現(xiàn)在也必須完成。

[[185897]]

到此為止，我們解決了所有問(wèn)題!你可以在示例工程文件的結(jié)束處加入如下代碼來(lái)進(jìn)行測(cè)試：

if let edges = dungeon.breadthFirstSearch(from: entranceRoom, to: treasureRoom) { 
  for edge in edges { 
    print("\(edge.source) -> \(edge.destination)") 
  } 
}  

相應(yīng)地，你應(yīng)當(dāng)在控制臺(tái)上觀察到如下的輸出結(jié)果：

Entrance -> Rat 
 
Rat -> Treasure  

小結(jié)

我真心希望廣大讀者朋友能夠喜歡本教程提供的基于Swift語(yǔ)言的廣度優(yōu)先搜索算法!

在本教程中，我們已經(jīng)擴(kuò)展了所有Graphable數(shù)據(jù)類型的行為，所以您可以搜索從任一頂點(diǎn)到任何其他頂點(diǎn)的路線。更妙的是，你得到的是一條擁有最少步數(shù)的路線。

你可以從網(wǎng)址https://koenig-media.raywenderlich.com/uploads/2017/03/BreadthFirstSearch-Final.playground.zip處下載包含所有上述代碼的改進(jìn)的示例工程源碼。你也可以在Swift算法俱樂(lè)部存儲(chǔ)庫(kù)中找到原始廣度優(yōu)先搜索算法的原始實(shí)現(xiàn)代碼并參與進(jìn)一步討論。

事實(shí)上，這個(gè)算法僅僅是Swift算法俱樂(lè)部存儲(chǔ)庫(kù)中的一個(gè)小部分，感興趣的讀者可以進(jìn)一步查閱這些代碼庫(kù)(https://github.com/raywenderlich/swift-algorithm-club)。

【51CTO譯稿，合作站點(diǎn)轉(zhuǎn)載請(qǐng)注明原文譯者和出處為51CTO.com】