幅優先探索のプログラムにおいて、深さをカウントするにはどうしたら良いですか?
例えば、
a→b→d
-----→e
-→c→f
-----→g
この場合aは深さ0。b,cが深さ1。d,e,f,gが深さ2という感じでカウントしたい。
以下はwikiの幅優先探索アルゴリズムの疑似コード
function 幅優先探索(v)
Q ← 空のキュー
v に訪問済みの印を付ける
v を Q に追加
while Q が空ではない do
v ← Q から取り出す
v を処理する
for each v に接続している頂点 i do
if i が未訪問 then
i に訪問済みの印を付ける
i を Q に追加
気になる質問をクリップする
クリップした質問は、後からいつでもMYページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
回答2件
0
ベストアンサー
TreeTraversalDemo.java
java
1import java.util.ArrayDeque; 2import java.util.Deque; 3 4class Tree { 5 String value; 6 Tree left; 7 Tree right; 8 9 Tree(String v, Tree l, Tree r) { 10 value = v; 11 left = l; 12 right = r; 13 } 14 15 public String toString() { 16 return value; 17 } 18} 19 20public class TreeTraversalDemo { 21 public static void main(String[] args) { 22 Tree root = new Tree("A", 23 new Tree("B", 24 new Tree("D", null, null), 25 new Tree("E", null, null)), 26 new Tree("C", 27 new Tree("F", null, null), 28 null) 29 ); 30 visit(root); 31 } 32 static void visit(Tree root) { 33 Deque<Object> queue = new ArrayDeque<Object>(); 34 35 queue.addFirst(root); 36 queue.push(0); 37 while(!queue.isEmpty()) { 38 Tree tree = (Tree)queue.removeLast(); 39 Integer nest = (Integer)queue.removeLast(); 40 System.out.println(tree.value + " [" + nest + "]"); 41 if (tree.left != null) { 42 queue.addFirst(tree.left); 43 queue.addFirst(nest + 1); 44 } 45 if (tree.right != null) { 46 queue.addFirst(tree.right); 47 queue.addFirst(nest + 1); 48 } 49 } 50 } 51}
キューに要素とその深さを対にして add, remove してます。
(本当は [要素、nest] の配列を Type として宣言して、その Type のインスタンスを add, remove したほうがよいです)
参考情報
- Visitor パターン再考
https://qiita.com/lyrical_logical/items/bc6126f34a571a2c4f97
- 深さ優先探索と幅優先探索の簡単な実装方法
http://d.hatena.ne.jp/lettas0726/20110418/1303097692
- Javaで深さ優先探索と幅優先探索
http://ryuunen-no-ikuth.hatenablog.com/entry/2014/05/14/215043
- 2分木の走査(全ノードの数え上げ)
http://fujimura2.fiw-web.net/java/mutter/tree/tree-traversal.html
投稿2017/12/08 20:42
総合スコア22324
0
再帰アルゴリズムとして考えるなら関数の引数に付加さを表す引数を加えれば簡単だと思います。
例えば深さ優先で木構造を以下のようにダンプするコードを書く場合など自分はよくそうします。
text
1+html 2 +head 3 +meta 4 +title 5 +body 6 +h2 7 +p
再帰ではなくキューなどを使ったアルゴリズムではキューにノードだけでなく深さも入れればよいです。(キューによるループでも再帰でも互いに相手のシミュレーションをしていると見做せるので本質的には同じことができます)
ところで質問文の最初の例は幅優先ではなくて深さ優先に見えます。
投稿2017/12/08 17:57
総合スコア18394
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
あなたの回答
tips
太字
斜体
打ち消し線
見出し
引用テキストの挿入
コードの挿入
リンクの挿入
リストの挿入
番号リストの挿入
表の挿入
水平線の挿入
プレビュー
質問の解決につながる回答をしましょう。 サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。 また、読む側のことを考えた、分かりやすい文章を心がけましょう。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。