How to Implement Graph in C#: Simple Guide with Example

To implement a graph in C#, use a Dictionary<T, List<T>> to represent adjacency lists where keys are nodes and values are lists of connected nodes. This structure allows easy addition of edges and traversal of the graph.

Syntax

A graph can be represented using an adjacency list with a Dictionary<T, List<T>> where each key is a node and the value is a list of nodes connected to it. You add nodes as keys and edges by adding nodes to the lists.

• Dictionary<T, List<T>> graph: stores nodes and their neighbors.
• AddNode(T node): adds a new node to the graph.
• AddEdge(T from, T to): adds a connection from one node to another.

csharp

Dictionary<T, List<T>> graph = new Dictionary<T, List<T>>();

void AddNode(T node) {
    if (!graph.ContainsKey(node)) {
        graph[node] = new List<T>();
    }
}

void AddEdge(T from, T to) {
    if (graph.ContainsKey(from)) {
        graph[from].Add(to);
    }
}

Example

This example shows how to create a simple directed graph with nodes and edges, then print all connections.

csharp

using System;
using System.Collections.Generic;

class Graph<T> {
    private Dictionary<T, List<T>> adjacencyList = new Dictionary<T, List<T>>();

    public void AddNode(T node) {
        if (!adjacencyList.ContainsKey(node)) {
            adjacencyList[node] = new List<T>();
        }
    }

    public void AddEdge(T from, T to) {
        if (!adjacencyList.ContainsKey(from)) {
            AddNode(from);
        }
        if (!adjacencyList.ContainsKey(to)) {
            AddNode(to);
        }
        adjacencyList[from].Add(to);
    }

    public void PrintGraph() {
        foreach (var node in adjacencyList) {
            Console.Write(node.Key + " -> ");
            Console.WriteLine(string.Join(", ", node.Value));
        }
    }
}

class Program {
    static void Main() {
        Graph<string> graph = new Graph<string>();
        graph.AddNode("A");
        graph.AddNode("B");
        graph.AddNode("C");

        graph.AddEdge("A", "B");
        graph.AddEdge("A", "C");
        graph.AddEdge("B", "C");

        graph.PrintGraph();
    }
}

Output

A -> B, C
B -> C
C -> 

Common Pitfalls

Common mistakes when implementing graphs in C# include:

• Not checking if nodes exist before adding edges, which can cause errors.
• Confusing directed and undirected edges; adding edges only one way creates a directed graph.
• Modifying the adjacency list while iterating over it, which can cause runtime exceptions.
• Not handling duplicate edges if your graph should avoid them.

Always ensure nodes exist before adding edges and decide if your graph is directed or undirected.

csharp

/* Wrong: Adding edge without checking node existence */
// graph["A"].Add("B"); // Throws KeyNotFoundException if "A" not added

/* Right: Use AddNode before adding edges */
graph.AddNode("A");
graph.AddNode("B");
graph.AddEdge("A", "B");

Quick Reference

Summary tips for graph implementation in C#:

• Use Dictionary<T, List<T>> for adjacency lists.
• Always add nodes before edges.
• Decide if graph is directed or undirected and add edges accordingly.
• Use loops to traverse or print the graph.

Key Takeaways

Use a dictionary of lists to represent graph adjacency in C#.

Always add nodes before adding edges to avoid errors.

Decide if your graph is directed or undirected before adding edges.

Check for node existence to prevent runtime exceptions.

Traverse the graph by iterating over the dictionary keys and their adjacency lists.