なっとく！アルゴリズム幅優先探索をSwiftで書く(p126)

# はじめに
納得アルゴリズム幅優先探索(p126)をPythonからSwiftに書き直してみる

# 幅優先探索とは
「Xまでの最短経路は何か」に答えるためのアルゴリズム

# 例題

```
あなたはマンゴー農園の所有者で、あなたのマンゴーを販売してくれるマンゴー販売者を探しています。Facebookでマンゴー販売者とつながっているでしょうか。(なっとく！アルゴリズムp112より引用)
```

```
あなたの友人を検索するだけでなく、友人の友人も検索します。あなたの人脈からマンゴー販売者を一人探し出すことが目的であることを思い出してください。(p114より引用)
```

つまり、マンゴー販売者が見つかるまで、人脈全体を探索する方法を探るというものです。

例題の人脈全体図は下記のようになっています。
![IMG_0908.png](https://qiita-image-store.s3.amazonaws.com/0/176479/343208c8-c5fb-d341-38f8-8fd2e177d181.png)
なっとく！アルゴリズム(p119)より引用





## python
なっとく！アルゴリズム(p126)よりPythonのコードを引用

```python
def search(name):
    search_queue = deque()
    search_queue += graph[name]
    searched = []
    while search_queue:
        person = search_queue.popleft()
        if not person in searched:
            if person_is_seller(person):
                print person + "is a mango seller"
                return True
            else:
                search_queue += graph[person]
                searched.append(person)
    return False
    
search("you")
```

### Swiftで書き直したコード全体

```Swift
// Your code here!

public struct Deque<T> {
  private var array = [T]()

  public var isEmpty: Bool {
    return array.isEmpty
  }

  public var count: Int {
    return array.count
  }

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

  public mutating func enqueueFront(_ element: T) {
    array.insert(element, at: 0)
  }

  public mutating func dequeue() -> T? {
    if isEmpty {
      return nil
    } else {
      return array.removeFirst()
    }
  }

  public mutating func dequeueBack() -> T? {
    if isEmpty {
      return nil
    } else {
      return array.removeLast()
    }
  }

  public func peekFront() -> T? {
    return array.first
  }

  public func peekBack() -> T? {
    return array.last
  }
  
  ///追加で書き加えた
  public mutating func enqueues(_ elements: [T]) {
    array.append(contentsOf: elements)
  }
}

//マンゴーを売ってる人の名前と一致したらtureを返す関数
func personIsSeller(name: String) -> Bool {
    let name = name
    if name == "jonny" {
        return true
    } else {
        return false
    }
}

//ノードの準備
var graph: [String:[String]] = [
    "you" : ["alice","bob","claire"],
    "bob" : ["anuj","peggy"],
    "claire" : ["jonny","thom"],
    "alice" : ["peggy"],
    "anuj":[],
    "peggy":[],
    "jonny":[],
    "thom":[]
]


func search(name:String) {
    print("graph",(graph[name])!)
    //Dequeの構造体を作る
    var searchQueue = Deque<String>()
    //指定した名前と関連する人物をキューに入れる
    searchQueue.enqueues((graph[name])!)
    //すでに探した名前を登録しておく配列
    var searched:[String] = []
    
    //キューがなくなるまで実行する
    while searchQueue.isEmpty == false {
        //キューの中から一つ名前を取り出す
        guard let person = searchQueue.dequeue() else{
            break
            return 
        }
        //すでに探した配列の中から、一致するものは無いか探す
        if searched.firstIndex(of: person) == nil {
            //マンゴーを売っている人か判定する関数
            if personIsSeller(name:person) {
                print("\(person)はマンゴーを売っている人です")
                break
            } else {
                //探した人物からまた関連する人物を辞書から抜き出しキューに入れる
                searchQueue.enqueues((graph[person])!)
                searched.append(person)
            }
            
        }
    }
}

search(name:"you")
```

## Dequeについて
[swift-algorithm-club の Deque](https://github.com/raywenderlich/swift-algorithm-club/tree/master/Deque)を参考に引用と拡張をした

Pythonのように`deque`というものは無いらしく、自作している例があったのでこれを活用した。
ここのリポジトリものすごく勉強になることわかった


```Swift
public struct Deque<T> {
  private var array = [T]()

  public var isEmpty: Bool {
    return array.isEmpty
  }

  public var count: Int {
    return array.count
  }

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

  public mutating func enqueueFront(_ element: T) {
    array.insert(element, at: 0)
  }

  public mutating func dequeue() -> T? {
    if isEmpty {
      return nil
    } else {
      return array.removeFirst()
    }
  }

  public mutating func dequeueBack() -> T? {
    if isEmpty {
      return nil
    } else {
      return array.removeLast()
    }
  }

  public func peekFront() -> T? {
    return array.first
  }

  public func peekBack() -> T? {
    return array.last
  }
  
  ///追加で書き加えた
  public mutating func enqueues(_ elements: [T]) {
    array.append(contentsOf: elements)
  }
}

```

## paizaで動かしているのもついでに掲載
https://paiza.io/projects/f7XK2bIN1VTk987tiu8Fcw

## 参考文献

https://developer.apple.com/documentation/swift/array

https://github.com/raywenderlich/swift-algorithm-club/tree/master/Deque

https://www.webopixel.net/ios/1022.html

https://developer.apple.com/documentation/swift/array/2994720-firstindex