Javaでキュー、スタックを使った木構造のBFS,DFS
インタフェースとArrayList,LinkedListを使ってみたかったので、ちょうどい題材としてキューとスタックにインタフェースを組み合わせて木構造を幅優先探索と深さ優先探索しました。
/ bin ar diff od usr home userA userB userC etc var
// スタックとキューを使った木構造の深さ優先、幅優先探索 // LinkedListの import java.util.LinkedList; import java.util.ArrayList; public class Traverse { public static void main(String[] args) { // DFS System.out.println("-- DFS"); traversal(new StackHandler()); // BFS System.out.println("-- BFS"); traversal(new QueueHandler()); } static void traversal(ContainerHandler handler){ // インタフェース変数(interface variable)というらしい Node node = TreeBuilder.build(); ContainerProxy proxy = new ContainerProxy(handler); proxy.put(node); while (!proxy.empty()){ node = proxy.fetch(); System.out.println(node.getValue()); // add all children to proxy for (int i = 0; i < node.size(); i++){ proxy.put(node.at(i)); } } } } // スタック、キュー関連 // はじめてのインタフェース interface ContainerHandler { public Node fetch(LinkedList<Node> lst); } class StackHandler implements ContainerHandler { public Node fetch(LinkedList<Node> lst){ return lst.removeFirst(); } } class QueueHandler implements ContainerHandler { public Node fetch(LinkedList<Node> lst){ return lst.removeLast(); } } class ContainerProxy { private ContainerHandler handler; private LinkedList<Node> cont; ContainerProxy(ContainerHandler h){ handler = h; cont = new LinkedList<Node>(); } void put(Node n){ cont.addFirst(n); } Node fetch(){ return handler.fetch(cont); } boolean empty(){ return cont.size() == 0; } } // // 木構造関連 // class TreeBuilder { public static Node build(){ // 木構造のビルド // root // bin // ar // diff // od // usr // home // userA // userB // userC // etc // var Node root = new Node("/"); Node bin = new Node("bin"); bin.add(new Node("ar")); bin.add(new Node("diff")); bin.add(new Node("od")); Node home = new Node("home"); home.add(new Node("userA")); home.add(new Node("userB")); home.add(new Node("userC")); Node usr = new Node("usr"); usr.add(home); root.add(usr); root.add(bin); root.add(new Node("etc")); root.add(new Node("var")); return root; } } class Node { private ArrayList<Node> entries; private String value; Node(String v) { entries = new ArrayList<Node>(); value = v; } public String getValue(){ return value; } public void add(Node n){ entries.add(n); } public int size(){ return entries.size(); } public Node at(int index){ return entries.get(index); } }
出力結果
-- DFS / var etc bin od diff ar usr home userC userB userA -- BFS / usr bin etc var home ar diff od userA userB userC