图形构建的邻接列表

本文关键字：列表 构建 图形 | 更新日期: 2023-09-27 18:35:25

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

例如，我可以在边的其他节点的每个位置内制作一个带有其他参数的数组列表

，如下所示： 
nodes {a,b,c}, connection {{a-c},{b,c}}

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

图形构建的邻接列表

邻

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

如果您有以下节点 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。然后，您可以使用一个成员变量来表示与另一个节点的连接，或者在数组的每个元素中具有单独的数组列表。

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

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

您可以使用 Dictionary 实现邻接列表。字典中的每个键都表示边缘的起始节点。每个值都是对象的List，每个对象定义边缘的目标节点。

例如，您可以在每个密钥中存储Tuples List。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);
    }
}
相关文章：