Breadth-first search 算法（Swift版）

2017-11-15 本文已影响119人老马的春天

在讲解Breadth-first search 算法之前，我们先简单介绍两种数据类型Graph和Queue。

Graph

image

这就是一个图，它由两部分组成：

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

这种数据结构可以形象的表示一个网络,而在实际解决问题的时候，我们除了找到类似网络的模拟外，还需要考虑下边两点：

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

而如何实现这个查找的过程就用到了算法。

在项目管理专业的工程方法中，存在一个有向连接图方法，根据这个图我们就可以划出邻接矩阵，然后再求出可达矩阵，缩减矩阵等等，说这些内容，是想表达在用代码模拟图的时候，可以使用矩阵的方式来描述，但本篇中采用的是另一种方式，我们使用数组保存某个节点的neighbor节点。

上边一段话会在下边的代码中进行展示：

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 {
      _ = duplicated.addNode(node.label)
    }

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

    return duplicated
  }
}

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

Queue

队列同样是一种数据结构，它遵循FIFO的原则，因为Swift没有现成的这个数据结构，因此我们手动实现一个。

值得指出的是，为了提高性能，我们针对在数组中读取数据做了优化。比如，当在数组中取出第一个值时，如果不做优化，那么这一步的消耗为O(n),我们采取的解决方法就是把该位置先置为nil，然后设置一个阈值，当达到阈值时，在对数组做进不去的处理。

这一部分的代码相当简单

Queue.swift

public struct Queue<T> {
    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 < array.count, let element = array[head] else { return nil }
        
        array[head] = nil
        head += 1
        
        let percentage = Double(head) / Double(array.count)
        if array.count > 50 && percentage > 0.25 {
            array.removeFirst(head)
            head = 0
        }
        
        return element
    }
    
    public var front: T? {
        if isEmpty {
            return nil
        } else {
            return array[head]
        }
    }
}