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

278

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

➊

node_from[][]

구조는

src

에서 모든

target

까지 경로를 복구하는 데 필요하다.

➋

완전 경로를 복구하기 위해

target

에서 시작한다.

➌

v

가

src

가 아닐 때까지

v

를

path

에 넣으면,

src

에서

target

까지 찾은 노드의 역방향 리스트가 된다.

➍

node_from[src][v]

에 기록된 대로

v

가 이전 노드가 되도록 설정한다.

➎

v

가

src

와 같다면,

while

루프는 종료하고

path

가 완전해지도록

src

를 추가한다.

➏

src

에서

target

까지 알맞은 순서로 나타나도록 리스트를 뒤집는다.

➐

node_from[target]

이

None

이면

target

은

src

에서 도달 가능하지 않다는 것이다.

7.9

요약

그래프는 지리 정보에서 소셜 네트워크의 관계 정보까지 다양한 애플리케이션 도메인을 모델

링할 수 있다. 그래프의 간선은 방향이 있거나 없을 수 있고, 간선은 숫자 가중치를 저장할 수

있다. 그래프가 주어지면 자연스럽게 여러 흥미로운 질문들이 생긴다.

●

그래프가 연결되어 있는가? 깊이 우선 탐색을 사용해 그래프 내 모든 노드가 방문되었는지 확인해보자.

●

유향 그래프는 순환을 포함할 수 있는가? 깊이 우선 탐색을 사용해 순환 유무를 검출하기 위해 탐색하

는 동안 추가 상태를 관리해보자.

●

그래프의 두 노드

u

와

v

가 주어지면, 포함하는 간선 개수 측면에서

u

에서

v

까지의 최단 경로는 무엇일

까? 너비 우선 탐색을 사용해 문제를 해결해보자.

●

가중 그래프와 시작 노드 ...