DFS と BFS

読了目安約3分

グラフを隣接リストで表し、深さ優先探索と幅優先探索で全頂点をたどる。

この章の目次

グラフは、頂点とそれらを結ぶ辺でできた構造です。

隣接リスト

グラフはプログラムでは隣接リストで表します。 graph[v] を「v と辺でつながる頂点の配列」とする、型 [[Int]] の二次元配列です。

Swift

let n = 6
let edges = [(1, 2), (1, 3), (2, 4), (3, 4), (4, 5)]
var graph = [[Int]](repeating: [], count: n + 1)
for (a, b) in edges {
    graph[a].append(b)
    graph[b].append(a)
}
print(graph[1])
print(graph[4])

向きのない辺 (無向辺) は、両方向に追加します。頂点番号を添字にそのまま使うため、大きさは n + 1 で確保します。

深さ優先探索（DFS）

**深さ優先探索（DFS）**は、行けるだけ奥へ進み、行き止まりで引き返す探索です。「行ける未訪問の頂点へ移る」を再帰で書くと、そのまま DFS になります。

同じ頂点を 2 回訪ねないよう、訪問済みを visited 配列に記録します。記録がないと、同じ辺を行き来して無限ループになります。

Swift

let n = 6
let edges = [(1, 2), (1, 3), (2, 4), (3, 4), (4, 5)]
var graph = [[Int]](repeating: [], count: n + 1)
for (a, b) in edges {
    graph[a].append(b)
    graph[b].append(a)
}

var visited = [Bool](repeating: false, count: n + 1)
func dfs(_ v: Int) {
    visited[v] = true
    print(v, terminator: " ")
    for next in graph[v] where !visited[next] {
        dfs(next)
    }
}
dfs(1)
print()

頂点 1 から 2、4 と奥まで進み、行き止まりで戻って残りを訪ねています。

再帰が深くなりすぎる大きな入力では、前章のスタックへ「これから訪ねる頂点」を積む書き方に切り替えます。

幅優先探索（BFS）

**幅優先探索（BFS）**は、出発点に近い頂点から順に訪ねる探索です。「次に訪ねる頂点」を前章のキューで管理すると、近い順が保たれます。

各頂点を最初に見つけたときの手数が、そのまま最短距離 (通る辺の最少本数) になります。

Swift

let n = 6
let edges = [(1, 2), (1, 3), (2, 4), (3, 4), (4, 5)]
var graph = [[Int]](repeating: [], count: n + 1)
for (a, b) in edges {
    graph[a].append(b)
    graph[b].append(a)
}

var dist = [Int](repeating: -1, count: n + 1)
var queue = [1]
dist[1] = 0
var head = 0
while head < queue.count {
    let v = queue[head]
    head += 1
    for next in graph[v] where dist[next] == -1 {
        dist[next] = dist[v] + 1
        queue.append(next)
    }
}
for v in 1...n {
    print("頂点 \(v): \(dist[v])")
}

距離の配列 dist を -1 で初期化し、visited の役割も兼ねさせています。

試してみよう: edges に (1, 5) を足すと、頂点 5 の距離が 3 から 1 に縮むことを確かめてください。

DFS も BFS も全頂点と全辺を 1 回ずつ見るので、計算量は O(N + M) です (N は頂点数、M は辺数)。

グリッドへの応用

迷路のようなマス目 (グリッド) もグラフです。各マスを頂点、上下左右の隣を辺とみなせば、同じ BFS がそのまま使えます。

Swift

let maze = [
    "..#.",
    ".#..",
    "....",
]
let grid = maze.map { Array($0) }
let h = grid.count
let w = grid[0].count

var dist = [[Int]](repeating: [Int](repeating: -1, count: w), count: h)
var queue = [(0, 0)]
dist[0][0] = 0
var head = 0
let dy = [1, -1, 0, 0]
let dx = [0, 0, 1, -1]
while head < queue.count {
    let (y, x) = queue[head]
    head += 1
    for d in 0..<4 {
        let ny = y + dy[d]
        let nx = x + dx[d]
        if ny < 0 || ny >= h || nx < 0 || nx >= w { continue }
        if grid[ny][nx] == "#" || dist[ny][nx] != -1 { continue }
        dist[ny][nx] = dist[y][x] + 1
        queue.append((ny, nx))
    }
}
print(dist[h - 1][w - 1])

# は壁で、左上から右下への最短の歩数を出力しています。 4 方向への移動は dy と dx の配列で書くのが定型です。

学びどころ

概念	一言まとめ
隣接リスト	`graph[v]` = v とつながる頂点の配列
DFS	奥まで進んで戻る。再帰かスタックで書く
BFS	近い順に訪ねる。キューで書き、最短距離が出る
`visited`	訪問済みの記録。無限ループを防ぐ

演習

1 行目に頂点数 N と辺数 M が入力されます。続く M 行に、無向辺の両端 a b (1 ≦ a, b ≦ N) が入力されます。

辺をたどって行き来できる頂点のまとまりを連結成分と呼びます。このグラフの連結成分の個数を出力してください。

テキスト
入力例:
5 3
1 2
2 3
4 5

出力例:
2

模範解答

Swift
let nm = readLine()!.split(separator: " ").map { Int($0)! }
let n = nm[0]
let m = nm[1]
var graph = [[Int]](repeating: [], count: n + 1)
for _ in 0..<m {
    let e = readLine()!.split(separator: " ").map { Int($0)! }
    graph[e[0]].append(e[1])
    graph[e[1]].append(e[0])
}

var visited = [Bool](repeating: false, count: n + 1)
func dfs(_ v: Int) {
    visited[v] = true
    for next in graph[v] where !visited[next] {
        dfs(next)
    }
}

var count = 0
for v in 1...n where !visited[v] {
    count += 1
    dfs(v)
}
print(count)

未訪問の頂点から DFS を始めるたびに、連結成分が 1 つ見つかります。