How do I represent a graph given as an adjacency list in C#?

Question

I am going to program various graph algorithms, and as input, I have given graphs on the form of adjacency lists.

Here's an example:

1 2 3 4

2 1 3 4

3 1 2 4

4 1 2 3 5

5 4 6

6 5

The graph has 6 vertices, represented by 6 rows (and the first entry of each row denotes the number of the vertex representing that row). The remaining entries in a row denote the vertices that the vertex corresponding to that row are adjacent to.

What is a good way of representing this in C#? The differing number of entries in each row seem to rule out an array, so I found these lists of lists.

I am going to manipulate the graph, e.g. contract edges, and I am looking for a data structure in which graph manipulations are both possible and efficient.

Answer 1

Looks like dictionary with a list of integers as a value structure cold be useful:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary<int, List<int>> graph = new Dictionary <int, List<int>>();
        graph[1] = new List<int> {2, 3, 4};
        graph[2] = new List<int> {1, 3, 4};
        graph[3] = new List<int> {1, 2, 4};
        graph[4] = new List<int> {1, 2, 3, 5};
        graph[5] = new List<int> {4, 6};
        graph[6] = new List<int> {5};
    }
}