BFS

5202 ワード
アルゴリズム#アルゴリズム# テキストリンク
BFS(幅優先ナビゲーション)
  • 古典的なグラフィックブラウズアルゴリズム
  • の頂点と同じレベルにあるノードが最初にナビゲートする方法
    • .
    HashMapで図形を表す
    HashMap<String, List<String>> graph = new HashMap<String, List<String>>();

graph.put("0", new ArrayList<String>(Arrays.asList("1","2");
graph.put("1", new ArrayList<String>(Arrays.asList("0","3");
graph.put("2", new ArrayList<String>(Arrays.asList("0","6");
graph.put("3", new ArrayList<String>(Arrays.asList("1");
graph.put("4", new ArrayList<String>(Arrays.asList("1");
graph.put("5", new ArrayList<String>(Arrays.asList("2");
graph.put("6", new ArrayList<String>(Arrays.asList("2");
    BFSプロセス
    needVisit、2つのキューにアクセスします.
    visitedneedVisit0
    visited0needVisit12
    visited01needVisit2034
    visited012needVisit034056
    visited0123needVisit40561
    visited01234needVisit05611
    visited01235needVisit6112
    visited012356needVisit1122
    例

    サンプルコード
        public Queue<String> solution(HashMap<String, List<String>> graph, String startNode) {
        Queue<String> visited = new LinkedList<>();
        Queue<String> needVisit = new LinkedList<>();

        needVisit.add(startNode);

        while (needVisit.size() > 0) {
            final String node = needVisit.poll();

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

    public static void main(String[] args) {
        final BfsExam T = new BfsExam();
        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("A", "G", "H", "I")));
        graph.put("D", new ArrayList<>(Arrays.asList("B", "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)
    • Flatiron での初日と私の最大の苦労.
    javascript foreachを連続して実行するには?