O (| V | + | E |)에서 인접성 목록의 역함수

Question

G = (V, E)를 인접성 목록 형식으로 주어진 유향 그래프로 둡니다. 에지 (u, v) ∈ E ' 이 (v, u) ∈ E 일 경우에만 방향성 그래프 G'= (V, E ')를 정의하십시오 (즉 G'에서 G '). O (| V | + | E |) 시간에 G ' 의 인접 목록 표시 을 얻기위한 알고리즘을 설명하십시오.

간단한 방법으로 인접성 목록을 역전시킬 수 있습니까?

그것이 있다면 말 :

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 | vertices는 알고리즘의 전체 시간 복잡도에 O (| V |)을 제공합니다. 또한 모든 인접 목록을 탐색하면 의 모든 가장자리를 효과적으로 통과합니다. 즉, 트래버스하는 모든 인접성 목록을 연결 한 경우 결과 목록의 길이는 | E |가됩니다. 따라서 다른 O (| E |)은 전체적인 복잡성에 기여합니다.

결과적으로 시간 복잡도는 꽤 일반적인 접근 방식으로 O (| V | + | E |)이되며이 복잡성을 달성하기 위해 특별한 방법을 고안 할 필요가 없습니다.