График: временная и пространственная сложность перехода от списка ребер к представлению списка смежности и наоборот - PullRequest
Новая
       54

График: временная и пространственная сложность перехода от списка ребер к представлению списка смежности и наоборот

0 голосов
/ 01 июня 2018

Я имею дело с ориентированным графом, и меня смутило то, как объяснение Альберто Миранды о Кора пришло к сложности времени O(n+m) [Я предполагаю, что он имеет в виду O(V+E) для вершин и ребер],

Можно преобразовать список ребер L в представление списка смежности A за время O (n + m).Затем можно выполнить DFS для представления A за время O (n + m), всего O (n + m).

Вот мое понимание преобразования из одного представления в другое.:

Для преобразования из списка ребер в список смежности:

Насколько я понимаю, все, что нам нужно сделать, - это пройти через каждое ребро и добавить в список смежностиэта первая вершина в каждом списке ребер, что дает временную сложность O(E).Чего мне не хватает?Я предполагаю, что переменные n и m относятся к вершинам и ребрам соответственно, но не стесняйтесь меня поправлять.

Для преобразования из списка смежности в список краев:

Я попробовал это преобразование просто для того, чтобы увидеть, имел ли он в виду обратное преобразование.Чтобы переключиться из списка смежности, мне нужно пройти через каждую вершину, V, а затем пройти через все ребра V, E, давая мне O(V+E).

Я написал код для проверки

Вот график, который я представляю: предостережение в том, что вершина 3 не является ключом в представлении списка смежности и поэтому не включена в преобразование из списка смежности.к краю списка.

graph being represented

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

1 Ответ

0 голосов
/ 18 сентября 2018

Насколько я понимаю, все, что нам нужно сделать, - это пройти через каждое ребро и добавить к списку смежности эту первую вершину в каждом списке ребер, тем самым давая временную сложность O (E).

Преобразование списка ребер в список смежности действительно O (E) .Имеется E ребер, поэтому должно быть E операций.Тем не менее, печать (или представление) самого списка смежности O (V + E) .Вот почему.

Подумайте, если между какими-либо вершинами не было ребра, вам все равно нужно пройти через каждую вершину, и вы получите что-то вроде этого: 

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

Итак V количество операций является обязательным.Кроме того, вы должны напечатать соседние вершины для каждой вершины, если ребра существуют.Вы должны напечатать соседние вершины всего E раз.Это сумма в O (V + E).

Подводя итог: преобразовать из списка ребер в список смежности: O (E) представить список смежности (независимо от преобразования): O (V + E)

...