グラフ探索 前編

２つのデータ管理方法

seen: その頂点を検知済みかどうかを表す配列

todo: 検知したがまだ訪問済みでない頂点の集合 (保留中の頂点の集合)

以下の擬似コードで表せる．

seen 全体を false に初期化して、todo を空にする

seen【s 】= true として、todo に s を追加する

todo が空になるまで以下を繰り返す:

todo → 32

todo から一つ頂点を取り出して v とする

T(v) の各要素 w に対して、

seen【w】= true であったならば、何もしない

そうでなかったら、seen【w】 = true として、todo に w を追加する

具体例

以下のような有向グラフを考えてみる

https://scrapbox.io/files/60f0b65fadd405001cb11b7d.png

code:swift

//graphを作成

//頂点を検知済みかどうかを表す配列

// 検知したがまだ訪問済みでない頂点の集合 (保留中の頂点の集合)

//スタート0地点

todo.append(0)

while !todo.isEmpty {

// 1

for i in Vs {

todo.append(i)

}

}

record.append(todo.first!)

todo.removeFirst()

}

print(record)

木構造について

木はグラフの一種

「サイクルを持たない」かつ「連結」(はぐれVがないこと)であるようなグラフのことを木という

https://scrapbox.io/files/60f0bed17c9039001c5c1cb0.webp

DFSは人間の思考に近い.

再帰関数と相性が良い

実装例

code:swift

//ここ重要 seenはグローバルに宣言するのもあり 今回は引数に渡している．

//vに訪問済み

//訪問済みならコンティニュー⛑

dfs(graph: graph, v: nextV, seen: &seen)

}

}

func main() {

//頂点の数，辺の数

let twoinput = readLine()!.split(separator: " ").map { Int($0)! }

//グラフを作成

_ = (0..<E).map { _ in

let (a,b) = readTwoInts()

}

//dfs

dfs(graph: graph, v: 1, seen: &seen)

print(graph)

}

main()

行きがけ順

code:swift

//vに訪問済み

count += 1

//訪問済みならコンティニュー⛑

dfs(graph: graph, v: nextV, seen: &seen, firstO: &firstO, count: &count)

}

}

帰りがけ順

code:swift

//vに訪問済み

//訪問済みならコンティニュー⛑

dfs(graph: graph, v: nextV, seen: &seen, lastO: &lastO, count: &count)

}

count += 1

}

DFSの説明は以上次は実践篇