Skip to content

Instantly share code, notes, and snippets.

@riyadparvez
Last active March 15, 2019 08:11
Show Gist options
  • Select an option

  • Save riyadparvez/5915044 to your computer and use it in GitHub Desktop.

Select an option

Save riyadparvez/5915044 to your computer and use it in GitHub Desktop.
Iterative deepening search in C#. A rudimentary implementation of node is also provided
public class Tree<K, V>
where K : class, IComparable<K>
where V : class
{
private Node<K, V> root;
/// <summary>
/// Searches tree using BFS but the depth of the search
/// is limited. Level of root is 0.
/// </summary>
/// <param name="root">To start the search</param>
/// <param name="goal"></param>
/// <param name="depth">Maximum depth of level to search</param>
/// <returns>Default of V if key is not found</returns>
public V DepthLimitedSearch(Node<K, V> root, K goal, int depth)
{
if(depth == 0 && root.key == goal)
{
return root.value;
}
else if (depth > 0)
{
foreach (var child in root.children)
{
var result = DepthLimitedSearch(child, goal, depth-1);
if(result != default(V))
{
return result;
}
}
return default(V);
}
else
{
return default(V);
}
}
public V IterativeDeepeningSearch(K key, int depth)
{
for (int currentDepth = 0; currentDepth <= depth; currentDepth++)
{
var v = DepthLimitedSearch(root, key, currentDepth);
if(v != default(V))
{
return v;
}
}
return default(V);
}
private class Node<K, V>
where K : class, IComparable<K>
where V : class
{
public K key;
public V value;
public Node<K, V>[] children;
}
}
@campanate
Copy link

thanks , it's perfect!

@janhenk
Copy link

janhenk commented Mar 15, 2019

private class Node<K, V>
should be
public class Node<K, V>
to resolve inconsistent accessibility level

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment