ＤＦＳ,ＢＦＳ と ＤＦＳ spanning tree,ＢＦＳ spannig tree

質問

ＤＦＳ,ＢＦＳ と ＤＦＳ spanning tree,ＢＦＳ spannig tree

これってどう違うんですか？

回答No.2

a-kuma · ベストアンサー

> ただ、最小全域木（ｓｐｎｎｉｎｇ　ｔｒｅｅ）がよくわかりません。

文字だけで説明するのは、ちと厳しいので、絵を探してみました。
参考URLのページではどうですか？

参考URL：

http://www.comm.ics.tut.ac.jp/gidaisai/opt/spanning.html

回答No.1

a-kuma

なんにも知らない人に説明するには、（私には）ちと、難しいかも。
グラフ理論を知っている、と思って良いのでしょうか？

DFS は、深さ優先探索です。経路のある時点で、いくつかの選択肢がある場合に、
ある選択肢に決め、その先がどうなるかを評価してから、次の選択肢に移ります。

BFS は、幅優先探索です。経路のある時点で、いくつかの選択肢がある場合に、
その選択肢全てを評価してから、どれをとるかを決めます。

道に迷って、分岐路にいることを想像しましょう。

DFS は、とりあえず道を決め、ずんずん先に進むやり方です。もちろん、他の
道をあとで探すために、今の場所を覚えておく必要があります。

BFS は、行ける道を全て見渡してみて、一番良さそうな道を選んで進んでゆく
やり方です。今の場所を覚えておく必要があるのは DFS と一緒。

spanning tree とは、「最小全域木」と呼ばれます。

経路を探すときに、ループを無くすような経路を最初に決めるやり方です。

お礼

ＤＦＳとＢＦＳはわかりました。ありがとうございました。

ただ、最小全域木（ｓｐｎｎｉｎｇ　ｔｒｅｅ）がよくわかりません。
ループを無くすような経路を最初に決めるとはどういうことですか？