Comment implémenter un algorithme de recherche en profondeur en C#

Comment implémenter l'algorithme de recherche en profondeur en C#

Depth First Search (DFS) est un algorithme de traversée de graphes couramment utilisé. C'est l'un des algorithmes utilisés pour parcourir ou rechercher un arbre ou un graphique. En C#, nous pouvons implémenter de manière récursive l’algorithme de recherche en profondeur. Cet article explique comment implémenter l'algorithme de recherche en profondeur en C# et donne des exemples de code pertinents.

1. Idée d'algorithme

L'algorithme de recherche en profondeur commence à partir d'un sommet, traverse progressivement vers le bas jusqu'à ce qu'il atteigne le point le plus profond, puis revient au sommet précédent, puis sélectionne le prochain sommet adjacent non visité pour continuer à parcourir jusqu'à tous les sommets. ont été visités. L'implémentation spécifique peut être réalisée en utilisant la récursion, en appelant continuellement des fonctions de manière récursive.

2. Implémentation de l'algorithme

Ci-dessous, nous utilisons un exemple simple pour illustrer comment implémenter l'algorithme de recherche en profondeur d'abord en C#. Supposons que nous ayons une matrice de contiguïté d'un graphe connecté et que notre objectif soit de partir d'un sommet de départ donné et de parcourir l'intégralité du graphe pour trouver tous les sommets. Voici un exemple de code qui implémente un algorithme de recherche en profondeur d'abord :

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

Ce code implémente un algorithme de recherche simple en profondeur d'abord. Nous définissons d'abord une matrice d'adjacence pour représenter la connectivité du graphe. Ensuite, un tableau visité est défini pour enregistrer l'état de visite de chaque sommet. Dans la fonction DFS, le sommet actuel est d'abord marqué comme visité et la valeur du sommet actuel est affichée. Parcourez ensuite les sommets adjacents du sommet actuel. Si les sommets adjacents n'ont pas été visités, continuez à appeler la fonction DFS de manière récursive jusqu'à ce que tous les sommets aient été visités.

3. Résultats d'exécution

En exécutant le code ci-dessus, vous pouvez obtenir les résultats de sortie suivants :

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

Ces résultats de sortie représentent le processus de visite de chaque sommet en séquence à partir du sommet de départ 0 selon l'algorithme de recherche en profondeur d'abord. .

Résumé

Cet article présente comment implémenter l'algorithme de recherche en profondeur d'abord en C# et donne des exemples de code pertinents. Les algorithmes de recherche en profondeur peuvent être facilement implémentés de manière récursive pour parcourir un graphique ou un arbre. Les algorithmes de recherche en profondeur sont largement utilisés dans de nombreux scénarios d'application, tels que le jugement de connectivité graphique, le tri topologique, etc. Les lecteurs peuvent créer d'autres extensions et applications basées sur les exemples de code contenus dans cet article.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!