もうみなさん、知っているかもしれないけどPythonだと「再帰関数よりも、非再帰の方が速い！」んです！！！！！
でも、やっぱり非再帰で書かずに、再帰関数を使って書いている人が多いように感じます。そこで、今回は非再帰での深さ優先探索の実装方法について書いてみたいと思います！
ネットで調べてみても全然でてこなかったから、もしかして自分が初めて！？（んなわけない…）
僕は、典型的な例（？）とは逆のパターンで、再帰関数より、非再帰の方が得意です！…と、いうより再帰関数を使ったことがまだ一度もありません（←これはどうなのか…）
ここに書いていくコードも、他の人のコードは参考にしていません…！（他の人のも見た方がよかったかもしれない）
そのため、やり方とかおかしいと思うかもしれませんが、そこはゆるしてください......
前置きみたいなのが長くなってしまいましたが、早速、書き方を解説したいと思います。
まずはコードを先にはっつけておきます（ネーミングセンスがないため変数名がおかしなことになっているので、変更をお願いします…）
また、深さ優先探索はいろいろなところで使われると思いますが、今から書くコードは、「頂点１から行くことのできる頂点の数を数える」コードです（もちろん出発点は変更可能）。
また、入力のところも書いておきました。ｎが頂点の数、ｍが辺の数で、辺は「a,b]という風に与えられ、辺iが頂点aと頂点bを結んでいることを表しています。
n,m=map(int,input().split()) graph = [[] * 1 for i in range(n)] for i in range(m): a,b=map(int,input().split()) graph[a-1].append(b) graph[b-1].append(a) #ここから深さ優先探索 stack=[1] itta=set() itta.add(1) while len(stack)>0: for i in range(len(graph[stack[(len(stack)-1)]-1])): if not graph[stack[len(stack)-1]-1][i] in itta: itta.add(graph[stack[len(stack)-1]-1][i]) stack.append(graph[stack[len(stack)-1]-1][i]) break else: stack.pop() print(len(itta))
上の方から順番に説明していきます。
まず、ｎとｍを受け取ります。AtCoderの問題でよくあるように、ｎは頂点の数、ｍは辺の数です。
次に、それぞれの辺の情報がｍ個与えられます。一つの辺の情報はa,bで表し、辺 i が頂点 a , b を連結していることを表しています。
これらの辺の情報を、二次元配列graphに格納します。この二次元配列には、「頂点 i 」から行くことのできる頂点を格納しておきます。
ですから、graph[0]には、頂点１から行くことのできる頂点が格納されています。同じように、graph[2]には、頂点３から行くことのできる頂点が格納されています。
ここから、深さ優先探索を始めます。stackという配列に出発する頂点を一つ格納します。今回はひとまず頂点１から出発することにします。
次に、今までにいったことのある頂点の番号を格納するset型を用意します。名前は「itta」です（な、なまえ…）。
これを読んでいるみなさんはもちろん十分わかっていると思うのですが、深さ優先探索ではすでに行ったところにはもういかないので、そのためにset型にいった頂点を格納しておいて、何回も同じ頂点に向かわないようにします。また、このset型の要素数を深さ優先探索が終わった後に確認すると、頂点１から行くことのできる頂点の数が分かります。set型にはいった頂点の番号が格納されているので、いった頂点の番号もすべて出力することができます。
ここからメインのところ？を”具体例”を使って解説していきます。
・まず、配列stackには、頂点１が格納されています。
・その後、頂点１から行くことのできる頂点を探索します。配列graphを見ていき、もし行ったことのない頂点の番号を見つけたらその頂点に移動することにします。
・例えば、頂点２と頂点１が連結だったとして、頂点２に移動することにしたとします。その場合、配列stackに頂点２の番号（２）を格納し、ループの最初に戻ります。同時に、set型の「itta」にも、２を格納します。
ここまで来たら、二番目の手順に戻ります。その後また三番目の手順をやって…また二番目に戻る。みたいなのを繰り返します。
頂点の数は有限なので（？）、しばらくこの操作を続けていくと、どうしても行ったことのない頂点しか行くことができないという状態になると思います。
ここまできたら、配列stackの一番最近に追加した要素を削除します（←説明が下手くそ…）。
具体例で説明してみると、
頂点１に行った！頂点２に行った！頂点４に行った！…でも行き止まりになっちゃった
この状態の時は、配列stackは下のような状態になっていると思います。
stack=[1,2,4]
深さ優先探索は、行けるところまで行って、行けなくなったら一個戻る、という作業を繰り返すので、頂点４に来る前にいた頂点２に戻らなければなりません。ですから配列stackに格納している「４」を削除すればいいのです。
…説明が下手くそな気がします…。やっていることだけを説明してみると、
・今いる頂点から、行ったことのない頂点に行くことができるのであれば、その頂点に行く。
もしくは
・今いる頂点から、行ったことのない頂点に行くことができないのであれば、ひとつ前にいた頂点に戻る。（この時頂点１にいる場合は、stackの要素数がゼロになり、whileの条件がFalseになるので、深さ優先探索が終了する）。
最後にset型のittaの要素数を出力すれば、頂点１からつながっている頂点の数（頂点１を含む）を出力することができます。
…説明は以上です。やっぱり説明がうまくなかったと思います。また、非再帰の深さ優先探索の説明というより、深さ優先探索の説明の方をいっぱいやっていたような…
とにかく、少しでも参考になればうれしいです。もし間違っているところがあったり、わからなくて教えてほしいところなどがあったらTwitter（X)などで連絡してください。お願いします！！！！
↓自分のTwitter（X）のアカウント。
https://twitter.com/rotti_coder
最後までありがとうございました！！
