Depth First Search in Java

テキストリンク:https://www.baeldung.com/java-depth-first-search
1.概要
このチュートリアルでは、Javaでの深度優先検索について説明します.
深度優先探索(DFS)は、ツリー、図などのデータ構造に適用される遍歴アルゴリズムである.次のブランチに移動する前に、深さ優先探索は深さを優先原則として新しいブランチを探索します.
次のセクションでは、まずツリーの実装、次に図について説明します.
Javaでこれらの構造を実装する方法については、以前のツリーBinary Treeと図Graphに関するチュートリアルを参照してください.
2.ツリーの深さ優先検索
DFSを使用してツリーを巡回するには、次の3つの順序があります.

先序遍歴

中序遍歴

後序は

を遍歴する.
2.1先順遍歴
先行シーケンスループでは、まずそのルートノードをループし、左サブツリーと右サブツリーの順にします.
再帰を使用して、優先パスを簡単に実行します.

現在のノード

へのアクセス

左サブツリー

を巡る

右サブツリー

を巡る

public void traversePreOrder(Node node) {
    if (node != null) {
        visit(node.value);
        traversePreOrder(node.left);
        traversePreOrder(node.right);
    }
}

再帰的でない方法を使用して、先行ループを実装します.

ルートノードをスタック

に入れる

スタックが空でない場合

現在のノード(スタックトップ要素)弾スタック

現在のノード

へのアクセス

現在のノードの右サブノード、左サブノードを順次スタック

に入れる.

public void traversePreOrderWithoutRecursion() {
    Stack<Node> stack = new Stack<Node>();
    Node current = root;
    stack.push(root);
    while(!stack.isEmpty()) {
        current = stack.pop();
        visit(current.value);
         
        if(current.right != null) {
            stack.push(current.right);
        }    
        if(current.left != null) {
            stack.push(current.left);
        }
    }        
}

2.2のシーケンス遍歴
中順ループの場合は、左サブツリーにアクセスし、ルートノードにアクセスし、最後に右サブツリーにアクセスします.
二叉探索ツリーの中順遍歴は、値の増加順にノードを遍歴することを意味する.
再帰的インプリメンテーションにおけるシーケンシャルループを使用するには、次の手順に従います.

public void traverseInOrder(Node node) {
    if (node != null) {
        traverseInOrder(node.left);
        visit(node.value);
        traverseInOrder(node.right);
    }
}

また、再帰的でないインプリメンテーションのシーケンシャルループも使用できます.

ルートノードスタック

スタックが空でない場合

は、現在のノードが最も左のノード(すなわち、左のサブノードがない)

になるまで、左のサブノードをスタックに押し込み続ける.

現在のノード

へのアクセス

右サブノードスタック

public void traverseInOrderWithoutRecursion() {
    Stack<Node> stack = new Stack<Node>();
    Node current = root;
    stack.push(root);
    while(! stack.isEmpty()) {
        while(current.left != null) {
            current = current.left;                
            stack.push(current);                
        }
        current = stack.pop();
        visit(current.value);
        if(current.right != null) {
            current = current.right;                
            stack.push(current);
        }
    }
}

2.3後序遍歴
最後に、下位ループでは、ルートノードにアクセスする前に、左サブノード、右サブノードの順にアクセスします.
前を参照して、再帰的に実装された後の順序を繰り返します.

public void traversePostOrder(Node node) {
    if (node != null) {
        traversePostOrder(node.left);
        traversePostOrder(node.right);
        visit(node.value);
    }
}

再帰的でない実装を使用して、次の順序で巡回します.

ルートノードをスタック

に入れる

スタックが空でない場合

左サブツリーと右サブツリー

を巡回したかどうかを確認します.

がない場合は、右サブノードと左サブノードをスタック

に押し付ける.

public void traversePostOrderWithoutRecursion() {
    Stack<Node> stack = new Stack<Node>();
    Node prev = root;
    Node current = root;
    stack.push(root);
 
    while (!stack.isEmpty()) {
        current = stack.peek();
        boolean hasChild = (current.left != null || current.right != null);
        boolean isPrevLastChild = (prev == current.right || 
          (prev == current.left && current.right == null));
 
        if (!hasChild || isPrevLastChild) {
            current = stack.pop();
            visit(current.value);
            prev = current;
        } else {
            if (current.right != null) {
                stack.push(current.right);
            }
            if (current.left != null) {
                stack.push(current.left);
            }
        }
    }   
}

3.図の深さ優先探索
図とツリーの主な違いは、図がループを含む可能性があることです.
したがって、ループ検索を回避するために、各ノードにアクセスするときにタグを付けます.
次に、図DFSの再帰的、非再帰的実装を示す.
3.1図のDFS再帰実装
まず、再帰から始めましょう.

任意のノードから

を開始する.

現在のノードがアクセス済みであることを示す

現在のノード

へのアクセス

は、非アクセスの隣接ノード

を巡回する.

public void dfs(int start) {
    boolean[] isVisited = new boolean[adjVertices.size()];
    dfsRecursive(start, isVisited);
}
 
private void dfsRecursive(int current, boolean[] isVisited) {
    isVisited[current] = true;
    visit(current);
    for (int dest : adjVertices.get(current)) {
        if (!isVisited[dest])
            dfsRecursive(dest, isVisited);
    }
}

3.2図のDFS非再帰実装
再帰を用いずに図のDFSを実現してもよい.スタックを使用して実装する必要もあります.

は、任意のノードから

を開始する.

ノードスタック

スタックが空でない場合

現在のノードがアクセス済みであることを示す

現在のノード

へのアクセス

アクセスされていない隣接頂点スタック

public void dfsWithoutRecursion(int start) {
    Stack<Integer> stack = new Stack<Integer>();
    boolean[] isVisited = new boolean[adjVertices.size()];
    stack.push(start);
    while (!stack.isEmpty()) {
        int current = stack.pop();
        isVisited[current] = true;
        visit(current);
        for (int dest : adjVertices.get(current)) {
            if (!isVisited[dest])
                stack.push(dest);
        }
    }
}

3.4トポロジのソート
図の深さ優先探索には多くの応用がある.トポロジーソートは、深度優先検索で最も有名なアプリケーションの1つです.
図面へのトポロジーソートは、その頂点の線形ソートであるため、ソースノードは各エッジに対してターゲットの前に配置されます.
トポロジーの順序付けを行うには、実装されたばかりのDFSを簡単に改造する必要があります.

アクセスする頂点をスタックに保持する必要があります.トポロジーソートは、反対の順序でアクセスする頂点

であるためです.

は、すべての隣接ノードを巡回した後にのみ、アクセスしたノードをスタックにプッシュします.

public List<Integer> topologicalSort(int start) {
    LinkedList<Integer> result = new LinkedList<Integer>();
    boolean[] isVisited = new boolean[adjVertices.size()];
    topologicalSortRecursive(start, isVisited, result);
    return result;
}
 
private void topologicalSortRecursive(int current, boolean[] isVisited, LinkedList<Integer> result) {
    isVisited[current] = true;
    for (int dest : adjVertices.get(current)) {
        if (!isVisited[dest])
            topologicalSortRecursive(dest, isVisited, result);
    }
    result.addFirst(current);
}

4.結論
本論文では,ツリーと図の深さ優先探索について論じた.
完全なコードはGitHubを参照してください.
原文:https://www.baeldung.com/java-depth-first-search 作者:baeldung訳者:陳苓洪