图表：从边缘列表更改为邻接列表表示的时间和空间复杂度，反之亦然

Question

我正在处理有向图，我很困惑Alberto Miranda对Quora的解释如何到达时间复杂度O(n+m) [我假设他的意思是O(V+E)的顶点和边缘]。

可以在时间O（n + m）中将边缘列表L转换为邻接列表表示A.然后，可以在时间O（n + m）上对表示A执行DFS，总共为O（n + m）。

以下是我对从一种表示转换为另一种表示的理解：

对于从边列表到邻接列表的转换：

我的理解是我们所要做的就是遍历每条边并添加到每个边列表中第一个顶点的邻接列表中，从而给出O(E)的时间复杂度。我错过了什么？我假设n和m变量分别指向顶点和边缘，但我可以随意纠正我。

对于从邻接列表到边缘列表的转换：

我试过这个转换只是为了看他是否指的是逆转换。要从邻接列表切换，我将不得不通过每个顶点，V，然后通过每个V的边缘，E给我O(V+E)。

我写了代码给它检查

这是我所代表的图：需要注意的是顶点3不是邻接列表表示中的键，因此不包括在从邻接列表到边列表的转换中。

from collections import defaultdict

class AdjacencyListGraph:
  def __init__(self):
    self.graph = defaultdict(list)

  def addEdge(self, u, v):
    self.graph[u].append(v)

class EdgeListGraph:
  def __init__(self):
    self.graph = []

  def addEdge(self, u, v):
    self.graph.append([u, v])

  def addAllEdgesAtOnce(self, edgeList):
    self.graph = edgeList



def edgeListToAdjacencyList(edgeListGraph):
  adjacencyListGraph = AdjacencyListGraph()

  for edge in edgeListGraph.graph:
    adjacencyListGraph.addEdge(edge[0], edge[1])

  return adjacencyListGraph

def adjacencyListToEdgeList(adjacencyListGraph):
  edgeListGraph = EdgeListGraph()

  for vertex in adjacencyListGraph.graph.keys():
    for child in adjacencyListGraph.graph[vertex]:
      edgeListGraph.addEdge(vertex, child)

  return edgeListGraph

edgeList = [
              [1, 2],
              [2, 3],
              [1, 3],
              [4, 1],
              [4, 5],
              [5, 6],
              [6, 4]
]

edgeListGraph = EdgeListGraph()
edgeListGraph.addAllEdgesAtOnce(edgeList)
adjacencyListGraph = edgeListToAdjacencyList(edgeListGraph)
print(adjacencyListGraph.graph)

# trying to reverse the conversion
convertedEdgeListGraph = adjacencyListToEdgeList(adjacencyListGraph)
print(convertedEdgeListGraph.graph)

给出结果

>>> defaultdict(<class 'list'>, {1: [2, 3], 2: [3], 4: [1, 5], 5: [6], 6: [4]})
>>> [[1, 2], [1, 3], [2, 3], [4, 1], [4, 5], [5, 6], [6, 4]]

所以我的转换工作。

这些帖子与邻接列表有关，但没有提及时间复杂性。

Post 1

Post 2

Answer 1

我的理解是我们所要做的就是遍历每个边缘并添加到每个边缘列表中第一个顶点的邻接列表中，从而给出O（E）的时间复杂度。

将边缘列表转换为邻接列表确实是O（E）。有E边，所以应该有E操作。然而，打印（或呈现）邻接列表本身是O（V + E）。这就是原因。

想想，如果任何顶点之间没有边缘，你还必须经历每个顶点，你最终会得到这样的结果：

{1: [], 2: [], 3: [], 4: [],... v: []}

因此V操作是必须的。如果边缘确实存在，则必须在每个顶点上打印相邻顶点。您必须在E次中打印相邻顶点。总和为O（V + E）。

总结：从边缘列表转换为邻接列表：O（E）呈现邻接列表（独立于转换）：O（V + E）