勉強ブログ

わからんこととか覚え書きとか

Graph Introduction Traversals

■ lecture 33

時間が空いてしまった…m(_ _)m

 

グラフ探索アルゴリズムについて。

 一応特につまることはなく。

 

  • p.3 

頂点とか辺とかグラフの構成要素について。これの最初らへん。

https://mathtrain.jp/graph

 

  • p.10-11, 13-16

深さ優先探索について。preorder, postorderの話がわかりやすい。

https://www.google.co.jp/url?sa=t&source=web&rct=j&url=http://www-ikn.ist.hokudai.ac.jp/~arim/pub/algo/algo6.pdf&ved=2ahUKEwjvjtbBoqDZAhWEVrwKHR7WDH0QFjAAegQIExAB&usg=AOvVaw2Mr6WJWNx-QX6wDEyi0Lj_

 

  • p.12, 17

DAG, トポロジカルソートについて。

https://www.slideshare.net/mobile/hcpc_hokudai/topological-sort-69581002

 

  • p.18

ダイクストラ法。なんか聞いたことがあると思ったらインターンで使った方法だった。

http://www.deqnotes.net/acmicpc/dijkstra/