时间戳

首页 > 解决方案 > 图：从边缘列表更改为邻接列表表示的时间和空间复杂度，反之亦然

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

问题描述

我正在处理一个有向图，我对 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]]

所以我的转换工作。

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

帖子 1

帖子 2

标签： pythongraphbig-oadjacency-list

解决方案

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

将边缘列表转换为邻接列表确实是O(E)。有E个边，所以应该有E个操作。但是，打印（或呈现）邻接列表本身是O(V+E)。这就是为什么。

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

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

所以V次操作是必须的。最重要的是，如果边确实存在，则必须为每个顶点打印相邻顶点。您必须总共打印E次相邻的顶点。总和为 O(V+E)。

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

推荐阅读