経路問題はウロボロスの香り

経路のパターンを洗い出す問題にて、
仕事場のプログラマーがいつまで経っても作れない…
ループする経路がないという限定条件なはずなんだけど…

というわけでサンプルを15分で書いて、
もう15分できれいにしたのがこちらです。
ハッシュテーブルに格納しているのは、
この方が実際に使うデータ構造に近かったからです。

	import java.util.ArrayList;
	import java.util.HashMap;
	public class NodeTreeTest {
	public static void main(String[] args) {
	HashMap<String, Node> map = new HashMap<String, Node>();
	// ノードの作成
	map.put("A", new Node("A"));
	map.put("B", new Node("B"));
	map.put("C", new Node("C"));
	map.put("D", new Node("D"));
	map.put("E", new Node("E"));
	map.put("F", new Node("F"));
	map.put("G", new Node("G"));
	map.put("H", new Node("H"));
	map.put("I", new Node("I"));
	map.put("J", new Node("J"));
	map.put("K", new Node("K"));
	// ノードの連結
	map.get("A").addChildren(new Node[]{map.get("B"), map.get("C")});
	map.get("B").addChildren(new Node[]{map.get("D")});
	map.get("C").addChildren(new Node[]{map.get("D"), map.get("E")});
	map.get("D").addChildren(new Node[]{map.get("H"), map.get("I")});
	map.get("E").addChildren(new Node[]{map.get("F"), map.get("G")});
	map.get("F").addChildren(new Node[]{map.get("J")});
	map.get("G").addChildren(new Node[]{map.get("J")});
	map.get("H").addChildren(new Node[]{map.get("K")});
	map.get("I").addChildren(new Node[]{map.get("K")});
	map.get("J").addChildren(new Node[]{map.get("K")});
	map.get("K").addChildren(new Node[]{});
	// 走査を開始する
	preorder(map.get("A"), map.get("A").getValue());
	}
	public static void preorder(Node node, String message) {
	// 子供がいない場合
	if (node.getChildren().size() == 0) {
	System.out.println(message);
	}
	// 子供がいる場合
	for (Node t : node.getChildren()) {
	preorder(t, message + ":" + t.getValue());
	}
	}
	public static class Node {
	private String value = null;
	private ArrayList<Node> children = new ArrayList<Node>();
	public Node(String value) {
	this.value = value;
	}
	public String getValue() {
	return value;
	}
	public ArrayList<Node> getChildren() {
	return children;
	}
	public void addChildren(Node[] nodes) {
	for (Node n : nodes) {
	children.add(n);
	}
	}
	}
	}

view raw NodeTreeTest.java hosted with ❤ by GitHub

追記：TreeModelクラスなんてものが…見なかったことにしよう。