똑똑한 코드 작성을 위한 실전 알고리즘

247

7

장

그래프

2

×

E

회 수행된다.

push

()

와

pop

()

실행

N

회와

if

문 실행

2

×

E

회를 모두 합치면, 인접 리스트를 사용했을 때

해당 탐색 알고리즘의 런타임 성능은

O

(

N

+

E

)다. 여기서

N

은 노드 개수이고

E

는 간선 개수

다. 너비 우선 탐색도 마찬가지인데, 스택 대신에 큐를 사용하지만 같은 런타임 성능을 보인다.

어떤 면에서 이 결과는 실제로 호환이 된다. 특히 노드가

N

개이고 무향 그래프에서

E

는

N

×

(

N

–

1

)/

2

6

간선보다 작거나 같다. 그래프가 인접 행렬을 사용하든 인접 리스트를 사용하든 상

관없이, 간선이 많은 그래프를 탐색하는 것은

N

×

(

N

–

1

)/

2

나

O

(

N

2

)에 비례하며 최악의 경

우에

O

(

N

2

)이 된다.

하지만 유도 탐색은 지정된 목적지 노드에 가장 가까운 노드를 유지하기 위해 우선순위 큐에

의존한다.

enqueue

()

와

dequeue

()

연산은 최악의 경우

O

(

log

N

)이 된다. 해당 메서드는

N

회 호출되므로 각 간선을 두 번씩 방문해 유도 탐색은 최악의 경우 성능이

O

(

N

log

N

+

E

)가

된다.

7.4

유향 그래프

그래프는 두 노드 간의 관계에 방향이 있는 문제를 모델링할 수도 있다. 이때 간선을 화살표로

사용하며, 방향이 있는 간선 (

u

,

v

)는

v

가

u

에 인접함을 의미하며, 간선

u

가

v

에 인접하지는 않

는다. 이 간선에서