Depth First Search

DepthFirstSearch.cs

void Main()
{
	// Define all the vertices in the graph
	var a = new Vertex<string>{ Value = "A" };
	var b = new Vertex<string>{ Value = "B" };
	var c = new Vertex<string>{ Value = "C" };
	var d = new Vertex<string>{ Value = "D" };
	var e = new Vertex<string>{ Value = "E" };
	var f = new Vertex<string>{ Value = "F" };
	var g = new Vertex<string>{ Value = "G" };
	var h = new Vertex<string>{ Value = "H" };
	var i = new Vertex<string>{ Value = "I" };
	var j = new Vertex<string>{ Value = "J" };
	var k = new Vertex<string>{ Value = "K" };
	var l = new Vertex<string>{ Value = "L" };
	
	// Associate neighbors
	a.Neighbors = new [] {b};
	b.Neighbors = new [] {c, f};
	c.Neighbors = new [] {g};
	f.Neighbors = new [] {j};
	g.Neighbors = new [] {f, h, d, k};
	h.Neighbors = new [] {l};
	i.Neighbors = new [] {e};
	j.Neighbors = new [] {i};
	
	var graph = new Graph<string>();
	
	var start = a;
	var lookFor = l;
	
	// Explore the graph
	var nodes = graph.DepthFirstSearch(start).Select(x => x.Value).Dump();
	
	// Do a topological sort
	var topologicalOrder = graph.TopologicalSort(start).Reverse().Dump();
	
	// Find a path
	var path = graph.FindPath(start, lookFor).Dump();
}

class Graph<T>
{	
	public IEnumerable<Vertex<T>> DepthFirstSearch(Vertex<T> vertex)
	{
		var result = new Dictionary<Vertex<T>, bool>();
		
		DepthFirstSearchVisit(vertex, result);
		
		return result.Keys;
	}
	private void DepthFirstSearchVisit(Vertex<T> vertex, Dictionary<Vertex<T>, bool> visited)
	{
		visited.Add(vertex, true);
		
		if(vertex.Neighbors == null) return;
		
		foreach(var neighbor in vertex.Neighbors)
		{
			if(!visited.ContainsKey(neighbor)) 
			{
				DepthFirstSearchVisit(neighbor, visited);
			}
		}
	}
	
	public Stack<T> TopologicalSort(Vertex<T> vertex)
	{
		var visited = new Dictionary<Vertex<T>, bool>();
		var result = new Stack<T>();
		TopologicalSort(vertex, visited, result);
		
		return result;
	}
	private void TopologicalSort(Vertex<T> vertex, Dictionary<Vertex<T>, bool> visited, Stack<T> result)
	{
		visited.Add(vertex, true);
		
		if(vertex.Neighbors == null) 
		{
			result.Push(vertex.Value);
			return;
		};
		
		foreach(var neighbor in vertex.Neighbors)
		{
			if(!visited.ContainsKey(neighbor)) 
			{
				TopologicalSort(neighbor, visited, result);
			}
		}
		
		result.Push(vertex.Value);
	}
	
	
	
	public IEnumerable<T> FindPath(Vertex<T> start, Vertex<T> end)
	{
		var result = new Dictionary<Vertex<T>, bool>();
		var path = new Stack<T>();
		
		FindPath(start, end, result, path);
		
		return path;
	}
	private void FindPath(Vertex<T> start, Vertex<T> end, Dictionary<Vertex<T>, bool> visited, Stack<T> path)
	{
		path.Push(start.Value);
		visited.Add(start, true);
		
		if(start.Neighbors == null) 
		{
			if(start != end) path.Pop();
			return;
		}
		
		
		foreach(var neighbor in start.Neighbors)
		{
			if(!visited.ContainsKey(neighbor)) 
			{
				FindPath(neighbor, end, visited, path);
			}
			if (visited.ContainsKey(end))
			{
				return;
			}
		}
		
		path.Pop();
	}
}

class Vertex<T>
{
	public IEnumerable<Vertex<T>> Neighbors {get; set;}
	public T Value {get; set;}
}