[자료구조] 14-2. 넓이 우선 탐색 알고리즘의 응용 (1)
bfs로 그래프의 거리를 측정하는 문제를 살펴보자. 맨 처음 살펴볼 문제는 '단일 출발점 최단 거리 찾기'이다. 하나의 출발점에서 시작해 다른 모든 버텍스로 가는 최단 거리를 찾는 문제다. 만약 버텍스 v0에서 버텍스 u까지 가는 경로를 v0, v1, v2...vk, u라고 한다면, 패스는 (v0, v1), (v1, v2)...(vk-1, vk), (vk. u)와 같은 엣지들의 집합이다. 이 경로의 cost는 엣지에 있는 가중치의 합으로 생각할 수 있다. 이러한 가중치 그래프가 있다고 할 때, A와 B 버텍스 사이에 가중치가 2라면, 그 사이에 버텍스를 하나 추가한다. B와 E 사이의 가중치는 3이므로 2개를 추가할 수 있다. 가중치가 w인 엣지에 대해 w-1개의 버텍스를 추가하면 동일한 거리를 가지며,..
[자료구조] 13-3. 깊이 우선 탐색 알고리즘의 응용 (2)
이중 연결 성분을 찾는 알고리즘은 크게 3단계로 나뉜다. 1. 분절점 정의1) dfn 정의2) back edge 정의3) 분절점 정의2. 분절점 찾기3. 분절점을 이용해 그래프를 이중 연결 성분으로 분해하기 dfn은 depth-first number의 약자이며, dfs를 하면서 버텍스를 방문하는 순서를 의미한다. 만약 위의 그래프에서 3번부터 dfs를 한다고 생각해보자. 버텍스 3에서 갈 수 있는 곳은 1 4 5가 있는데, 숫자가 낮은 것부터 방문하므로 1-2-4-0의 순서로 방문할 것이다. 그럼 dfn은 버텍스 3부터 1-2-4-0까지 0, 1, 2, 3, 4로 부여된다. 맨 마지막에 3번으로 다시 돌아오면 5-6-7-8-9를 방문할 것이다. 이 순서대로 또 5, 6, 7, 8, 9번 dfn이 부여된다..
