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)
AddVertex(vertex);
foreach(var edge in edges)
AddEdge(edge);
}
public Dictionary<T, HashSet<T>> AdjacencyList { get; } = new Dictionary<T, HashSet<T>>();
public void AddVertex(T vertex) {
AdjacencyList[vertex] = new HashSet<T>();
}
public void AddEdge(Tuple<T,T> edge) {
if (AdjacencyList.ContainsKey(edge.Item1) && AdjacencyList.ContainsKey(edge.Item2)) {
AdjacencyList[edge.Item1].Add(edge.Item2);
AdjacencyList[edge.Item2].Add(edge.Item1);
}
}
}
}
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>();
if (!graph.AdjacencyList.ContainsKey(start))
return visited;
var stack = new Stack<T>();
stack.Push(start);
while (stack.Count > 0) {
var vertex = stack.Pop();
if (visited.Contains(vertex))
continue;
visited.Add(vertex);
foreach(var neighbor in graph.AdjacencyList[vertex])
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>();
if (!graph.AdjacencyList.ContainsKey(start))
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);
visited.Add(vertex);
foreach(var neighbor in graph.AdjacencyList[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.
