, обратный к списку смежности в O (| V | + | E |)

Question

Пусть G = (V, E) - ориентированный граф, заданный в формате списка смежности. Определите ориентированный граф G '= (V, E'), где ребро (u, v) ∈ E ' тогда и только тогда, когда (v, u) ∈ E (а именно, G обращается к направлению каждого ребра в G). Описать алгоритм для получения представления списка смежности из G ' в O (| V | + | E |).

есть ли простой способ изменить список смежности?

сказать, если это было:

a-> b 
b-> de 
c-> c 
d-> ab 
e-> 

к:

a-> d 
b-> ad 
c-> c 
d-> ab 
e-> b 

Answer 1

Допустим, вы итерацию смежности списки всех вершин графа следующим образом.

for each u in V: 
    for each v in adjacency_list[u]: 
     reverse_adjacency_list[v].append(u) 

При таком подходе вы проходите списки смежности всех | V | вершины, которые вносят O (| V |) в общую временную сложность вашего алгоритма. Кроме того, по мере прохождения по всем этим спискам смежности вы эффективно проходите все ребра на графике. Другими словами, если вы сориентируете все перемещенные списки смежности, длина этого результирующего списка будет | E |. Таким образом, другая общая сумма O (| E |).

Следовательно, временная сложность будет O (| V | + | E |) с этим довольно стандартным подходом, и вам не нужно придумывать какой-либо своеобразный метод для достижения этой сложности.