Adjacency List Implementation in C#

Hello people..! This is a special extension for my discussion on Graph Theory Basics. Here, I give you the code for implementing the Adjacency List in C# using the .Net Library. Some of the features of this code are –

  • The Adjacency List is an array of LinkedList<>, where each element is a Tuple<>. This Tuple stores two values, the destination vertex, (V2 in an edge V1 → V2) and the weight of the edge.
  • For adding an edge, we can call –
    • void addEdgeAtEnd(int startVertex, int endVertex, int weight) – To append an edge to the linked list.
    • void addEdgeAtBegin(int startVertex, int endVertex, int weight) – To add an edge at the beginning of the linked list.
  • Methods have been provided to return the number of vertices.
  • An Indexer has been provided to help in retrieving the edges from a vertex. We can use Count property on this, to get the number of edges from a vertex.
  • bool removeEdge(int startVertex, int endVertex, int weight) – Tries to remove the first occurrence an edge from the adjacency list. Returns true if successfull.
using System;
using System.Collections.Generic;

namespace TheoryOfProgramming
    class AdjacencyList
        LinkedList<Tuple<int, int>>[] adjacencyList;

        // Constructor - creates an empty Adjacency List
        public AdjacencyList(int vertices)
            adjacencyList = new LinkedList<Tuple<int, int>>[vertices];

            for (int i = 0; i < adjacencyList.Length; ++i)
                adjacencyList[i] = new LinkedList<Tuple<int, int>>();

        // Appends a new Edge to the linked list
        public void addEdgeAtEnd(int startVertex, int endVertex, int weight)
            adjacencyList[startVertex].AddLast(new Tuple<int, int>(endVertex, weight));

        // Adds a new Edge to the linked list from the front
        public void addEdgeAtBegin(int startVertex, int endVertex, int weight)
            adjacencyList[startVertex].AddFirst(new Tuple<int, int>(endVertex, weight));

        // Returns number of vertices
        // Does not change for an object
        public int getNumberOfVertices()
            return adjacencyList.Length;

        // Returns a copy of the Linked List of outward edges from a vertex
        public LinkedList<Tuple<int, int>> this[int index]
                LinkedList<Tuple<int, int>> edgeList 
                               = new LinkedList<Tuple<int, int>>(adjacencyList[index]);

                return edgeList;

        // Prints the Adjacency List
        public void printAdjacencyList()
            int i = 0;

            foreach (LinkedList<Tuple<int, int>> list in adjacencyList)
                Console.Write("adjacencyList[" + i + "] -> ");

                foreach (Tuple<int, int> edge in list)
                    Console.Write(edge.Item1 + "(" + edge.Item2 + ")");


        // Removes the first occurence of an edge and returns true
        // if there was any change in the collection, else false
        public bool removeEdge(int startVertex, int endVertex, int weight)
            Tuple<int, int> edge = new Tuple<int, int>(endVertex, weight);

            return adjacencyList[startVertex].Remove(edge);

    class TestGraph
        public static void Main()
            Console.WriteLine("Enter the number of vertices -");
            int vertices = Int32.Parse(Console.ReadLine());

            AdjacencyList adjacencyList = new AdjacencyList(vertices + 1);
            Console.WriteLine("Enter the number of edges -");
            int edges = Int32.Parse(Console.ReadLine());

            Console.WriteLine("Enter the edges with weights -");
            int startVertex, endVertex, weight;

            for (int i = 0; i < edges; ++i)
                startVertex = Int32.Parse(Console.ReadLine());
                endVertex = Int32.Parse(Console.ReadLine());
                weight = Int32.Parse(Console.ReadLine());

                adjacencyList.addEdgeAtEnd(startVertex, endVertex, weight);

            adjacencyList.removeEdge(1, 2, 1);

One sweet thing about this code is that we can easily store more information in an edge. We can do so by adding elements to the generic Tuple<>… We need to give each input in a single line, otherwise an exception is thrown. If not we must split the input and then parse the array elements. This is an example demonstrates it –

class Program
    static void Main(string[] args)
        Console.WriteLine("Enter -> startVertex endVertex weight");

        // Spilt by space as delimeter
        String[] input = Console.ReadLine().Split(' ');

        int startVertex = Int32.Parse(input[0]);
        int endVertex = Int32.Parse(input[1]);
        int weight = Int32.Parse(input[2]);



Feel free to comment if you have any doubts..! Commenting is super easy if you are a Facebook, Twitter or a Google+ user…! So, don’t hesitate..! 😉 … Keep practising..! Happy Coding..! 😀


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s