# Depth-First Search Algorithm in C# and .NET Core

I am currently learning and using Python in my computer science and algorithms courses, but C# is the programming language I have been using for years. In this article I will be coding the depth-first search algorithm using C#. In particular, this is C# 6 running on .NET Core 1.1 on macOS, and I am coding with VS Code. If interested, you can also learn about breadth-first search in C#.

## Depth-First Search

Depth-first search is a useful algorithm for searching a graph. There are recursive and iterative versions of depth-first search, and in this article I am coding the iterative form. The iterative version of depth-first search requires an extra Stack Data Structure to keep track of vertices to visit, which is taken care of naturally in the recursive version.

Depth-first search will help answer the following question: Given an undirected graph, G, and a starting vertex, V, what vertices can V reach? This is a question of connectivity, which can be very useful when mapping networks, web pages, social networks, etc.

## Undirected Graph Modeled as Adjacency List

A Graph is an abstract data structure and can be modeled in various ways. Three popular ways to model a graph are 1) edge list, 2) adjacency matrix, and 3) adjacency list. In this article I will be using an adjacency list. In the sample shown, there are 3 vertices (1, 2, 3) in the graph. Vertex 1 has neighbors 2 and 3, vertex 2 has a single neighbor, 1, and vertex 3 also has a single neighbor, 1.

The adjacency list will be a Dictionary in C#, with the keys being the vertices and the value of each vertex being its set of neighbors.

```AdjacencyList = new Dictionary<T, HashSet<T>>();

{1:{2, 3}, 2:{1}, 3:{1}}
```

The `Graph` Class contains the adjacency list and has a couple of helpers to add nodes and edges.

```using System;
using System.Collections.Generic;

namespace KoderDojo.Examples {
public class Graph<T> {
public Graph() {}
public Graph(IEnumerable<T> vertices, IEnumerable<Tuple<T,T>> edges) {
foreach(var vertex in vertices)

foreach(var edge in edges)
}

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

}

}
}
}
}```

## Depth-First Search Algorithm in C#

Here is an example of the depth-first search algorithm in C# that takes an instance of a graph and a starting vertex to find all vertices that can be reached by the starting vertex.

```using System.Collections.Generic;

namespace KoderDojo.Examples {
public class Algorithms {
public 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;
}
}
}```

To make sure the depth-first search algorithm doesn't re-visit vertices, the `visited` HashSet keeps track of vertices already visited. A Stack, called `stack`, keeps track of vertices found but not yet visited. Initially `stack` contains the starting vertex. The next vertex is popped from `stack`. If it has already been visited, it is discarded and the next vertex is popped from `stack`. If it has not been visited, it is added to the set of visited vertices and its unvisited neighbors are added to `stack`. This continues until there are no more vertices in `stack`, and the set of vertices visited is returned. The set of vertices returned is all the vertices that can be reached from the starting vertex.

## Depth-First Search Example in C#

Given the following graph, use depth-first search in C# to find all vertices that can be reached from 1.

```using System;

namespace KoderDojo.Examples {
public 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);
var algorithms = new Algorithms();

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

Since all vertices can be reached by 1, it is not surprising that the set of visited vertices returned will be all vertices (1 - 10). Although the HashSet in C# doesn't guarantee an order, the order returned appears to be the exact path followed by depth-first-search. Notice that depth-first search aggresively follows a path until it can't go any futher and then backtracks a bit and continues to aggressively follow the next available path.

Dive Deep: 1 -> 3 -> 6 -> 5 -> 8 -> 9 -> 10, and then backtrack to 5 and dive deep again: 7 -> 4-> 2.

## Tracing the Path of Depth-First Search in C#

If you want a list of the vertices as they are visited by depth-first search, just add each vertex one-by-one to a list. Here is depth-first search with an extra parameter, `preVisit`, which allows one to pass a function that gets called each time a vertex is visited.

```public HashSet<T> DFS<T>(Graph<T> graph, T start, Action<T> preVisit = null) {
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 (preVisit != null)
preVisit(vertex);

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

return visited;
}```

Modify the client a bit to initiate a new list, called `path`, that gets updated each time a new vertex is visited. As you can see, the HashSet happens to be preserving the order that each vertex was inserted, but I wouldn't bet on that. A list is guaranteed to maintain its order.

```using System;
using System.Collections.Generic;

namespace KoderDojo.Examples {
public 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);
var algorithms = new Algorithms();

var path = new List<int>();

Console.WriteLine(string.Join(", ", algorithms.DFS(graph, 1, v => path.Add(v)));
# 1, 3, 6, 5, 8, 9, 10, 7, 4, 2

Console.WriteLine(string.Join(", ", path));
# 1, 3, 6, 5, 8, 9, 10, 7, 4, 2
}
}
}```

## Conclusion

Hopefully this gives you a pretty good understanding of undirected vs. directed graphs, adjacency lists, and depth-first search in C#. Next time I will code breadth-first search in C#, which can also be used to determine connectivity/reachability in an undirected graph. The code will be surprisingly similar!

You can find me on twitter as KoderDojo.

Posted by David Hayden
David Hayden is a professional Microsoft web developer. He mentors and tutors computer science students in C, C++, Java, and Python. In addition to writing computer science and programming tutorials at Koder Dojo, he also writes tutorials on C#, ASP.NET Core, and Azure as well as tutorials on Orchard Core.