第4回情報

旭丘数理科学部 第4回情報 おしながき • グラフとは？ • DFS • BFS 旭丘数理科学部 情報講義担当 たきかわ @cinnamon_cute_

旭丘数理科学部 グラフとは？

グラフとは？ • グラフとは？ • 頂点と辺を持った構造 • 物事の関係を表すのに用いる。 • グラフで表せるものの例 • SNSのFF関係 • 物の輸送経路 • 人間の交友関係 • and more! 旭丘数理科学部

グラフとは？ 旭丘数理科学部 • 鉄道の例 岐阜 大阪 沖縄 名古屋 セント レア 東京

グラフとは 旭丘数理科学部 • 僕の交友関係の例 たきかわ

グラフとは 旭丘数理科学部 • 頂点 岐阜 • 右図の青丸の部分 大阪 名古屋 •辺 • 右図の線の部分 • 連結成分 • 辺と頂点からなる構造 • 右図には次の連結成分がある • 沖縄 • 名古屋～… 沖縄 セント レア 東京

グラフとは？ 旭丘数理科学部 • 大きく分けて2種類のグラフがあります。 • 1.有向グラフ • 辺が向きを持ってるグラフです。 • 右図みたいなやつ • 矢印の向きにしか進めません。 • Ex. • 自宅→大曽根は行けるが • 大曽根→自宅はいけない 大曽 根 学校 自宅 矢田

グラフとは 旭丘数理科学部 • 2.無向グラフ • 向きを持っていないグラフです。 • 右図みたいなやつ • 両方に進めます。 • Ex. • 以下略 栄 市役 所前 どっ か 砂田 橋

グラフとは? 旭丘数理科学部 • プログラミングで実現する場合 • 各頂点に0-indexedの番号をふる • 二次元配列を作成( vector<vector<int>> graph(N) ) • 頂点番号a→bへ辺をはりたいときには、 • graph[a].push_back(b) • をする。無向グラフを作りたい場合は • graph[b].push_back(a) • も同時に行う

旭丘数理科学部 DFS

DFS 旭丘数理科学部 • 最も有名かつ初歩的なグラフ探索手法です。 • グラフ探索手法とは、グラフから何かしらの情報を読み取ること の総称です。 • DFSでは、パスが存在するかどうかを調べることができま す。 • パスとは、ある頂点からある頂点への道のりです。 • Ex. s-tパスが存在するかどうか する しない t s t s

DFS 旭丘数理科学部 • DFSとは • Deep First Searchの略で、日本語だと深さ優先探索 • ある頂点sを始点として、すべての頂点tに対してs-tパスが存在す るかを判別することができる。 • どのように探索するか • 始点から出ている辺の先の頂点を調べる • その頂点から出ている辺の先の頂点を調べる • …以下ループ • すべての頂点の探索が終わり次第終了。

DFS 旭丘数理科学部 • 今回はこの無向グラフを用いて実際にDFSを行います。 ｓ

DFS 旭丘数理科学部 • sの辺を確認します。 • s-パスが存在する頂点には橙色を付けていきます。 ｓ

DFS 旭丘数理科学部 先にある頂点も同じ用に確認し、色をつけます。 (わかりやすさのために操作中の頂点には赤色をつけます) ｓ

DFS 旭丘数理科学部 • まずひとつの辺を見ます。 ｓ

DFS 旭丘数理科学部 • 辺の先の頂点から出る辺を確認します。 ｓ

DFS 旭丘数理科学部 • 同様に確認します。 ｓ

DFS 旭丘数理科学部 • 頂点から出る辺がないです。 ｓ

DFS 旭丘数理科学部 • なので、来た頂点に1個戻ります。 ｓ

DFS 旭丘数理科学部 • 同様に、1個戻ります。 ｓ

DFS 旭丘数理科学部 • 同様に1個戻ると、未探索の辺が見つかります。 ｓ

DFS 旭丘数理科学部 • 辺を探索しますが、先が色付き頂点なので、探索しません。 ｓ

DFS 旭丘数理科学部 • 未探索の辺がなくなったので戻ります。 ｓ

DFS 旭丘数理科学部 • ｓまで戻ってきたので、DFS終了です。 • 色付き頂点がパスの存在するところです。 ｓ

DFS • プログラミングとしての実装方法は、 • vector<bool> seen(N,false)を作る • graph[x]に入っている頂点を探索する • 探索した頂点のseen[x]=true;にする • 辺をすべて探索したら戻る • の実装を繰り返します 旭丘数理科学部

旭丘数理科学部 BFS

BFS 旭丘数理科学部 • Breadth First Searchの略 • これを用いることによって、頂点からの距離がわかる。 • どのように実装するか • 辺をデータ構造のqueueに入れて、頂点から出る辺を探索する • データ構造queueとは？ • FILO First In Last Out 型のデータ構造 • 人が並んでいる列を考えると良い

旭丘数理科学部 • 今回はこの無向グラフを用いてBFSを行う s

旭丘数理科学部 • 原点に色つけます距離もつけます 0

旭丘数理科学部 • 辺と頂点をを見て距離をつけます 1 0

旭丘数理科学部 • 別の辺と頂点を見ます 1 1 0

旭丘数理科学部 • 辺がなくなったので新たな距離1の頂点へ移ります 1 1 0

旭丘数理科学部 • 辺を見て距離2の頂点を塗ります 2 1 1 0

旭丘数理科学部 • 辺がなくなったので次の距離1の頂点を見ます 2 1 1 0

旭丘数理科学部 • 上にある辺の先はすでに距離が判明しているのでスキップ • 右下の辺の先に距離を書きます。 2 1 1 0 2

旭丘数理科学部 • 距離1の頂点は全部見たので距離2の頂点を見ます 2 3 1 3 1 0 2

旭丘数理科学部 • もう1つの距離2の頂点からも見ます 2 3 1 3 1 0 3 2

旭丘数理科学部 • 距離2の頂点は全部見たので、3へ行きます 2 3 1 3 1 0 3 2

旭丘数理科学部 • 3の頂点から辺を見ます 4の頂点に色塗ります 2 3 1 4 3 1 0 3 2

旭丘数理科学部 • 他の3の頂点からも見ます。 • (すでに4は塗られているので更新されない) 2 3 1 4 3 1 0 3 2

旭丘数理科学部 • 4の頂点から見ますが、辺の先はすべて色が塗られているの でこれで終了です。 2 3 1 4 3 1 0 3 2

旭丘数理科学部 • DFSとBFS何が違うの？ • DFS は、FILO First in Last out • BFS は、FIFO First in First out • DFSはつきすすむ捜索手順 • BFSはまんべんなく進む捜索手順 • 計算量はともに𝑂(|𝐸| + |𝑉|)です。 • (最悪の場合でも、頂点を1回、辺を1回を全部確認するため) • It’s so Fast!

旭丘数理科学部 例題

旭丘数理科学部 • 頑張って考えてください • 疲れた • 二部グラフ判定とかどう？ • JOI 2021/2022 予選 とかどう？