BreadthFirstSearch.cs

using System;
using System.Collections.Generic;
using DataStructures.Graph;

namespace Algorithms.Graph
{
    /// <summary>
    /// Breadth First Search - algorithm for traversing graph.
    /// Algorithm starts from root node that is selected by the user.
    /// Algorithm explores all nodes at the present depth.
    /// </summary>
    /// <typeparam name="T">Vertex data type.</typeparam>
    public class BreadthFirstSearch<T> : IGraphSearch<T> where T : IComparable<T>
    {
        /// <summary>
        /// Traverses graph from start vertex.
        /// </summary>
        /// <param name="graph">Graph instance.</param>
        /// <param name="startVertex">Vertex that search starts from.</param>
        /// <param name="action">Action that needs to be executed on each graph vertex.</param>
        public void VisitAll(IDirectedWeightedGraph<T> graph, Vertex<T> startVertex, Action<Vertex<T>>? action = default)
        {
            Bfs(graph, startVertex, action, new HashSet<Vertex<T>>());
        }

        /// <summary>
        /// Traverses graph from start vertex.
        /// </summary>
        /// <param name="graph">Graph instance.</param>
        /// <param name="startVertex">Vertex that search starts from.</param>
        /// <param name="action">Action that needs to be executed on each graph vertex.</param>
        /// <param name="visited">Hash set with visited vertices.</param>
        private void Bfs(IDirectedWeightedGraph<T> graph, Vertex<T> startVertex, Action<Vertex<T>>? action, HashSet<Vertex<T>> visited)
        {
            var queue = new Queue<Vertex<T>>();

            queue.Enqueue(startVertex);

            while (queue.Count > 0)
            {
                var currentVertex = queue.Dequeue();

                if (currentVertex == null || visited.Contains(currentVertex))
                {
                    continue;
                }

                foreach (var vertex in graph.GetNeighbors(currentVertex))
                {
                    queue.Enqueue(vertex!);
                }

                action?.Invoke(currentVertex);

                visited.Add(currentVertex);
            }
        }
    }
}