このグラフで深さ優先探索を用いると順番はどのようになりますか？ 一意には決まらないと思いますが例を教

このグラフで深さ優先探索を用いると順番はどのようになりますか？

一意には決まらないと思いますが例を教えて欲しいです！ループするところがわかりません。

aを始点としてください。

No.1 回答者： stomachman 回答日時： 2018/10/24 17:51

◯ root(出発点)のノードを決め、「来ました」マークを付ける。

◯ ノードsから出るどの枝にも「通過しました」マークが付いていれば、sは行き止まりなので、sに来た枝b*（b*は「通過しました」マークが付いていてsに向かっている）を逆戻り。（rootから逆戻りしようとしたら、終わり。）
◯ ノードsから出る（「通過しました」マークが付いていない）テキトーな枝bを選んで、この枝bに「通過しました」マークを付ける。この枝bの先にあるノードs'について、
　s'に「来ました」マークが付いていたら、s'は既に行ったノードなので、bの枝は存在しなかったのと同じ。sの別の枝を選ぶ。
　s'に「来ました」マークが付いていなければ、s'へ移動して「来ました」マークを付ける。