幅優先探索の整理



幅優先探索の整理。目的によって微妙に実装が異なるので幾つかのバージョンを PowerShell で書いた。


# グラフの表現

整理が目的なので効率性は度外視。

```.bash
function %w {$args | %{$_ -split ' '}}

$g = @{
  A = %w B C
  B = %w D E
  C = %w E F
}
```

`$g` は下記のグラフを表す。

![g1.png](https://qiita-image-store.s3.amazonaws.com/0/36744/6a1bc56a-9d41-6d17-05ff-7dae9bb421ce.png "g1.png")


# 単純な幅優先探索

下記の実装は `$StartNode` から幅優先探索によって各頂点を訪問し、その訪問順（[レベル順](https://ja.wikipedia.org/wiki/%E6%9C%A8%E6%A7%8B%E9%80%A0_(%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0)#.E5.B9.85.E5.84.AA.E5.85.88.E6.8E.A2.E7.B4.A2)）に並べられた頂点の配列を返す。
なお、訪問済みを検知していないため、始点 `$StartNode` から到達可能なサイクルが存在すれば停止しない。また、到達可能な全ての頂点を調べるため、無限グラフを探索すると停止しない可能性がある。終点 `$GoalNode` を発見した時点で停止させたければ、`if ($node -eq $GoalNode) {break}` を `$node` の下辺りに仕込む必要がある。

```.bash
function BFS ([string]$StartNode, [HashTable]$Children)
{
  $q = New-Object System.Collections.Queue
  $q.Enqueue($StartNode)

  while ($q.Count -ne 0)
  {
    $node = $q.Dequeue()
    $node

    $Children[$node] | ?{$_ -ne $null} | %{$q.Enqueue($_)}
  }
}
```

## 実行例

```.bash
$a = BFS F @{
  F = %w B G
  B = %w A D
  G = %w I
  D = %w C E
  I = %w H
}

$a -join ', ' # => F, B, G, A, D, I, C, E, H
```
![g2.png](https://qiita-image-store.s3.amazonaws.com/0/36744/d482fe3e-8b97-1fd9-5906-647af530f25b.png "g2.png")



# 訪問済みを検知する幅優先探索

下記の実装は、`$StartNode` から到達可能な全頂点の配列を返す。
なお、探索中、各頂点を無色 `$null` 、灰色 `"Gray"` 、黒 `Black"` に分類している。未発見の頂点は無色であり、訪問済みの頂点は灰色か、黒である。単純にサイクルに捕まらないよう訪問済みであることを管理したければ、灰色と黒を区別する必要はない。灰色は頂点がキューに残っていることを表し、黒は頂点に隣接する全ての頂点に訪問済みであることを表す。

```.bash
function BFS ([string]$StartNode, [HashTable]$Children)
{
  $q = New-Object System.Collections.Queue
  $q.Enqueue($StartNode)

  $Color = @{$StartNode = "Gray"}

  while ($q.Count -ne 0)
  {
    $node = $q.Dequeue()
    $node

    $Children[$node] | ?{$_ -ne $null} | ?{-not $Color.ContainsKey($_)} | %{
      $q.Enqueue($_)
      $Color[$_] = "Gray"
    }
    
    $Color[$node] = "Black"
  }
}
```

## 実行例

```.bash
$a = BFS A @{
  A = %w B
  B = %w C D
  C = %w A E
  D = %w E
  F = %w C
}

($a | sort) -join ', ' # => A, B, C, D, E
```

![g3.png](https://qiita-image-store.s3.amazonaws.com/0/36744/ec25f16b-5b78-560b-820a-68d04e14540b.png "g3.png")



# 重みなしグラフの最短距離を求める幅優先探索

下記の実装は、`$StartNode` から各頂点の最短距離を返す。ただし、全ての辺の重みが 1 であると仮定している。
なお、`$Distance[$x]` が `$null` を返すとき、`$StartNode` から `$x` への距離は∞とする。

```.bash
function BFS ([string]$StartNode, [HashTable]$Children)
{
  $q = New-Object System.Collections.Queue
  $q.Enqueue($StartNode)

  $Distance = @{$StartNode = 0}

  while ($q.Count -ne 0)
  {
    $node = $q.Dequeue()
    
    $Children[$node] | ?{$_ -ne $null} | ?{-not $Distance.ContainsKey($_)} | %{
      $q.Enqueue($_)
      $Distance[$_] = $Distance[$node] + 1
    }
  }
  
  $Distance
}
```

## 実行例

```.bash
$a = BFS A @{
  A = %w B C
  B = %w A D E
  C = %w A D F
  D = %w B C G
  E = %w B G
  F = %w C
  G = %w D E
}

$a.GetEnumerator() | sort Name
```

```txt
Name                           Value
----                           -----
A                              0
B                              1
C                              1
D                              2
E                              2
F                              2
G                              3
```

![g4.png](https://qiita-image-store.s3.amazonaws.com/0/36744/7fd5c7b2-4c78-838d-543c-21fd7db92283.png "g4.png") ![g6.png](https://qiita-image-store.s3.amazonaws.com/0/36744/37bfea67-f053-56ac-8a51-8a14f7cd4155.png "g6.png")


# 重みなしグラフの単一始点最短経路問題を解く幅優先探索

下記の実装は、`$StartNode`と各頂点の最短経路からなる内向木（最小全域木）を返す。

```.bash
function BFS ([string]$StartNode, [HashTable]$Children)
{
  $q = New-Object System.Collections.Queue
  $q.Enqueue($StartNode)

  $Parent = @{$StartNode = $StartNode}

  while ($q.Count -ne 0)
  {
    $node = $q.Dequeue()
    
    $Children[$node] | ?{$_ -ne $null} | ?{-not $Parent.ContainsKey($_)} | %{
      $q.Enqueue($_)
      $Parent[$_] = $node
    }
  }
  
  $Parent
}
```

## 実行例

```.bash
$p = BFS A @{
  A = %w B C
  B = %w A D E
  C = %w A D F
  D = %w B C G
  E = %w B G
  F = %w C
  G = %w D E
}

$n = 'G'
$path = @($n)
while ($p[$n] -ne $n) {$n = $p[$n]; $path = @($n) + $path}
$path -join ', ' # => A, B, D, G
```

![g4.png](https://qiita-image-store.s3.amazonaws.com/0/36744/7fd5c7b2-4c78-838d-543c-21fd7db92283.png "g4.png") ![g5.png](https://qiita-image-store.s3.amazonaws.com/0/36744/2c7d4d40-dca9-e8ac-85d1-31cbca9dc6d4.png "g5.png")