何でも質問してください。（動画とそこまで関係なくても構いません。） Feel free to ask any questions. (Even if they are not very relevant to the video.)

Beautiful explanation :D Would be nice to see a video of bfs + heap

0:47 _"[it seems whole areas is searched]"_ woww, this is sooo well illustrated without any words. awesome. thinking back, the if there were a record of possible moves, then that would easily allow to overcome this type of trap moves. 1:16 but G[v] is not defined.. ohw, it's pseudocode, haha, u got me there. 2:01 the tree illustration at right center is super helpful 5:34 -"[no detour in BFS... so, use BFS for shortest path.]"_ wowww, yeah, i got reminded that the A* SSSP algo does a combo of DFS + BFS, but yeah, it's guided i.e. uses a heuristic parameter.

うおおおBFSvsDFSが気になるぞ

Evimaさんのコードが綺麗

いつも解説動画見させていただいています。 質問なのですが、再帰のDFSにできてスタックのDFSにできないことってありますか？もしくは逆にスタックのDFSにできて再帰のDFSにできないことはありますか？抽象的な質問ですみません。回答していただけると幸いです。

電車乗り換えアプリで運賃最安で検索するような時はこの迷路に運賃の重みをつけた上でなんとかして頑張るんかな？ 遠回りした方が安いような時どうやって探索するか動画で見たいです

0:02 ゆっくり解説で類を見ない唐突さ

ちっちゃい霊夢かわいい

ずっと疑問に思っているのですが、再起関数で実装したDFSと、スタックで実装したDFSの実行速度に違いはあるのでしょうか？(python)

@evimalab

7 ай бұрын

はい、「自前」のスタックで実装した方が速いです。 この動画では実行速度については触れませんでしたが、もともと実行速度の速くないPythonにとっては致命的になりうるポイントです。 （おまけに、基本的には速い PyPy が再帰は苦手です。） 例えば、この問題（ABC327D: atcoder.jp/contests/abc327/tasks/abc327_d ）で再帰と非再帰の Python コード（PyPy）の速度を比較すると次のようになりました。 再帰：612 ms atcoder.jp/contests/abc327/submissions/47204491 非再帰：187 ms atcoder.jp/contests/abc327/submissions/47994307 なお、この動画の Python コードでは通常のリストをスタックとして使っていますが、これも collections.deque で置き換えた方が速いです。 （動画でそうしていないのは、データ構造をスタックからキューに変えたのが分かりづらくなるのと、通常のリストでは致命的に遅いというほどではないためです。 なお、queue.Queue は明確に遅く、少し分かりづらくなることを承知で使用を控えました。）

@paranoia5971

7 ай бұрын

回答ありがとうございます！ 今度からスタックで組もうと思います。 また、リストよりdequeを使ったほうが早いというのも知りませんでした... 勉強になります！

こんにちは、動画にありがとう。気に成りました。 for w in G[v] の中でwが何の意味ですか？ 普通uとv使う事がいっぱい見えます。

@evimalab

7 ай бұрын

v w x y z の w です（vertex の v を先に使いたかった）。 私は u, v より v, w の方が見やすいと思っていて、また u は used の頭文字でもあるので v, w を使いました。

@jullien191

7 ай бұрын

@@evimalab はい、ありがとうございました😊

BFSはテレポートしてるの草

how can i practice questions? ( from where should I pick )?

@user-mi2ft6ji3m

7 ай бұрын

yeah I have same quiz

@evimalab

7 ай бұрын

Problems that require DFS/BFS, or problems in competitive programming in general? In the latter case, I'd recommend using AtCoder Problems (kenkoooo.com/atcoder/ ), where you can sort problems by difficulty. I explained this in detail in this video: kzread.info/dash/bejne/dISfvMVsp9apqLg.htmlsi=XGAunmtVjM6K-5dz&t=271 . In the former case, I guess that's one of the features missing in AtCoder. For now, I'd recommend using Codeforces's problem tag "dfs and similar" and difficulty sorting: codeforces.com/problemset?order=BY_RATING_ASC&tags=dfs+and+similar . It may be better to prioritize ones that also have the tag "graphs".

2:10 i got where i fail in such type of problems: * in trying to [overly] optimize, my effort would go on inserting only false elements in G[v]... * while it _may_ help near the end of trees, but that makes the code a bit cumbersome... * anddd, also, it seems that while it may save some computation while traversing, * it will be expensive while making G[v] itself. as in the above case, the logic for making G[v] is simple, and can be done in one dedicated go at the start. * heck, it doesn't even need to be stored separately and can be done on the go with accessing x-1, y-1, x+1, y+1 if the graph is provided as such a 2d matrix so, this type of optim should be done _only_ where performance is extreme priority and there too, it should be done _only after_ benchmarking 3:07 well, this does exactly that. but it uses some different logic along with it

以雷霆击碎黑暗