DFS

3185 ワード
アルゴリズム#アルゴリズム# テキストリンク
DFS

まず定点の子供を探す方法です.
一つのノードに乗った子供が最後まで巡り、また戻って他の兄弟の子供に乗って巡りに行きます.
例

needVisitスタックとアクセスキューを使用します.
visitedneedVisitA
visitedAneedVisitBC
visitedACneedVisitBAGHI
visitedACIneedVisitBAGHCJ
visitedACIJneedVisitBAGHCI
visitedACIJneedVisitBAGH
visitedACIJHneedVisitBAGC
visitedACIJHGneedVisitBAC
visitedACIJHGBneedVisitD
visitedACIJHGBDneedVisitEF
visitedACIJHGBDFneedVisitED
visitedACIJHGBDFneedVisitD
サンプルコード
    public Queue<String> solution(HashMap<String, List<String>> graph, String startNode) {
        Stack<String> needVisit = new Stack<>();
        Queue<String> visited = new LinkedList<>();

        needVisit.add(startNode);

        while (!needVisit.isEmpty()) {
            final String node = needVisit.pop();

            if (!visited.contains(node)) {
                visited.add(node);
                needVisit.addAll(graph.get(node));
            }
        }
        return visited;
    }

    public static void main(String[] args) {
        final DfsExam T = new DfsExam();

        HashMap<String, List<String>> graph = new HashMap<>();
        graph.put("A", new ArrayList<>(Arrays.asList("B", "C")));
        graph.put("B", new ArrayList<>(Arrays.asList("A", "D")));
        graph.put("C", new ArrayList<>(Arrays.asList("G", "H", "I")));
        graph.put("D", new ArrayList<>(Arrays.asList("E", "F")));
        graph.put("E", new ArrayList<>(Arrays.asList("D")));
        graph.put("F", new ArrayList<>(Arrays.asList("D")));
        graph.put("G", new ArrayList<>(Arrays.asList("C")));
        graph.put("H", new ArrayList<>(Arrays.asList("C")));
        graph.put("I", new ArrayList<>(Arrays.asList("C", "J")));
        graph.put("J", new ArrayList<>(Arrays.asList("I")));

        System.out.println(T.solution(graph, "A").toString());
    }
  • 時間の複雑さ:
  • ノード数:V
  • 幹線:E
    = O(V+E)
    • Ssh ログアウトでプログラムを実行し続ける方法
    AES対称暗号化と復号化