Maison  >  Article  >  développement back-end  >  Comment écrire un algorithme de recherche en largeur en utilisant C#

Comment écrire un algorithme de recherche en largeur en utilisant C#

王林
王林original
2023-09-19 11:45:361279parcourir

Comment écrire un algorithme de recherche en largeur en utilisant C#

Comment écrire un algorithme de recherche en largeur en premier à l'aide de C#

La recherche en largeur d'abord (BFS) est un algorithme de recherche de graphique couramment utilisé qui permet de parcourir un graphique ou un arbre en fonction de la largeur. Dans cet article, nous explorerons comment écrire un algorithme de recherche en largeur en utilisant C# et fournirons des exemples de code concrets.

  1. Principe de l'algorithme
    Le principe de base de l'algorithme de recherche en largeur d'abord est de partir du point de départ de l'algorithme et d'étendre la plage de recherche couche par couche jusqu'à ce que la cible soit trouvée ou que l'ensemble du graphique soit parcouru. Il est généralement implémenté via des files d’attente.
  2. Implémentation du code
    Ce qui suit est un exemple de code pour écrire un algorithme de recherche en largeur en premier en utilisant C# :
using System;
using System.Collections.Generic;

public class BFS
{
    public class Node
    {
        public int value;
        public List<Node> neighbors;

        public Node(int v)
        {
            value = v;
            neighbors = new List<Node>();
        }
    }

    public static void BFSAlgorithm(Node start)
    {
        Queue<Node> queue = new Queue<Node>();
        HashSet<Node> visited = new HashSet<Node>();

        queue.Enqueue(start);
        visited.Add(start);

        while (queue.Count > 0)
        {
            Node node = queue.Dequeue();
            Console.Write(node.value + " ");

            foreach (Node neighbor in node.neighbors)
            {
                if (!visited.Contains(neighbor))
                {
                    queue.Enqueue(neighbor);
                    visited.Add(neighbor);
                }
            }
        }
    }

    public static void Main(string[] args)
    {
        Node node1 = new Node(1);

        Node node2 = new Node(2);
        Node node3 = new Node(3);
        node1.neighbors.Add(node2);
        node1.neighbors.Add(node3);

        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        node2.neighbors.Add(node4);
        node2.neighbors.Add(node5);
        node3.neighbors.Add(node6);

        BFSAlgorithm(node1);
    }
}

Dans le code ci-dessus, nous définissons d'abord une fonction Node类,用于表示图中的节点。节点包含一个值和一个邻居列表。BFSAlgorithm函数实现了广度优先搜索算法,其中使用一个队列来存储待处理的节点,并使用一个集合来记录已访问过的节点。算法从起点开始,将其加入队列和已访问集合,然后迭代处理队列中的节点,并将其邻居节点加入队列和已访问集合。最后,我们在程序的Main函数中创建了一个简单的图,并调用BFSAlgorithm à rechercher.

  1. Exemple de sortie
    La sortie du code ci-dessus est : 1 2 3 4 5 6. Indique que l'algorithme de recherche en largeur parcourt les nœuds du graphique dans l'ordre en commençant par 1.

Résumé :
Cet article explique comment utiliser C# pour écrire un algorithme de recherche en largeur et donne des exemples de code détaillés. En utilisant des files d'attente et des collections pour implémenter l'algorithme de recherche en largeur d'abord, nous pouvons parcourir en largeur dans un graphique ou un arbre pour trouver le nœud cible ou parcourir la structure entière. J'espère que les lecteurs pourront maîtriser les compétences de base nécessaires à l'écriture d'algorithmes de recherche étendus en C# grâce à 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!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn