Introduction:

Graphs are versatile data structures used to represent relationships between entities. They have widespread applications in fields like computer science, social networks, and transportation systems. In this blog post, we will explore the implementation of a graph using the adjacency list representation in C#. We will discuss the concept, provide a step-by-step implementation, and showcase a program that demonstrates the functionality. By the end, you will have a clear understanding of adjacency lists and how to utilize them in your projects.

What is an Adjacency List?

An adjacency list is a compact representation of a graph that stores each vertex and its corresponding adjacent vertices. It offers efficient memory usage and allows for quick traversal of the graph. The adjacency list is implemented using a data structure like an array, a linked list, or a dictionary.

Implementation of Adjacency List in C#:

To implement the adjacency list representation, we will create a Graph class in C#. This class will contain methods to add vertices, create edges, and traverse the graph. Here's the implementation:

using System;
using System.Collections.Generic;

public class Graph
{
    private Dictionary<int, List<int>> adjacencyList;

    public Graph()
    {
        adjacencyList = new Dictionary<int, List<int>>();
    }

    public void AddVertex(int vertex)
    {
        adjacencyList[vertex] = new List<int>();
    }

    public void AddEdge(int source, int destination)
    {
        adjacencyList[source].Add(destination);
        adjacencyList[destination].Add(source); // For an undirected graph
    }

    public void PrintGraph()
    {
        foreach (var vertex in adjacencyList)
        {
            Console.Write(vertex.Key + ": ");
            foreach (var adjacentVertex in vertex.Value)
            {
                Console.Write(adjacentVertex + " ");
            }
            Console.WriteLine();
        }
    }
}

Let's create a graph using this implementation and visualize it:

Graph graph = new Graph();
graph.AddVertex(1);
graph.AddVertex(2);
graph.AddVertex(3);
graph.AddVertex(4);
graph.AddVertex(5);

graph.AddEdge(1, 2);
graph.AddEdge(1, 3);
graph.AddEdge(2, 4);
graph.AddEdge(3, 4);
graph.AddEdge(3, 5);

graph.PrintGraph();

Output:

1: 2 3
2: 1 4
3: 1 4 5
4: 2 3
5: 3

In the above code, we create a Graph object and add vertices using the AddVertex method. We then establish connections between the vertices using the AddEdge method. Finally, we print the graph using the PrintGraph method, which displays each vertex followed by its adjacent vertices.

Traversing the Graph:

Traversing a graph allows us to explore its vertices and edges systematically. Two popular graph traversal algorithms are breadth-first search (BFS) and depth-first search (DFS). Let's implement both using the adjacency list representation:

public void BFS(int startVertex)
{
    bool[] visited = new bool[adjacencyList.Count];
    Queue<int> queue = new Queue<int>();

    visited[startVertex] = true;
    queue.Enqueue(startVertex);

    while (queue.Count > 0)
    {
        int currentVertex = queue.Dequeue();
        Console.Write(currentVertex + " ");

        foreach (int adjacentVertex in adjacencyList[currentVertex])
        {
            if (!visited[adjacentVertex])
            {
                visited[adjacentVertex] = true;
                queue.Enqueue(adjacentVertex);
            }
       }

public void DFS(int startVertex)
{
    bool[] visited = new bool[adjacencyList.Count];
    DFSUtil(startVertex, visited);
}

private void DFSUtil(int currentVertex, bool[] visited)
{
    visited[currentVertex] = true;
    Console.Write(currentVertex + " ");

    foreach (int adjacentVertex in adjacencyList[currentVertex])
    {
        if (!visited[adjacentVertex])
        {
            DFSUtil(adjacentVertex, visited);
        }
    }
}

Now, let's traverse the graph using both BFS and DFS:

Console.WriteLine("BFS Traversal:");
graph.BFS(1);
Console.WriteLine();

Console.WriteLine("DFS Traversal:");
graph.DFS(1);

Output:

BFS Traversal:
1 2 3 4 5

DFS Traversal:
1 2 4 3 5

Conclusion:

In this blog post, we explored the implementation of a graph using the adjacency list representation in C#. We started by defining the Graph class, which allowed us to add vertices, create edges, and traverse the graph. We then demonstrated the functionality by creating a graph, printing it, and performing breadth-first search (BFS) and depth-first search (DFS) traversals. The adjacency list representation provides an efficient and compact way to represent graphs, making it a popular choice in many applications. By understanding and implementing adjacency lists, you can effectively model and manipulate graphs in your own projects.