A few years ago, I was working on a feature for a logistics platform that needed to calculate the "degrees of separation" between different warehouses in a global supply chain. My first instinct was to handle this with a series of recursive SQL joins. It worked for a couple of levels, but as soon as I tried to find a path across five or six hops, the database started screaming, and the query time skyrocketed. I realized I was trying to treat a graph problem like a table problem. I had to pull the topology into memory and implement a proper graph traversal. It was a humbling reminder that while databases are powerful, some data structures are just fundamentally better suited for specific types of movement.

Mapping Connections with Adjacency Lists

In C#, you could technically represent a graph using a 2D array (an adjacency matrix), but unless your graph is incredibly dense, that's a massive waste of memory. Instead, I almost always use an adjacency list. Essentially, this is a dictionary where the key is the node, and the value is a list of all the nodes it connects to. It's flexible, intuitive, and maps perfectly to C#'s Dictionary<T, List<T>>.

public class Graph<T> where T : notnull
{
    // The adjacency list: each node maps to a list of its neighbors
    private readonly Dictionary<T, List<T>> _adjacencyList = new();

    public void AddEdge(T source, T destination, bool bidirectional = true)
    {
        if (!_adjacencyList.ContainsKey(source)) _adjacencyList[source] = new List<T>();
        if (!_adjacencyList.ContainsKey(destination)) _adjacencyList[destination] = new List<T>();

        _adjacencyList[source].Add(destination);
        if (bidirectional)
        {
            _adjacencyList[destination].Add(source);
        }
    }

    public List<T> GetNeighbors(T node) => 
        _adjacencyList.TryGetValue(node, out var neighbors) ? neighbors : new List<T>();
}

Layer-by-Layer Exploration with BFS

When you need to find the shortest path in an unweighted graph—like finding the fewest number of hops between two people in a social network—Breadth-First Search (BFS) is your best friend. Think of it like a ripple in a pond. You visit the starting node, then all its immediate neighbors, then all their neighbors, and so on.

The key to BFS is the Queue. You enqueue the start node, and while the queue isn't empty, you dequeue a node, process it, and enqueue all of its unvisited neighbors. I always emphasize using a HashSet to track visited nodes; if you don't, and your graph has a cycle (A points to B, B points to A), your program will loop forever and crash with a stack overflow or an out-of-memory exception.

public void BreadthFirstSearch(T startNode)
{
    var visited = new HashSet<T>();
    var queue = new Queue<T>();

    visited.Add(startNode);
    queue.Enqueue(startNode);

    while (queue.Count > 0)
    {
        T current = queue.Dequeue();
        Console.WriteLine($"Visited: {current}");

        foreach (T neighbor in GetNeighbors(current))
        {
            if (!visited.Contains(neighbor))
            {
                visited.Add(neighbor);
                queue.Enqueue(neighbor);
            }
        }
    }
}

Diving Deep with DFS

Depth-First Search (DFS) is a different beast. Instead of ripples, think of DFS like exploring a maze. You pick a path and follow it as far as it goes until you hit a dead end, then you backtrack to the last junction and try the next path. This is typically implemented using recursion, which leverages the call stack, though you can use an explicit Stack<T> if you're worried about very deep graphs.

DFS isn't great for finding the shortest path, but it's fantastic for detecting cycles or checking if a path exists at all. It's also the foundation for more complex algorithms like topological sorting. Here is how I usually implement it recursively for clarity:

public void DepthFirstSearch(T startNode)
{
    var visited = new HashSet<T>();
    DFSRecursive(startNode, visited);
}

private void DFSRecursive(T current, HashSet<T> visited)
{
    visited.Add(current);
    Console.WriteLine($"Visited: {current}");

    foreach (T neighbor in GetNeighbors(current))
    {
        if (!visited.Contains(neighbor))
        {
            DFSRecursive(neighbor, visited);
        }
    }
}

📋 Practical Task

Exercise: The Corporate Hierarchy Path-Finder

You are building a tool for an HR department to analyze the reporting structure of a large company. Some employees have multiple mentors or dotted-line managers, making the organization a graph rather than a simple tree.

Your Task: Implement a class CompanyGraph that allows the HR team to:

• Add reporting relationships (Edges) between employees (Nodes).
• Implement a method bool CanEmployeeReachManager(string employee, string manager) that uses DFS to determine if there is any reporting path from a specific employee up to a specific manager.
• Implement a method int GetMinimumHops(string employee, string manager) that uses BFS to find the shortest number of reporting levels between two people. Return -1 if no path exists.

Test Scenario:
Relationships:
Alice → Bob
Bob → Charlie
Alice → David
David → Charlie
Charlie → CEO
Eve → CEO

Verify that GetMinimumHops("Alice", "CEO") returns 3 (Alice → Bob/David → Charlie → CEO).