グラフ探索 DFS 後編
グラフ上の様々な例題
いよいよ、深さ優先探索 (DFS) を用いて、グラフに関する様々な問題を解いてみましょう。グラフの連結性に関する問題の多くが、単純な探索によって解決できることがわかります。
そしてグラフ探索はとにかく「習うより慣れろ」の精神が重要なテーマでもあります。本記事では、グラフの連結性に関する諸概念に親しみながら、探索にも慣れるという一石二鳥を狙います。なお、ここで取り上げる問題のほとんどは DFS だけでなく BFS で解くこともできます。BFS を用いた解法については別途記事にしたいと思います。
4-1. s から t へ辿り着けるか問題を解いてみる
標準入力
v頂点数の数15
e:辺の数の数14
s :3
t: 7
無向グラフとする
0 が １につながっている
1が ２につながっている
code:bash
0 1
1 2
1 3
0 4
4 5
5 8
5 7
4 8
8 9
8 10
0 11
11 12
11 13
13 14
スタート
code:swift
//問題 頂点sから頂点tにたどり着けるか問題
func dfs(graph: Int, v:Int, seen: inout Bool) { dfs(graph: graph, v: ver, seen: &seen)
}
}
func main1() {
let input = readLine()!.split(separator: " ").map { Int($0)! }
let (V,E) = (input0, input1) var graph = Int.init(repeating: [], count: V)
var seen = Bool.init(repeating: false, count: V) _ = (0..<E).map { _ in
let (a,b) = readTwoInts()
}
let (from,to) = readTwoInts()
//
dfs(graph: graph, v: from, seen: &seen)
print("Yes")
} else {
print("No")
}
}
main1()
4-3. 二部グラフ判定
まず、DFS の始点となる頂点 v については白黒いずれに塗ってもよいです。ここでは白としてみます。そうすると
白頂点に隣接した頂点は黒でなければならない
黒頂点に隣接した頂点は白でなければならない
なお以下の実装では、配列 color に各頂点の色を格納しますが、これを seen 配列の役割も同時に持たせることにします。すなわち
color【V】= 1 (黒確定)、0 (白確定)、-1 (未訪問)
を表すようにする．