Graphs

A graph consists of vertices (nodes) connected by edges. Graphs model relationships — social networks, road maps, dependency trees.

Types

• Directed — edges have a direction (A -> B)
• Undirected — edges go both ways (A <-> B)
• Weighted — edges have a cost or distance
• Unweighted — all edges are equal

Adjacency List Representation

The most common representation — a dictionary mapping each vertex to its neighbors:

public class Graph
{
    private Dictionary<string, List<string>> adjList = new();

    public void AddVertex(string vertex)
    {
        if (!adjList.ContainsKey(vertex))
            adjList[vertex] = new List<string>();
    }

    public void AddEdge(string from, string to)
    {
        AddVertex(from);
        AddVertex(to);
        adjList[from].Add(to);
        adjList[to].Add(from); // remove for directed graph
    }

    public List<string> GetNeighbors(string vertex)
    {
        return adjList.GetValueOrDefault(vertex, new List<string>());
    }
}

BFS Traversal

Breadth-First Search explores all neighbors at the current depth before moving deeper:

public List<string> BFS(string start)
{
    var visited = new HashSet<string>();
    var queue = new Queue<string>();
    var result = new List<string>();

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

    while (queue.Count > 0)
    {
        string vertex = queue.Dequeue();
        result.Add(vertex);

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

    return result;
}

// Usage
var graph = new Graph();
graph.AddEdge("A", "B");
graph.AddEdge("A", "C");
graph.AddEdge("B", "D");
graph.AddEdge("C", "D");

var order = graph.BFS("A"); // [A, B, C, D]