本文是對 Swift Algorithm Club 翻譯的一篇文章。
Swift Algorithm Club是 raywenderlich.com網站出品的用Swift實現(xiàn)算法和數(shù)據結構的開源項目，目前在GitHub上有18000+??，我初略統(tǒng)計了一下，大概有一百左右個的算法和數(shù)據結構，基本上常見的都包含了，是iOSer學習算法和數(shù)據結構不錯的資源。
??andyRon/swift-algorithm-club-cn是我對Swift Algorithm Club，邊學習邊翻譯的項目。由于能力有限，如發(fā)現(xiàn)錯誤或翻譯不妥，請指正，歡迎pull request。也歡迎有興趣、有時間的小伙伴一起參與翻譯和學習??。當然也歡迎加??，??????????。
本文的翻譯原文和代碼可以查看??swift-algorithm-club-cn/Shortest Path(Unweighted)

最短路徑算法（Shortest Path(Unweighted Graph)）

目標：找到圖中從一個節(jié)點到另一個節(jié)點的最短路徑。

假設我們以下圖為例：

Example graph

我們可能想知道從節(jié)點A到節(jié)點F的最短路徑是什么。

如果圖是未加權的，那么找到最短路徑很容易：我們可以使用廣度優(yōu)先搜索算法。 對于加權圖，我們可以使用Dijkstra算法。

未加權圖：廣度優(yōu)先搜索

廣度優(yōu)先搜索是遍歷樹或圖數(shù)據結構的方法。 它從源節(jié)點開始，在移動到下一級鄰居之前首先探索直接鄰居節(jié)點。 方便的副作用是，它會自動計算源節(jié)點與樹或圖中其他每個節(jié)點之間的最短路徑。

廣度優(yōu)先搜索的結果可以用樹表示：

The BFS tree

樹的根節(jié)點是廣度優(yōu)先搜索開始的節(jié)點。 為了找到從節(jié)點A到任何其他節(jié)點的距離，我們只計算樹中邊的數(shù)目。 所以我們發(fā)現(xiàn)A和F之間的最短路徑是2.樹不僅告訴你路徑有多長，而且還告訴你如何實際從A到F（或者任何一個其他節(jié)點）。

讓我們將廣度優(yōu)先搜索付諸實踐，并計算從A到所有其他節(jié)點的最短路徑。 我們從源節(jié)點A開始，并將其添加到隊列中，距離為0。

queue.enqueue(element: A)
A.distance = 0

隊列現(xiàn)在是[A]。 我們將A出列并將其兩個直接鄰居節(jié)點B和C入列，并設置距離1。

queue.dequeue()   // A
queue.enqueue(element: B)
B.distance = A.distance + 1   // result: 1
queue.enqueue(element: C)
C.distance = A.distance + 1   // result: 1

隊列現(xiàn)在是[B, C]。 將B出列，并將B的鄰居節(jié)點D和E入列，距離為2。

queue.dequeue()   // B
queue.enqueue(element: D)
D.distance = B.distance + 1   // result: 2
queue.enqueue(element: E)
E.distance = B.distance + 1   // result: 2

隊列現(xiàn)在是[C, D, E]。 將C出列并將C的鄰居節(jié)點F和G入隊，距離為2。

queue.dequeue()   // C
queue.enqueue(element: F)
F.distance = C.distance + 1   // result: 2
queue.enqueue(element: G)
G.distance = C.distance + 1   // result: 2

這么一直持續(xù)到隊列為空，同時我們訪問了所有節(jié)點。 每次我們發(fā)現(xiàn)一個新節(jié)點時，它會獲得其父節(jié)點的distance加1.正如您所看到的，這正是廣度優(yōu)先搜索算法的作用， 除此之外，我們現(xiàn)在還知道距離尋找的路徑。

這是代碼：

func breadthFirstSearchShortestPath(graph: Graph, source: Node) -> Graph {
  let shortestPathGraph = graph.duplicate()

  var queue = Queue<Node>()
  let sourceInShortestPathsGraph = shortestPathGraph.findNodeWithLabel(label: source.label)
  queue.enqueue(element: sourceInShortestPathsGraph)
  sourceInShortestPathsGraph.distance = 0

  while let current = queue.dequeue() {
    for edge in current.neighbors {
      let neighborNode = edge.neighbor
      if !neighborNode.hasDistance {
        queue.enqueue(element: neighborNode)
        neighborNode.distance = current.distance! + 1
      }
    }
  }

  return shortestPathGraph
}

在playground中進行測試：

let shortestPathGraph = breadthFirstSearchShortestPath(graph: graph, source: nodeA)
print(shortestPathGraph.nodes)

輸出結果：

Node(label: a, distance: 0), Node(label: b, distance: 1), Node(label: c, distance: 1),
Node(label: d, distance: 2), Node(label: e, distance: 2), Node(label: f, distance: 2),
Node(label: g, distance: 2), Node(label: h, distance: 3)

注意：這個版本的breadthFirstSearchShortestPath()實際上并不生成樹，它只計算距離。 有關如何通過去除邊緣將圖轉換為樹，請參見最小生成樹。

作者：Chris Pilcher，Matthijs Hollemans
翻譯：Andy Ron
校對：Andy Ron