Javaでの深さ優先検索
-
link:/tag/data-structures/ [データ構造]
1. 概要
このチュートリアルでは、Javaでの深さ優先検索について説明します。
深さ優先検索(DFS)は、ツリーとグラフの両方のデータ構造に使用されるトラバーサルアルゴリズムです。 深さ優先**検索は、別のブランチを探索するために移動する前に各ブランチで深くなります**
次のセクションでは、最初にツリーの実装、次にグラフの実装を見ていきます。
これらの構造をJavaで実装する方法については、https://www.baeldung.com/java-binary-tree [Binary Tree]およびlink:/java-の以前のチュートリアルをご覧ください。グラフ[グラフ]。
2. ツリーの深さ優先検索
DFSを使用してツリーをトラバースするには、3つの異なる順序があります。
-
先行予約のトラバーサル
-
順序通りの横断
-
後順走査
2.1. 先行予約のトラバーサル
*前順序走査では、最初にルートを走査し、次に左右のサブツリーを走査します。*
単純に*再帰を使用して事前順序走査を実装できます*:
-
_current_ノードにアクセス
-
_left_サブツリーをトラバースする
-
_right_サブツリーをトラバースする
public void traversePreOrder(Node node) {
if (node != null) {
visit(node.value);
traversePreOrder(node.left);
traversePreOrder(node.right);
}
}
また、再帰なしで事前順序走査を実装することもできます。
*反復的な事前順序走査を実装するには、_Stack_ *が必要です。次の手順を実行します。
-
_root_をstackにプッシュします
-
_stack_は空ではありませんが
-
_current_ノードをポップ
-
_current_ノードにアクセス
-
_right_子を押し、次に_left_子を_stack_に押します
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);
}
}
また、*再帰なしで順序走査を実装することもできます*。
-
_root_ノードを_stack_にプッシュします
-
stackは空ではありませんが
-
_current_に達するまで、_left_子を_stack_に押し続けます
ノードの左端の子 -
_current_ノードにアクセス
-
_right_子を_stack_にプッシュします
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);
}
}
または、*再帰なしで後順走査を実装することもできます*:
-
_stack_の_root_ノードをプッシュします
-
stackは空ではありませんが
-
左と右のサブツリーをすでに横断しているかどうかを確認します
-
そうでない場合は、right childおよび_left_ childを_stack_にプッシュします
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の2つの実装が表示されます。
3.1. 再帰を使用したグラフDFS
まず、再帰から始めましょう:
-
指定されたノードから開始します
-
_current_ノードを訪問済みとしてマークする
-
_current_ノードにアクセス
-
未訪問の隣接する頂点をトラバースする
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を実装することもできます。 単に_Stack_を使用します:
-
指定されたノードから開始します
-
_start_ノードを_stack_にプッシュします
-
_Stack_は空ではありませんが
-
_current_ノードを訪問済みとしてマークする
-
_current_ノードにアクセス
-
訪れていない隣接する頂点をプッシュする
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. トポロジカルソート
グラフの深さ優先検索には多くのアプリケーションがあります。 DFSの有名なアプリケーションの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. 結論
この記事では、ツリーとグラフの両方のデータ構造の深さ優先検索について説明しました。
完全なソースコードはhttps://github.com/eugenp/tutorials/tree/master/data-structures[GitHub]で入手できます。