BreadthFirstSearch.cs

usingSystem;
usingSystem.Collections.Generic;
usingDataStructures.Graph;

namespaceAlgorithms.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>
publicclassBreadthFirstSearch<T>:IGraphSearch<T>whereT: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>
publicvoidVisitAll(IDirectedWeightedGraph<T>graph,Vertex<T>startVertex,Action<Vertex<T>>?action=default)
{
Bfs(graph,startVertex,action,newHashSet<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>
privatevoidBfs(IDirectedWeightedGraph<T>graph,Vertex<T>startVertex,Action<Vertex<T>>?action,HashSet<Vertex<T>>visited)
{
varqueue=newQueue<Vertex<T>>();

queue.Enqueue(startVertex);

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

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

foreach(varvertexingraph.GetNeighbors(currentVertex))
{
queue.Enqueue(vertex!);
}

action?.Invoke(currentVertex);

visited.Add(currentVertex);
}
}
}