c# - 如何在 C# 中表示作为邻接表给出的图？

Question

我将编写各种图算法，作为输入，我给出了邻接表形式的图。

这是一个例子:

1 2 3 4

2 1 3 4

3 1 2 4

4 1 2 3 5

5 4 6

6 5

该图有 6 个顶点，由 6 行表示(每行的第一个条目表示代表该行的顶点的编号)。一行中的其余条目表示与该行对应的顶点相邻的顶点。

用 C# 表示这个的好方法是什么？每行中不同的条目数似乎排除了一个数组，所以我找到了这些 lists of lists .

我要操作图形，例如contract edges ，并且我正在寻找一种数据结构，其中图形操作既可能又有效。

Answer 1

看起来像用整数列表作为值结构的字典很有用:

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};
    }
}