6.3.2 Algoritmos de recorrido y búsqueda A lo ancho

6.3.2 Algoritmos de recorrido y búsqueda A lo ancho

Es un método para explorar un árbol o gráfico. En un BFS, primero explora todos los nodos a un paso, luego todos los nodos a dos pasos, etc.

La búsqueda en primer lugar es como tirar una piedra en el centro de un estanque. Los nodos que exploras "ondulan" desde el punto de partida.

Aquí hay una descripción de cómo un BFS atravesaría este árbol, comenzando con la raíz:

En la primera imagen de la figura anterior, hemos comenzado con el nodo más alto.

En la segunda imagen, recorremos todos los nodos presentes en el segundo nivel. En la tercera imagen, todos los nodos presentes en el tercer nivel y así sucesivamente. Hasta que lleguemos al final.

Ventajas:

·         Un BFS encontrará la  ruta más corta  entre el punto de inicio y cualquier otro nodo accesible. Una búsqueda en profundidad no necesariamente encontrará el camino más corto.

Desventajas

·         Un BFS en un árbol binario  generalmente  requiere más memoria que un DFS.

Ejemplo BFS de búsqueda en C#

En el siguiente código, he intentado crear la misma estructura que se muestra en la siguiente figura.

static void Main(string[] args)

        {

            Node topNode = new Node() { Value = 1 };

            topNode.Neighbours.Add(new Node() { Value = 2, Neighbours = new List<Node> { new Node() { Value = 5, Neighbours = new List<Node> { new Node() { Value = 9 } } } } });

            topNode.Neighbours.Add(new Node() { Value = 3, Neighbours = new List<Node> { new Node() { Value = 6, Neighbours = new List<Node>() { new Node() { Value = 10 } } }, new Node() { Value = 7 } } });

            topNode.Neighbours.Add(new Node() { Value = 4, Neighbours = new List<Node>() { new Node() { Value = 8 } } });

            Queue<Node> queue = new Queue<Node>();

            queue.Enqueue(topNode);

            while (queue.Count > 0)

            {

               var element =  queue.Dequeue();

                if (element.Neighbours.Count > 0)

                {

                    Console.WriteLine(element.Value);

                    foreach (var item in element.Neighbours)

                    {

                        queue.Enqueue(item);

                    }

                }

                else

                    Console.WriteLine(element.Value);

            }

            Console.Read();

        }

        public class Node

        {

            public Node()

            {

                Neighbours = new List<Node>();

            }

            public int Value { get; set; }

            public IList<Node> Neighbours { get; set; }

        }