C++ で深さ優先検索アルゴリズムを使用する方法

C で深さ優先検索アルゴリズムを使用する方法

深さ優先検索 (DFS) アルゴリズムは、グラフまたはツリーを走査または検索するためのアルゴリズムです。から開始します。 ルート ノードから開始して、これ以上進めなくなるまでグラフのブランチをできるだけ深く探索し、その後、戻って他のブランチを探索します。 DFS は、グラフの接続性の検出、グラフのサイクルの検出、すべての可能なパスの生成と出力など、多くの問題に対する非常に便利なソリューションです。

この記事では、C で深さ優先検索アルゴリズムを実装する方法を紹介し、具体的なコード例を使用して説明します。

深さ優先検索の基本的な考え方は、再帰またはスタックを使用して、トラバースする必要があるノードを保存することです。以下は、隣接行列で表されるグラフの DFS アルゴリズムのサンプル コードです。

#include <iostream>
#include <stack>

using namespace std;

const int MAX = 100;
bool visited[MAX];
int graph[MAX][MAX];
int numVertices;

void dfs(int start) {
    stack<int> s;
    visited[start] = true;
    cout << start << " ";

    s.push(start);

    while (!s.empty()) {
        int current = s.top();
        s.pop();

        for (int i = 0; i < numVertices; i++) {
            if (graph[current][i] == 1 && !visited[i]) {
                visited[i] = true;
                cout << i << " ";
                s.push(i);
            }
        }
    }
}

int main() {
    int numEdges, start;

    cout << "Enter the number of vertices: ";
    cin >> numVertices;
    cout << "Enter the number of edges: ";
    cin >> numEdges;

    for (int i = 0; i < numEdges; i++) {
        int u, v;
        cout << "Enter edge (u, v): ";
        cin >> u >> v;
        graph[u][v] = 1;
        graph[v][u] = 1; // Assuming undirected graph
    }

    cout << "Enter the starting vertex for DFS: ";
    cin >> start;

    dfs(start);

    return 0;
}

上記のサンプル コードでは、最初にグローバル 2 次元隣接行列 graph を定義します。 andvisited配列は、ノードが訪問されたかどうかをマークするために使用されます。次に、深さ優先検索を実装するための dfs() 関数を定義しました。この関数はスタックを使用して、トラバースする必要があるノードを保存します。まず、開始ノードがスタックにプッシュされ、訪問済みとしてマークされます。次にループに入り、毎回スタックからノードを取り出し、そのノードの隣接ノードを巡回します。隣接ノードが訪問されていない場合は、その隣接ノードがスタックにプッシュされ、訪問済みとしてマークされます。このプロセスは、スタックが空になるまで継続されます。最後に、main() 関数を使用してグラフ情報を読み取り、dfs() 関数を呼び出して深さ優先検索を実行します。

上記のコード例は、深さ優先検索アルゴリズムの単純な適用にすぎません。実際、このアルゴリズムは、再帰的実装の使用、カラー マーキングの使用など、いくつかのテクニックを通じて最適化することもできます。

深さ優先探索アルゴリズムは、さまざまなグラフ理論の問題を解決するのに非常に効果的であり、実際のアプリケーションで広く使用されています。 DFS アルゴリズムの実装に習熟していれば、グラフ理論を理解し、関連する問題を解決するのに非常に役立ちます。

概要:

この記事では、C で深さ優先検索アルゴリズムを実装する方法を紹介し、具体的なコード例を示します。深さ優先探索アルゴリズムは、グラフの分岐を走査または検索することによって、多くのグラフ関連の問題を解決できる重要なグラフ理論アルゴリズムです。 DFS アルゴリズムをマスターすることは、グラフ理論を理解し、関連する問題を解決するのに非常に役立ちます。

以上がC++ で深さ優先検索アルゴリズムを使用する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。