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.