使用邻接表向图添加边的时间复杂度
Time Complexity of Adding Edge to Graph using Adjacency List
我一直在研究使用邻接列表实现的图，我 reading 认为添加边是 O(1) 操作。
如果您只是将一条边添加到 Vertex 的边链接列表上，这是有道理的，但我不明白这是怎么回事，只要您关心删除旧边，如果 一个已经存在。找到那个边缘需要 O(V) 时间。
如果您不这样做，并且您添加了一条已经存在的边，那么您将拥有该边的重复条目，这意味着它们可能具有不同的权重等。
谁能解释一下我似乎遗漏了什么？谢谢！
您的复杂性分析是正确的。查找边是否已经存在确实是 O(V)。但是请注意，即使存在这条边，添加这条边仍然是 O(1)。
您需要记住，具有相同源和目的地的 2 条边是 有效 图的输入 - 即使具有不同的权重（可能不是均匀但因为）。
这样向邻接列表图添加边的时间复杂度为 O(1)
为了兼顾最佳搜索时间复杂度和邻接列表的优点，人们通常会使用哈希集数组而不是列表数组。
或者，
If you want a worst-case optimal solution, use RadixSort to order the
list of all edges in O(v+e) time, remove duplicates, and then build
the adjacency list representation in the usual way.
我一直在研究使用邻接列表实现的图，我 reading 认为添加边是 O(1) 操作。
如果您只是将一条边添加到 Vertex 的边链接列表上，这是有道理的，但我不明白这是怎么回事，只要您关心删除旧边，如果 一个已经存在。找到那个边缘需要 O(V) 时间。
如果您不这样做，并且您添加了一条已经存在的边，那么您将拥有该边的重复条目，这意味着它们可能具有不同的权重等。
谁能解释一下我似乎遗漏了什么？谢谢！
您的复杂性分析是正确的。查找边是否已经存在确实是 O(V)。但是请注意，即使存在这条边，添加这条边仍然是 O(1)。
您需要记住，具有相同源和目的地的 2 条边是 有效 图的输入 - 即使具有不同的权重（可能不是均匀但因为）。
这样向邻接列表图添加边的时间复杂度为 O(1)
为了兼顾最佳搜索时间复杂度和邻接列表的优点，人们通常会使用哈希集数组而不是列表数组。
或者，
If you want a worst-case optimal solution, use RadixSort to order the list of all edges in O(v+e) time, remove duplicates, and then build the adjacency list representation in the usual way.