Bagaimana untuk melaksanakan algoritma carian mendalam-pertama dalam C#

Cara melaksanakan algoritma carian mendalam-pertama dalam C#

Depth First Search (DFS) ialah algoritma traversal graf yang biasa digunakan Ia adalah salah satu algoritma yang digunakan untuk merentasi atau mencari pokok atau graf. Dalam C#, kita boleh melaksanakan algoritma carian kedalaman pertama secara rekursif. Artikel ini akan memperkenalkan cara melaksanakan algoritma carian pertama mendalam dalam C# dan memberikan contoh kod yang berkaitan.

1. Idea algoritma

Algoritma carian kedalaman pertama bermula dari bucu, secara beransur-ansur merentasi ke bawah sehingga mencapai titik paling dalam, kemudian berundur ke bucu sebelumnya, dan kemudian memilih bucu bersebelahan yang tidak dilawati seterusnya untuk meneruskan perjalanan sehingga semua bucu telah dilawati. Pelaksanaan khusus boleh dicapai menggunakan rekursi, dengan terus memanggil fungsi secara rekursif.

2. Implementasi Algoritma

Di bawah ini kami menggunakan contoh mudah untuk menggambarkan cara melaksanakan algoritma carian kedalaman pertama dalam C#. Katakan kita mempunyai matriks bersebelahan graf yang disambungkan, dan matlamat kita adalah untuk bermula dari bucu permulaan yang diberikan dan melintasi keseluruhan graf untuk mencari semua bucu. Berikut ialah contoh kod yang melaksanakan algoritma carian mendalam-dahulu:

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);
                }
            }
        }
    }
}

Kod ini melaksanakan algoritma carian mendalam-dahulu yang mudah. Kami mula-mula mentakrifkan matriks bersebelahan untuk mewakili ketersambungan graf. Kemudian tatasusunan yang dilawati ditakrifkan untuk merekodkan status lawatan setiap bucu. Dalam fungsi DFS, puncak semasa mula-mula ditanda sebagai dilawati dan nilai puncak semasa adalah output. Kemudian lintasi bucu bersebelahan bucu semasa Jika bucu bersebelahan belum dilawati, teruskan memanggil fungsi DFS secara rekursif sehingga semua bucu telah dilawati.

3. Menjalankan hasil

Menjalankan kod di atas, anda boleh mendapatkan hasil keluaran berikut:

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

Hasil keluaran ini mewakili proses melawat setiap bucu dalam urutan bermula dari bucu permulaan 0 mengikut algoritma carian kedalaman pertama .

Ringkasan

Artikel ini memperkenalkan cara melaksanakan algoritma carian pertama mendalam dalam C# dan memberikan contoh kod yang berkaitan. Algoritma carian mendalam-pertama boleh dilaksanakan dengan mudah secara rekursif untuk melintasi graf atau pokok. Algoritma carian kedalaman pertama digunakan secara meluas dalam banyak senario aplikasi, seperti pertimbangan ketersambungan graf, pengisihan topologi, dsb. Pembaca boleh membuat sambungan dan aplikasi lanjut berdasarkan contoh kod dalam artikel ini.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma carian mendalam-pertama dalam C#. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!