---
title: 第4回情報
tags: 
author: [旭丘数理科学部情報](https://www.docswell.com/user/asahi_infomatics)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/KY76MNZDEV.jpg?width=480
description: 第4回情報 by 旭丘数理科学部情報
published: January 20, 22
canonical: https://www.docswell.com/s/asahi_infomatics/Z4EDL5-2022-01-20-233131
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/KY76MNZDEV.jpg)

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


# Page. 2

![Page Image](https://bcdn.docswell.com/page/5G75Z5W8J4.jpg)

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


# Page. 3

![Page Image](https://bcdn.docswell.com/page/V9J2RNQV7R.jpg)

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


# Page. 4

![Page Image](https://bcdn.docswell.com/page/5DEYDPWQEM.jpg)

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


# Page. 5

![Page Image](https://bcdn.docswell.com/page/2VJN6592J8.jpg)

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


# Page. 6

![Page Image](https://bcdn.docswell.com/page/GYE9LY2D73.jpg)

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


# Page. 7

![Page Image](https://bcdn.docswell.com/page/5GE8X655JD.jpg)

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


# Page. 8

![Page Image](https://bcdn.docswell.com/page/MLEL89Y37R.jpg)

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


# Page. 9

![Page Image](https://bcdn.docswell.com/page/54JM6ZNMEW.jpg)

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


# Page. 10

![Page Image](https://bcdn.docswell.com/page/ZPJRP6DLE9.jpg)

旭丘数理科学部
DFS


# Page. 11

![Page Image](https://bcdn.docswell.com/page/NPEX3M26JX.jpg)

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


# Page. 12

![Page Image](https://bcdn.docswell.com/page/63EKYGMGJD.jpg)

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


# Page. 13

![Page Image](https://bcdn.docswell.com/page/4L739NY575.jpg)

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


# Page. 14

![Page Image](https://bcdn.docswell.com/page/V87DGW5Y7G.jpg)

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


# Page. 15

![Page Image](https://bcdn.docswell.com/page/4VJP39G2E8.jpg)

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


# Page. 16

![Page Image](https://bcdn.docswell.com/page/L2EV4M6XJQ.jpg)

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


# Page. 17

![Page Image](https://bcdn.docswell.com/page/Z57G1GNREL.jpg)

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


# Page. 18

![Page Image](https://bcdn.docswell.com/page/V4EQDXQYJP.jpg)

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


# Page. 19

![Page Image](https://bcdn.docswell.com/page/DKJ4Z6NZ71.jpg)

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


# Page. 20

![Page Image](https://bcdn.docswell.com/page/PLE1RV5DEG.jpg)

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


# Page. 21

![Page Image](https://bcdn.docswell.com/page/8GEW1L5872.jpg)

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


# Page. 22

![Page Image](https://bcdn.docswell.com/page/W47ZPMN9E3.jpg)

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


# Page. 23

![Page Image](https://bcdn.docswell.com/page/KYJ6MN8D7V.jpg)

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


# Page. 24

![Page Image](https://bcdn.docswell.com/page/5GJ5Z598E4.jpg)

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


# Page. 25

![Page Image](https://bcdn.docswell.com/page/4LE39NYGE5.jpg)

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


# Page. 26

![Page Image](https://bcdn.docswell.com/page/V8EDGW5NEG.jpg)

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


# Page. 27

![Page Image](https://bcdn.docswell.com/page/4V7P39GNJ8.jpg)

旭丘数理科学部
BFS


# Page. 28

![Page Image](https://bcdn.docswell.com/page/L2JV4M6Y7Q.jpg)

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


# Page. 29

![Page Image](https://bcdn.docswell.com/page/Z5EG1GNWJL.jpg)

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


# Page. 30

![Page Image](https://bcdn.docswell.com/page/V4JQDXQQ7P.jpg)

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


# Page. 31

![Page Image](https://bcdn.docswell.com/page/DK74Z6NYE1.jpg)

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


# Page. 32

![Page Image](https://bcdn.docswell.com/page/PLJ1RV5NJG.jpg)

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


# Page. 33

![Page Image](https://bcdn.docswell.com/page/8GJW1LWME2.jpg)

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


# Page. 34

![Page Image](https://bcdn.docswell.com/page/W4EZPM5MJ3.jpg)

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


# Page. 35

![Page Image](https://bcdn.docswell.com/page/KY76MN95EV.jpg)

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


# Page. 36

![Page Image](https://bcdn.docswell.com/page/5G75Z5NGJ4.jpg)

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


# Page. 37

![Page Image](https://bcdn.docswell.com/page/V9J2RN5D7R.jpg)

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


# Page. 38

![Page Image](https://bcdn.docswell.com/page/5DEYDPKMEM.jpg)

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


# Page. 39

![Page Image](https://bcdn.docswell.com/page/2VJN65R3J8.jpg)

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


# Page. 40

![Page Image](https://bcdn.docswell.com/page/GYE9LYMP73.jpg)

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


# Page. 41

![Page Image](https://bcdn.docswell.com/page/5GE8X6LXJD.jpg)

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


# Page. 42

![Page Image](https://bcdn.docswell.com/page/MLEL89LN7R.jpg)

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


# Page. 43

![Page Image](https://bcdn.docswell.com/page/54JM6ZMQEW.jpg)

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


# Page. 44

![Page Image](https://bcdn.docswell.com/page/ZPJRP6VKE9.jpg)

旭丘数理科学部
例題


# Page. 45

![Page Image](https://bcdn.docswell.com/page/NPEX3MZ5JX.jpg)

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


