Advertisement
Meetes

DFS

Mar 31st, 2020
211
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.44 KB | None | 0 0
  1.         /// <summary>
  2.         /// Depth first search implementation in c#
  3.         /// </summary>
  4.         /// <typeparam name="T">Type of tree structure item</typeparam>
  5.         /// <typeparam name="TChilds">Type of childs collection</typeparam>
  6.         /// <param name="node">Starting node to search</param>
  7.         /// <param name="ChildsProperty">Property to return child node</param>
  8.         /// <param name="Match">Predicate for matching</param>
  9.         /// <returns>The instance of matched result, null if not found</returns>
  10.         public static T DepthFirstSearch<T, TChilds>(this T node, Func<T, TChilds> ChildsProperty, Predicate<T> Match)
  11.             where T : class
  12.         {
  13.             if (!(ChildsProperty(node) is IEnumerable<T>))
  14.                 throw new ArgumentException("ChildsProperty must be IEnumerable<T>");
  15.  
  16.             Stack<T> stack = new Stack<T>();
  17.             stack.Push(node);
  18.             while (stack.Count > 0)
  19.             {
  20.                 T thisNode = stack.Pop();
  21. #if DEBUG
  22.                 System.Diagnostics.Debug.WriteLine(thisNode.ToString());
  23. #endif
  24.                 if (Match(thisNode))
  25.                     return thisNode;
  26.                 if (ChildsProperty(thisNode) != null)
  27.                 {
  28.                     foreach (T child in (ChildsProperty(thisNode) as IEnumerable<T>).Reverse())
  29.                         stack.Push(child);
  30.                 }
  31.             }
  32.             return null;
  33.         }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement