# Breadth- and Depth- First Search in C#

Another recreational implementation for review! As a side comment, for some reason I just feel like if (visited.Contains(vertex)) { .. } isn't necessary, as this example doesn't break from not including it in either algorithm. Any feedback is welcome!

Graph.cs

using System;
using System.Collections.Generic;

namespace CodeReview
{
public class Graph<T>
{
public Dictionary<T, HashSet<T>> AdjacencyList { get; } = new Dictionary<T, HashSet<T>>();

public Graph() { }

public Graph(IEnumerable<T> vertices, IEnumerable<Tuple<T, T>> edges)
{
foreach (var vertex in vertices)
{
}

foreach (var edge in edges)
{
}
}

{
}

{
{
}
}
}
}


Program.cs

using System;
using System.Collections.Generic;

namespace CodeReview
{
class Program
{
public static void Main(string[] args)
{
var vertices = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
var edges = new[] {
Tuple.Create(1, 2),
Tuple.Create(1, 3),
Tuple.Create(2, 4),
Tuple.Create(3, 5),
Tuple.Create(3, 6),
Tuple.Create(4, 7),
Tuple.Create(5, 7),
Tuple.Create(5, 8),
Tuple.Create(5, 6),
Tuple.Create(8, 9),
Tuple.Create(9, 10)
};

var graph = new Graph<int>(vertices, edges);

Console.WriteLine(string.Join(", ", BFS(graph, 1)));
// 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Console.WriteLine(string.Join(", ", DFS(graph, 1)));
// 1, 3, 6, 5, 8, 9, 10, 7, 4, 2

}

// using HashSet for O(1) access and loop operations
public static HashSet<T> BFS<T>(Graph<T> graph, T start)
{
var visited = new HashSet<T>();

{
return visited;
}

var queue = new Queue<T>();
queue.Enqueue(start);

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

if (visited.Contains(vertex))
{
continue;
}

{
if (!visited.Contains(neighbor))
{
queue.Enqueue(neighbor);
}
}
}

return visited;
}

// using HashSet for O(1) access and loop operations
public static HashSet<T> DFS<T>(Graph<T> graph, T start)
{
var visited = new HashSet<T>();

{
return visited;
}

var stack = new Stack<T>();
stack.Push(start);

while (stack.Count > 0)
{
var vertex = stack.Pop();

if (visited.Contains(vertex))
{
continue;
}

{
if (!visited.Contains(neighbor))
{
stack.Push(neighbor);
}
}
}

return visited;
}
}
}


First off, I think the static search methods should not be static but rather methods in the Graph class. Both methods look very similar, other than the fact that one uses a Queue and the other a Stack. In the interest of being DRY this can be modified using an interface.

I also find it needless to pass in the vertices along with edges. By virtue of passing in an edge, you know your vertices.

Since AdjacencyList is public, I suggest making it an IDictionary.

An interface for a searcher is simple:

interface IEdgeSearcher<T>
{
int Count { get; }
T GetNext();
}


The 2 different search classes implementing the interface could be private to Graph:

private class SearchQueue<TSearch> : IEdgeSearcher<TSearch>
{
private Queue<TSearch> _queue;
private SearchQueue() { _queue = new Queue<TSearch>(); }
public static SearchQueue<T> Create() => new SearchQueue<T>();
public void Add(TSearch item) { _queue.Enqueue(item); }
public int Count => _queue.Count;
public TSearch GetNext() => _queue.Dequeue();
}

private class SearchStack<TSearch> : IEdgeSearcher<TSearch>
{
private Stack<TSearch> _stack;
private SearchStack() { _stack = new Stack<TSearch>(); }
public static SearchStack<TSearch> Create() => new SearchStack<TSearch>();
public void Add(TSearch item) { _stack.Push(item); }
public int Count => _stack.Count;
public TSearch GetNext() => _stack.Pop();
}


Back in Graph you would call a respective searcher with one line:

public HashSet<T> BreadthFirstSearch(T start) => Search(SearchQueue<T>.Create(), start);
public HashSet<T> DepthFirstSearch(T start) => Search(SearchStack<T>.Create(), start);


Those are public, but call a new private method that expects the interface:

private HashSet<T> Search(IEdgeSearcher<T> searcher, T start)
{
var visited = new HashSet<T>();

{
return visited;
}

while (searcher.Count > 0)
{
var vertex = searcher.GetNext();

{
if (!visited.Contains(neighbor))
{
}
}
}

return visited;
}


Bringing it all together, the modified Graph would look like:

public class Graph<T>
{
public IDictionary<T, HashSet<T>> AdjacencyList { get; } = new Dictionary<T, HashSet<T>>();

public Graph() { }

public Graph(IEnumerable<Tuple<T, T>> edges)
{
foreach (var edge in edges)
{
}
}

{
}

{
}

public HashSet<T> BreadthFirstSearch(T start) => Search(SearchQueue<T>.Create(), start);
public HashSet<T> DepthFirstSearch(T start) => Search(SearchStack<T>.Create(), start);

private HashSet<T> Search(IEdgeSearcher<T> searcher, T start)
{
var visited = new HashSet<T>();

{
return visited;
}

while (searcher.Count > 0)
{
var vertex = searcher.GetNext();

{
if (!visited.Contains(neighbor))
{
}
}
}

return visited;
}

private class SearchQueue<TSearch> : IEdgeSearcher<TSearch>
{
private Queue<TSearch> _queue;
private SearchQueue() { _queue = new Queue<TSearch>(); }
public static SearchQueue<T> Create() => new SearchQueue<T>();
public void Add(TSearch item) { _queue.Enqueue(item); }
public int Count => _queue.Count;
public TSearch GetNext() => _queue.Dequeue();
}

private class SearchStack<TSearch> : IEdgeSearcher<TSearch>
{
private Stack<TSearch> _stack;
private SearchStack() { _stack = new Stack<TSearch>(); }
public static SearchStack<TSearch> Create() => new SearchStack<TSearch>();
public void Add(TSearch item) { _stack.Push(item); }
public int Count => _stack.Count;
public TSearch GetNext() => _stack.Pop();
}
}