DepthFirstSearch.cs

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

namespace Algorithms.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>
    public class DepthFirstSearch<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)
        {
            Dfs(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 Dfs(IDirectedWeightedGraph<T> graph, Vertex<T> startVertex, Action<Vertex<T>>? action, HashSet<Vertex<T>> visited)
        {
            action?.Invoke(startVertex);

            visited.Add(startVertex);

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

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