DepthFirstSearch.cs

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

namespaceAlgorithms.Graph;

/// <summary>
/// Depth First Search - algorithm for traversing graph.
/// Algorithm starts from root node that is selected by the user.
/// Algorithm explores as far as possible along each branch before backtracking.
/// </summary>
/// <typeparam name="T">Vertex data type.</typeparam>
publicclassDepthFirstSearch<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)
{
Dfs(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>
privatevoidDfs(IDirectedWeightedGraph<T>graph,Vertex<T>startVertex,Action<Vertex<T>>?action,HashSet<Vertex<T>>visited)
{
action?.Invoke(startVertex);

visited.Add(startVertex);

foreach(varvertexingraph.GetNeighbors(startVertex))
{
if(vertex==null||visited.Contains(vertex))
{
continue;
}

Dfs(graph,vertex!,action,visited);
}
}
}