【51CTO.com快譯】Swift算法俱樂部(https://github.com/raywenderlich/swift-algorithm-club)是一個開放源碼項目，其目的是使用Swift語言實現一些常用的算法和數據結構。

在每個月份，SAC團隊都會在www.raywenderlich.com網站上以教程形式公布一個很酷的數據結構或算法。因此，如果您想要了解更多關于Swift語言實現的算法和數據結構，您可以一直關注這個網站。

在本教程中，你將學習一種經典的搜索和尋路算法，即廣度優先搜索算法。

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

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

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

入門

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

例如，可以用圖來描述一個迷宮。在迷宮中的每個接合點可以由一個頂點來描述，而接合點之間的每個通道可以使用邊來描述。

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

• 搜索圍繞從某一源點出發的一組移動對應的每一個位置。
• 然后，以增量步長方式修改這個數字，直到找到目的地。

下面，讓我們來分析一下具體的例子。

舉例

假設你是在一個迷宮的入口處，請參考下圖。

廣度優先搜索算法以如下方式工作︰

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

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

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

4.***，如果存在一條到達目的地的路線，則稱發現了一條通路，并以從原點出發的最少移動步數存儲起這條通道。如果你已經用完了要搜索的位置，則說明不存在一條到達目標的的通路。

【注】就廣度優先搜索算法而言，最短路線是指從一個位置到達下一個位置的最少移動步數。

在我們提供的迷宮例子中，廣度優先搜索算法認為迷宮中房間之間的所有通道都具有相同的長度，當然是實際中這可能不是真實的。你可以把通過迷宮的最短路線看作最短方向列表，而不是最短的距離。

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

Swift廣度優先搜索算法

從現在開始，讓我們具體分析一下基于Swift語言實現的廣度優先搜索算法。

為此，請先下載本教程的初始源碼(https://koenig-media.raywenderlich.com/uploads/2017/03/BreadthFirstSearch-Start.playground.zip)，其中提供了基于Swift語言實現的鄰接表和隊列的數據結構。

【注意】如果你想了解Swift語言實現的鄰接表和隊列的數據結構是如何工作的，你可以使用命令View\Navigators\ Show Project Navigator來分析有關代碼。您還可以具體學習如何使用Swift語言構建這些鄰接表和隊列教程。

首先，我們定義一個名為Graphable的協議;所有的圖形數據結構都要遵從該協議。然后，我們要擴展該協議;這樣一來，我們可以將廣度優先搜索應用于所有的圖類型中。

下面是Graphable協議看起來的樣子︰

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>]? 
}  

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

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

讓我們概括一下此函數簽名︰

• 其中聲明了一個函數，它接收兩個頂點參數：***個是源點，即我們的出發點;第二個是目標點，即我們的目標。此函數返回一條以邊對象形式組成的路線(從源點出發直到目標位置)。
• 如果路線存在，我們還指望它以排序方式存儲!路線中的***條邊將從源頂點開始，而路線中的***一條邊將以目標頂點終結。對于路線中的每一對相鄰邊，***條邊的目的點將與第二條邊的源點成為同一頂點。
• 如果源點與目的點是一樣的，則說明這條路線是一個空數組。
• 如果路線不存在，該函數應返回nil。

廣度優先搜索依賴于按正確的順序訪問的頂點。要訪問的***個頂點總是對應于源點。之后，我們會分析源點的鄰結點;然后，以此類推下去。我們每訪問一個頂點，便將其結點添加到隊列的后面。

因為我們此前已經了解了隊列知識，所以這里我們可以直接使用它!

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

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 
  
}  

下面，我們來逐步分析一下上面的代碼：

1. 首先，創建一個頂點隊列，并把源點加入隊列。

2. 從隊列中出列一個頂點(只要隊列非空)，并稱之為訪問頂點。

3. 在***迭代中，訪問頂點將是源點，而且隊列會立即為空。然而，如果訪問源結點添加更多的結點，則搜索會繼續進行下去。

4. 檢測是否訪問頂點是目標頂點。如果是，則立即結束搜索。目前情況下，你將返回一個空的列表——這與目標結點找到時是一樣的情況。然后，將構造一條更為細致的線路。

5. 如果隊列中頂點為空，則返回nil。這意味著，目標結點沒有找到;有可能不存在相對于它的一條通路。

接下來，我們需要把訪問結點的所有鄰居結點加入隊列中。為此，可以使用如下代碼：

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

再讓我們作細致的分析：

1.這里使用Graphable協議的edges(from:)函數來取得訪問結點的邊數組。記住，edges(from:)函數返回的是一個可選的邊數組。這意味著，如果此該數組為空，或者nil，則不存在以此結點開始的邊。

因為(為了我們的搜索目的)空表和nil意思一樣——沒有鄰結點可入隊列;所以，我們使用一個空列表來nil聚合可選數組，從而去掉可選功能。

2.現在，你可以在邊列表上安全地進行for循環迭代，從而把每一個邊的目標結點入隊列。

到此，我們的任務還沒有完全完成。事實上，在此搜索算法中還存在一處微妙的危險!如果你在此示例中運行搜索算法會遇到什么問題呢?在此，我們可以不考慮這樣一個事實，即寶物房間沒有關連到圖上。

我們不妨去手工方式推算一下每當我們訪問一個頂點時將會發生什么。

如果你在此示例中運行搜索算法會遇到什么問題呢?答案如下：

1. 寬度優先搜索算法將創建一個隊列，并把入口處房間入隊列。

2. 當***次進入到while循環時，我們把入口房間出隊列并訪問它。入口房間中不存在寶物，這樣我們可以搜索入口房間的所有鄰居房間。入口房間有一個鄰居房間，即蜘蛛房間。于是，我們把它入隊列。

3. 當第二次進入到while循環時，我們把蜘蛛房間出隊列并訪問它。因為蜘蛛房間中也沒有寶物，所以我們進一步搜索蜘蛛房間的所有鄰居房間。蜘蛛房間有一個鄰居房間，即入口房間，于是我們把它入隊列。

4. 當第三次進入到while循環時，我們把入口房間出隊列……

問題是：我們以前已經達到過這個位置了!

為了修正這個問題，我們需要記下我們曾經訪問過的頂點信息，以便我們確保不會第二次訪問它們。

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

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 
}  

讓我們回顧一下發生了什么變化︰

1.上面的代碼將創建一個頂點數組，用來描述到目前為止你遇到過的頂點的列表。請記住，Vertex類型是Hashable，所以我們不需要做任何更多的工作來構建一個頂點集。

2.每當檢查相鄰的頂點，都要首先檢查此前是否遇到過該結點。

3.如果你以前沒有遇到過該結點，則將它添加到兩個隊列中：要處理的頂點列表(隊列結構)和遇到的頂點列表(enqueuedVertices)。

這意味著，上面的搜索算法是相當安全的。但是，現在你還不能訪問比開始的那個圖中更多的頂點，因此搜索最終必須終止。

發現回路

我們的算法快要成功了!

到目前為止，你已經知道如果找不到目的地，你會返回一個nil值。但是，如果你找到了目的地，你需要找到你的往回走的線路。不幸的是，每個你訪問過的房間都已經出隊列了，對于如何找到目的地沒有留下任何記錄信息!

為了記錄下搜索信息，你需要使用一個字典結構來替換你搜索過的頂點集合，其中需要包含所有您搜索過的頂點信息和你如何到達該頂點的信息。我們不妨把這想像為探索一個迷宮，使用一個帶箭頭的粉筆標記指向所有你探索過的房間——通過這種方式來記憶下到達入口處的所有信息。

如果我們保持跟蹤所有的箭頭——針對我們訪問過的任何房間，我們只可以查找我們沿著到達它的邊緣。這個邊將引回到我們早些時候訪問過的房間。當然，我們也可以查找我們沿著到達它的邊，如此下去……直到開頭的那一條邊。

讓我們來試試這種想法——創建下面的Visit枚舉類型。注意，你必須在Graphable擴展的外部創建這個類型，因為Swift 3不支持嵌套泛型類型。

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

在我們的查詢表中，***列中的每個項都是一個頂點(Vertex)，但第二列中的每個項并不都是一條邊(Edge);一個頂點(Vertex)總是源頂點;否則，就會出現嚴重的錯誤，從而導致我們永遠走不出圖去!

接下來，按照如下所示修改您的方法︰

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 
}  

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

1. 這將創建一個對應于Vertex鍵和Visit值的字典，并使用源頂點作為從“源點”處的訪問來初始化這個字典。

2. 如果字典里沒有對應于某一個頂點的入口，那么說明此頂點還沒有加入隊列。

3. 每當你入隊一個頂點時，你并不只是把它放進一個頂點集合中，還要記錄下到達它對應的邊。

***，你可以從目標到入口進行回溯!并且使用TODO注釋處的實際代碼來更新if語句︰

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.首先創建一個新的變量，用來存儲作為路線的一部分的每個頂點。

2.還要創建一個變量來存儲路線。

3.創建一個while循環;只要訪問字典有一個頂點入口并且只要此入口是一條邊，則該循環將會繼續下去。如果該入口是一個源點，則該while循環將結束。

4.把邊添加到你的路線的開頭，并把頂點設置為該邊的源點。現在，你距離開始處更接近了一步。

5.while循環結束;所以，你的路線現在也必須完成。

[[185897]]

到此為止，我們解決了所有問題!你可以在示例工程文件的結束處加入如下代碼來進行測試：

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

相應地，你應當在控制臺上觀察到如下的輸出結果：

Entrance -> Rat 
 
Rat -> Treasure  

小結

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

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

你可以從網址https://koenig-media.raywenderlich.com/uploads/2017/03/BreadthFirstSearch-Final.playground.zip處下載包含所有上述代碼的改進的示例工程源碼。你也可以在Swift算法俱樂部存儲庫中找到原始廣度優先搜索算法的原始實現代碼并參與進一步討論。

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

【51CTO譯稿，合作站點轉載請注明原文譯者和出處為51CTO.com】