Java の DFS アルゴリズム

DFS アルゴリズムは、深さ優先検索と略される検索アルゴリズムとして定義されるトラバーサル アルゴリズムです。これは、グラフ構造のように見えるツリー構造内で検索を行うため、グラフ アルゴリズムとしても知られており、ルートとトラバース、およびさまざまなブランチを含む以下のグラフ。一般に、Java の DFS アルゴリズムは、ツリーまたはグラフ構造をトラバースするトラバーサル アルゴリズムとして定義されます。このアルゴリズムは、始点のルート ノードから開始して、最後のブランチの最後のノードに到達するまで各ブランチを深く掘り下げていきます。このような検索は知られています。これは、深さ優先検索として機能し、プリオーダー、インオーダー、ポストオーダーのトラバーサル検索など、3 つの異なる方法の DFS を提供します。

無料ソフトウェア開発コースを始めましょう

Web 開発、プログラミング言語、ソフトウェア テスト、その他

アルゴリズム:

DFS は非最適解をもたらす統一アルゴリズムであり、DFS アルゴリズムは次のように動作します。

ステップ 1: 任意のグラフまたはツリーのルート ノードから開始します。

ステップ 2: 次に、ルート ノードをグラフの最初のノードとして考慮し、このノードをスタックまたはリストの先頭に配置します。

ステップ 3: 次に、最初のノードであるルート ノードの隣接ノードを探し、これらの隣接ノードを隣接ノード リストの他のリストに追加します。

ステップ 4: 次に、ルート ノードの後のスタックまたはリスト内の各ノードの隣接ノードを追加します。

ステップ 5: グラフ内の最後の分岐の終了ノードに到達するか、隣接するノードのリストが空になるまで、ステップ 3 から 4 を続けます。

そこで、JavaにおけるDFSアルゴリズムは、先頭ノードから終点ノードまでを深く探索する横断探索アルゴリズムの一つです。ただし、左の分岐を経由するか右の分岐を経由するかにかかわらず、グラフを移動するときに混乱することがあります。これを解決するために、指定された順序に従ってツリーを横断するための 3 つの異なるタイプの DFS preorder、inorder、postorder が用意されています。

DFS アルゴリズムは例でどのように機能しますか?

Java では、DFS アルゴリズムは上記のアルゴリズムに従って機能します。無向グラフの DFS アルゴリズムは、ルート ノードから開始します。まずこのルート ノードを、訪問されたノードを保持する訪問先スタックとみなせる 1 つのスタックに配置し、次にルート ノードのすべての隣接ノードをこのスタックに配置します。ルートノードが存在するスタックを訪問しました。次に、グラフを横断して、各ルートの隣接ノードの隣接ノードを見つけます。グラフの最後のノードまで続行し、すべてのノードを別のスタックに配置してこれらのノードを横断します。これにより、検索が完了すると、訪問したスタックが表示されます。グラフ内を通過したノード。

例 #1

次に、切断されたグラフ上に Java プログラミング言語で実装された簡単な DFS アルゴリズムの例を見てみましょう。

コード:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class vertex
{
int root, dest;
public vertex(int root, int dest)
{
this.root = root;
this.dest = dest;
}
}
class graphstruc
{
List<List<Integer>> adjList = null;
graphstruc(List<vertex> v, int N)
{
adjList = new ArrayList<>();
for (int i = 0; i < N; i++) {
adjList.add(new ArrayList<>());
}
for (vertex e: v)
{
int src = e.root;
int dest = e.dest;
adjList.get(src).add(dest);
adjList.get(dest).add(src);
}
}
}
class Main
{
public static void DFS(graphstruc graph, int v, boolean[] d)
{
d[v] = true;
System.out.print(v + " ");
for (int u: graph.adjList.get(v))
{
if (!d[u]) {
DFS(graph, u, d);
}
}
}
public static void main(String[] args)
{
List<vertex> v = Arrays.asList(
new vertex(1, 2), new vertex(1, 7), new vertex(1, 8),
new vertex(2, 3), new vertex(2, 6), new vertex(3, 4),
new vertex(3, 5), new vertex(8, 9), new vertex(8, 12),
new vertex(9, 10), new vertex(9, 11), new vertex(10, 12),
new vertex(10, 13), new vertex(11, 14)
);
final int N = 15;
graphstruc g = new graphstruc(v, N);
boolean[] d = new boolean[N];
System.out.println("Demonstration of Depth First Search algorithm in Java is as follows:");
for (int i = 0; i < N; i++)
{
if (!d[i]) {
DFS(g, i, d);
}
}
}
}

出力:

上記の例では、まずクラス頂点を定義し、このクラス頂点がグラフの頂点を格納するグラフ内のルート頂点と宛先頂点を宣言します。次に、クラス chartstruc を定義してルート ノードの隣接する頂点を宣言し、これらの隣接するノードをリストに追加します。隣接する頂点を保存し、後でこれらの頂点の隣接する頂点をリストに追加します。次に、DFS を実行するために、指定されたグラフから現在のノードを識別するクラス DFS を宣言し、各ノードの隣接ノードを識別し、隣接リスト ノードを追加します。最後に、メイン クラスで、グラフ頂点のリストをノードの総数とともに配列として定義します。DFS 関数を呼び出した後、上のスクリーンショットに示すように、DFS 検索リストにリストが表示されます。 、これが出力です。

例 #2

次に、Java でのプレオーダー、インオーダー、ポストオーダー トラバーサルなど、さまざまな種類のトラバーサル順序を使用した DFS 実装を見てみましょう。以下では、Java でのプリオーダー実装を見ていきます。

コード:

class vertex
{
int data;
vertex l, r;
public vertex(int k)
{
data = k;
l = r = null;
}
}
class Main
{
public static void preorder(vertex root)
{
if (root == null) {
return;
}
System.out.print(root.data + " ");
preorder(root.l);
preorder(root.r);
}
public static void main(String[] args)
{
vertex root = new vertex(2);
root.l = new vertex(3);
root.r = new vertex(1);
root.l.l = new vertex(6);
root.r.l = new vertex(4);
root.r.r = new vertex(5);
root.r.l.l = new vertex(8);
root.r.l.r = new vertex(7);
preorder(root);
}
}

出力:

上記の例も前の例と似ていますが、唯一の違いは DFS アルゴリズムでトラバース順序を定義していることです。ここでは、プリオーダー走査順序のみを定義しています。これを定義すると、ルート ノード、左ノード、右ノードの順序で深さ優先グラフを走査します。したがって、ここでは、ノード 2 をルート ノードとして宣言し、ノード 3 を左ノードとして、ノード 6 を右ノードとして宣言するなどとします。出力は上のスクリーンショットに示されているとおりです。

結論

この記事では、Java の DFS アルゴリズムは、最後のノードに到達するまでグラフを深く検索または検索するトラバーサル アルゴリズムであると結論付けています。 DFS アルゴリズムの時間計算量は通常 O(E+V) で表されます。E はグラフのエッジ、V は頂点を表します。 DFS アルゴリズムには、グラフ内で順列、前順、後順の DFS 走査として分類される走査順序に基づいて、さまざまなアプリケーションが多数あります。

以上がJava の DFS アルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。