Graph Algorithms

Why graph algorithms matter

In Dynamic Programming, you learned to reuse answers when a problem has overlapping subproblems. Graph algorithms train a different muscle: reasoning about relationships.

A graph is useful whenever your program needs to model things like:

• users connected by friendships
• web pages connected by links
• game map rooms connected by doors
• build tasks connected by prerequisites
• services connected by API calls

In OODSA terms, graphs are where object modeling and data structures meet: objects become nodes, relationships become edges, and algorithms answer questions like “Can I reach it?”, “What is nearby?”, and “What must happen first?”

Nodes and edges

A graph contains:

• Vertices / nodes: the things being modeled
• Edges: relationships between those things

Edges can be:

• Undirected: A is connected to B, and B is connected to A
• Directed: A points to B, but B may not point back
• Weighted: an edge has a cost, distance, or duration

Example:

Undirected friends:
A --- B --- C

Directed prerequisites:
Intro -> Data Structures -> Graphs

For this lesson, focus on the core graph thinking pattern: represent the relationships, then traverse them carefully.

Adjacency lists

From Data Structures, you already know dictionaries and lists. A common graph representation combines them:

• key: a node
• value: the nodes directly connected to it

This is called an adjacency list. It is often the best default for programming interviews and real systems because many graphs are sparse: each node connects to only a few others.

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

public class Program
{
    static void AddUndirectedEdge(Dictionary<string, List<string>> graph, string a, string b)
    {
        if (!graph.ContainsKey(a)) graph[a] = new List<string>();
        if (!graph.ContainsKey(b)) graph[b] = new List<string>();

        graph[a].Add(b);
        graph[b].Add(a);
    }

    public static void Main()
    {
        var graph = new Dictionary<string, List<string>>();

        AddUndirectedEdge(graph, "Alice", "Bob");
        AddUndirectedEdge(graph, "Alice", "Chloe");
        AddUndirectedEdge(graph, "Bob", "Diego");

        foreach (var node in graph)
        {
            Console.WriteLine(node.Key + " -> " + string.Join(", ", node.Value));
        }
    }
}
```

BFS explores by layers

Breadth-first search, or BFS, starts at one node and visits all nodes at distance 1, then distance 2, then distance 3, and so on.

That layer-by-layer behavior makes BFS a natural fit for questions like:

• “Can I reach this node?”
• “How many edges away is it?”
• “What is the shortest path in an unweighted graph?”

The key data structure is a queue, which you saw in Data Structures.

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

public class Program
{
    public static void Main()
    {
        var graph = new Dictionary<string, List<string>>
        {
            ["A"] = new List<string> { "B", "C" },
            ["B"] = new List<string> { "A", "D" },
            ["C"] = new List<string> { "A", "E" },
            ["D"] = new List<string> { "B", "F" },
            ["E"] = new List<string> { "C", "F" },
            ["F"] = new List<string> { "D", "E" }
        };

        string start = "A";
        string target = "F";

        var queue = new Queue<string>();
        var distance = new Dictionary<string, int>();

        queue.Enqueue(start);
        distance[start] = 0;

        while (queue.Count > 0)
        {
            string current = queue.Dequeue();

            foreach (string neighbor in graph[current])
            {
                if (distance.ContainsKey(neighbor)) continue;

                distance[neighbor] = distance[current] + 1;
                queue.Enqueue(neighbor);
            }
        }

        Console.WriteLine($"Shortest unweighted distance from {start} to {target}: {distance[target]}");
    }
}
```

DFS follows a path deeply

Depth-first search, or DFS, explores as far as it can along one path before backing up.

A helpful mental image:

BFS: ripple outward from the start
DFS: walk down one corridor until stuck, then backtrack

DFS is especially useful for:

• detecting whether a path exists
• exploring connected components
• solving maze-like problems
• reasoning about dependencies and cycles

The invariant is simple but important: never process a visited node twice. Without that, a graph with cycles can trap your algorithm forever.

You are modeling a large social network where each user has a relatively small number of friends compared with the total number of users.

Which graph representation is usually the best default?

True or false: In an unweighted graph, BFS is the usual traversal to find the shortest number of edges from a start node to a target node.

Topological sort

Some directed graphs describe prerequisites:

Design -> Build -> Test -> Deploy

A topological sort returns an order where every prerequisite appears before the thing that depends on it.

This only works for a directed acyclic graph, often called a DAG. If there is a cycle, no valid ordering exists because something eventually depends on itself.

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

public class Program
{
    public static void Main()
    {
        var graph = new Dictionary<string, List<string>>
        {
            ["Design"] = new List<string> { "Build" },
            ["Build"] = new List<string> { "Test" },
            ["Test"] = new List<string> { "Deploy" },
            ["Deploy"] = new List<string>()
        };

        var indegree = new Dictionary<string, int>();

        foreach (var node in graph.Keys)
        {
            if (!indegree.ContainsKey(node)) indegree[node] = 0;
            foreach (var neighbor in graph[node])
            {
                if (!indegree.ContainsKey(neighbor)) indegree[neighbor] = 0;
                indegree[neighbor]++;
            }
        }

        var queue = new Queue<string>();
        foreach (var pair in indegree)
        {
            if (pair.Value == 0) queue.Enqueue(pair.Key);
        }

        var order = new List<string>();

        while (queue.Count > 0)
        {
            string current = queue.Dequeue();
            order.Add(current);

            foreach (string neighbor in graph[current])
            {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) queue.Enqueue(neighbor);
            }
        }

        Console.WriteLine("Build order: " + string.Join(" -> ", order));
    }
}
```

In BFS or DFS, we usually keep a set of nodes already seen. This set is commonly called the ______ set.

How to approach graph problems

Use this checklist before writing code:

1. What are the nodes? Objects, states, tasks, locations, users?
2. What are the edges? Are they directed or undirected?
3. Are edges weighted? If yes, this changes the strategy.
4. What question are you answering? Reachability, shortest unweighted path, connected groups, dependency order?
5. Which traversal fits? BFS for layers, DFS for deep exploration, topological sort for DAG ordering.
6. What prevents repetition? Usually a visited set or indegree tracking.

This keeps the same habit you built in Algorithmic Thinking: define the invariant before trusting the loop.

Next, you’ll study Greedy Algorithms, where the challenge becomes choosing a locally best move and knowing when that choice is safe.