c# - 图构建的邻接表

Question

有人可以告诉我我必须制作什么样的邻接列表来构建具有适当节点和链接的图形吗？我必须创建一个树结构来定义 ajdacency 列表吗？还是有其他方法？
现在对矩阵不感兴趣，谢谢。

例如，我可以在边缘的其他节点的每个位置与其他 arralists 一起创建一个数组列表，以具有如下所示：

nodes {a,b,c}, connection {{a-c},{b,c}}

所以我有和arraylist或我的邻接列表[a[c],b[c],c[a,b]]

Answer 1

邻接表仅表示哪些节点相互连接。

如果您有以下节点 1 -4 的图形，则相邻矩阵将如下所示。“1”表示节点之间的连接。

    1 2 3 4
 1  1 1 1 1
 2  1 0 0 0
 3  0 1 0 1
 4  0 1 1 0

列表看起来像这样。-> 表示链接

 1  -> 1 -> 2 -> 3 -> 4
 2  -> 1
 3  -> 2 -> 4
 4  -> 2 -> 3

您是否考虑过在上面指定的数组中使用链表，因此该数组将包含节点 1 - 4。然后您可以有一个表示与另一个节点的连接的成员变量，或者在数组的每个元素中都有一个单独的数组列表.

Answer 2

一个 ArrayList 的 ArrayList（或更一般地说，一个列表的列表）是一个很好的方法，是的。这是邻接列表的标准表示。所以你的想法很好。

此外，如果您事先知道图形的大小（节点数），并且在创建后不需要向其添加节点，则 ArrayLists 数组也可以这样做并且效率更高。

Answer 3

您可以使用Dictionary. 字典中的每个键都代表边缘的起始节点。每个值都是一个List对象，每个对象定义边缘的目标节点。

例如，您可以在每个键中存储一个Listof 。Tuples中的第一项Tuple将代表目标节点。其他项目将定义边缘的属性。

class AdjacencyList
{

    Dictionary<int, List<Tuple<int, int>>> adjacencyList;

    // Constructor - creates an empty Adjacency List
    public AdjacencyList(int vertices)
    {
        adjacencyList = new Dictionary<int, List<Tuple<int, int>>>();
    }

    // Appends a new Edge to the linked list
    public void addEdge(int startVertex, int endVertex, int weight)
    {
        if (!adjacencyList.ContainsKey(startVertex)) {
            adjacencyList[startVertex] = new List<Tuple<int, int>>();
        }

        adjacencyList[startVertex].Add(new Tuple<int, int>(endVertex, weight));
    }

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