# Breadth-first search 算法（Swift版）

## Graph

• 节点， 使用圆圈表示的部分
• 边， 使用线表示的地方，通常都是有方向的线

• 需要找到某条路径
• 需要找到到达某个节点的最短路径

```Graph.swift

// MARK: - Edge

public class Edge: Equatable {
public var neighbor: Node

public init(neighbor: Node) {
self.neighbor = neighbor
}
}

public func == (lhs: Edge, rhs: Edge) -> Bool {
return lhs.neighbor == rhs.neighbor
}

// MARK: - Node

public class Node: CustomStringConvertible, Equatable {
public var neighbors: [Edge]

public private(set) var label: String
public var distance: Int?
public var visited: Bool

public init(label: String) {
self.label = label
neighbors = []
visited = false
}

public var description: String {
if let distance = distance {
return "Node(label: (label), distance: (distance))"
}
return "Node(label: (label), distance: infinity)"
}

public var hasDistance: Bool {
return distance != nil
}

public func remove(edge: Edge) {
neighbors.remove(at: neighbors.index { \$0 === edge }!)
}
}

public func == (lhs: Node, rhs: Node) -> Bool {
return lhs.label == rhs.label && lhs.neighbors == rhs.neighbors
}

// MARK: - Graph

public class Graph: CustomStringConvertible, Equatable {
public private(set) var nodes: [Node]

public init() {
self.nodes = []
}

public func addNode(_ label: String) -> Node {
let node = Node(label: label)
nodes.append(node)
return node
}

public func addEdge(_ source: Node, neighbor: Node) {
let edge = Edge(neighbor: neighbor)
source.neighbors.append(edge)
}

public var description: String {
var description = ""

for node in nodes {
if !node.neighbors.isEmpty {
description += "[node: (node.label) edges: (node.neighbors.map { \$0.neighbor.label})]"
}
}
return description
}

public func findNodeWithLabel(_ label: String) -> Node {
return nodes.filter { \$0.label == label }.first!
}

public func duplicate() -> Graph {
let duplicated = Graph()

for node in nodes {
}

for node in nodes {
for edge in node.neighbors {
let source = duplicated.findNodeWithLabel(node.label)
let neighbour = duplicated.findNodeWithLabel(edge.neighbor.label)
}
}

return duplicated
}
}

public func == (lhs: Graph, rhs: Graph) -> Bool {
return lhs.nodes == rhs.nodes
}```

## Queue

```Queue.swift

public struct Queue {
fileprivate var array = [T?]()
fileprivate var head = 0

public init() {

}

public var isEmpty: Bool {
return count == 0
}

public var count: Int {
return array.count - head
}

public mutating func enqueue(_ element: T) {
array.append(element)
}

public mutating func dequeue() -> T? {
guard head  50 && percentage > 0.25 {
}

return element
}

public var front: T? {
if isEmpty {
return nil
} else {
}
}
}```

#### 打破循环的条件需要根据实际情况来设定。

```//: Playground - noun: a place where people can play

import UIKit
import Foundation

var str = "Hello, playground"

func breadthFirstSearch(_ graph: Graph, source: Node) -> [String] {
/// 创建一个队列并把源Node放入这个队列中
var queue = Queue()
queue.enqueue(source)

/// 创建一个数组用于存放结果
var nodesResult = [source.label]

/// 设置Node的visited为true，因为我们会把这个当做一个开关
source.visited = true

/// 开始遍历
while let node = queue.dequeue() {
for edge in node.neighbors {
let neighborNode = edge.neighbor
if !neighborNode.visited {
queue.enqueue(neighborNode)
neighborNode.visited = true
nodesResult.append(neighborNode.label)
}
}
}

return nodesResult
}

let graph = Graph()

let nodeA = graph.addNode("a")
let nodeB = graph.addNode("b")
let nodeC = graph.addNode("c")
let nodeD = graph.addNode("d")
let nodeE = graph.addNode("e")
let nodeF = graph.addNode("f")
let nodeG = graph.addNode("g")
let nodeH = graph.addNode("h")

let nodesExplored = breadthFirstSearch(graph, source: nodeA)
print(nodesExplored)```

|