Graphs in C#: Adjacency List, BFS, DFS, and Real-World Applications

Graphs are everywhere—from Google Maps to social networks to dependency graphs in software. If you’ve already wrapped your head around trees, you’re ready to go deeper. Graphs generalize trees: they can have cycles, multiple connections, and even weights. In this post, we’ll break down how graphs work, how to represent them in C#, and how to traverse them using BFS and DFS.

What Is a Graph: A graph is a collection of nodes (vertices) connected by edges. Unlike trees, graphs:

• May contain cycles
• Can be directed or undirected
• May have weighted edges

Real-World Analogies:

• Social networks (people are nodes, friendships are edges)
• Maps (cities as nodes, roads as edges)
• Project dependencies (tasks and their prerequisites)

Graph Representation in C#

1. Adjacency List (Recommended)

Efficient for sparse graphs (most common in real life).

Dictionary<int, List<int>> graph = new();
graph[0] = new List<int> { 1, 2 };
graph[1] = new List<int> { 2 };
graph[2] = new List<int> { 0, 3 };
graph[3] = new List<int> { 3 };

2. Adjacency Matrix (for dense graphs)

int[,] matrix = new int[4, 4];
matrix[0, 1] = 1;
matrix[0, 2] = 1;
// matrix[i, j] = 1 if there is an edge from i to j

BFS: Breadth-First Search (Level by Level) – BFS Using Queue

void BFS(Dictionary<int, List<int>> graph, int start)
{
    var visited = new HashSet<int>();
    var queue = new Queue<int>();

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

    while (queue.Count > 0)
    {
        int node = queue.Dequeue();
        Console.WriteLine(node);

        foreach (var neighbor in graph[node])
        {
            if (!visited.Contains(neighbor))
            {
                visited.Add(neighbor);
                queue.Enqueue(neighbor);
            }
        }
    }
}

DFS: Depth-First Search (Dive Deep First) – DFS Using Recursion

void DFS(Dictionary<int, List<int>> graph, int node, HashSet<int> visited)
{
    if (visited.Contains(node)) return;
    visited.Add(node);
    Console.WriteLine(node);

    foreach (var neighbor in graph[node])
    {
        DFS(graph, neighbor, visited);
    }
}

DFS Using Stack (Iterative)

void DFSIterative(Dictionary<int, List<int>> graph, int start)
{
    var visited = new HashSet<int>();
    var stack = new Stack<int>();

    stack.Push(start);

    while (stack.Count > 0)
    {
        int node = stack.Pop();
        if (!visited.Contains(node))
        {
            Console.WriteLine(node);
            visited.Add(node);

            foreach (var neighbor in graph[node])
            {
                if (!visited.Contains(neighbor))
                    stack.Push(neighbor);
            }
        }
    }
}

Real-World Applications of Graphs

• Navigation systems (shortest path, GPS)
• Web crawling (linked pages as a graph)
• Social networks (friend suggestions)
• Task scheduling (topological sort)
• Detecting deadlocks in OS (cycle detection)

Practice Problems

1. Detect a cycle in a directed graph
2. Count connected components
3. Check if a graph is bipartite
4. Find shortest path using BFS
5. Implement a graph class with AddEdge, RemoveEdge, Display