C# で深さ優先検索アルゴリズムを実装する方法

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

#深さ優先検索 (DFS) は、一般的に使用されるグラフ走査アルゴリズムであり、アルゴリズムの 1 つとして使用されます。ツリーまたはグラフの走査または検索に使用します。 C# では、深さ優先検索アルゴリズムを再帰的に実装できます。この記事では、C# で深さ優先検索アルゴリズムを実装する方法と、関連するコード例を紹介します。

1. アルゴリズム的思考

深さ優先検索アルゴリズムは、頂点から開始し、最も深い点に到達するまで徐々に下に移動し、その後、前の頂点に戻り、その後、次の頂点を選択します。訪問されていない隣接する頂点は、すべての頂点が訪問されるまでトラバースされ続けます。特定の実装は、関数を再帰的に継続的に呼び出す再帰を使用して実現できます。

2. アルゴリズムの実装

以下では、簡単な例を使用して、C# で深さ優先検索アルゴリズムを実装する方法を説明します。接続されたグラフの隣接行列があるとします。目標は、指定された開始頂点から開始してグラフ全体を走査してすべての頂点を見つけることです。以下は、深さ優先検索アルゴリズムを実装するコード例です。

using System;
using System.Collections.Generic;

namespace DFSExample
{
    class Program
    {
        static int[][] graph;
        static bool[] visited;

        static void Main(string[] args)
        {
            // 初始化邻接矩阵
            InitializeGraph();

            // 初始化visited数组
            visited = new bool[graph.Length];

            // 从顶点0开始遍历
            DFS(0);

            Console.ReadLine();
        }

        static void InitializeGraph()
        {
            // 定义邻接矩阵
            graph = new int[][]
            {
                new int[] {0, 1, 1, 0, 0, 0},
                new int[] {1, 0, 0, 1, 1, 0},
                new int[] {1, 0, 0, 0, 0, 1},
                new int[] {0, 1, 0, 0, 0, 0},
                new int[] {0, 1, 0, 0, 0, 0},
                new int[] {0, 0, 1, 0, 0, 0}
            };
        }

        static void DFS(int vertex)
        {
            // 标记当前顶点为已访问
            visited[vertex] = true;
            Console.WriteLine("Visited vertex: " + vertex);

            // 遍历当前顶点的邻接顶点
            for (int i = 0; i < graph.Length; i++)
            {
                if (graph[vertex][i] == 1 && !visited[i])
                {
                    DFS(i);
                }
            }
        }
    }
}

このコードは、単純な深さ優先検索アルゴリズムを実装します。まず、グラフの接続性を表す隣接行列を定義します。次に、各頂点の訪問ステータスを記録するために訪問済み配列が定義されます。 DFS 関数では、まず現在の頂点が訪問済みとしてマークされ、現在の頂点の値が出力されます。次に、現在の頂点の隣接する頂点をトラバースします。隣接する頂点がまだ訪問されていない場合は、すべての頂点が訪問されるまで DFS 関数を再帰的に呼び出し続けます。

3. 実行結果

上記のコードを実行すると、次の出力結果が得られます:

Visited vertex: 0
Visited vertex: 1
Visited vertex: 3
Visited vertex: 4
Visited vertex: 2
Visited vertex: 5

これらの出力結果は、開始頂点 0 からの開始を表します。によると、深さ優先検索アルゴリズムは各頂点を順番に訪問します。

概要

この記事では、C# で深さ優先検索アルゴリズムを実装する方法を紹介し、関連するコード例を示します。深さ優先検索アルゴリズムは、グラフまたはツリーを横断するために再帰的に簡単に実装できます。深さ優先検索アルゴリズムは、グラフ接続性の判断、トポロジカル ソートなど、多くのアプリケーション シナリオで広く使用されています。読者は、この記事のコード例に基づいて、さらなる拡張機能やアプリケーションを作成できます。

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