9. 그래프 순회

그래프 순회

순회: 모든 정점과 간선을 검사하여 그래프를 탐색하는 체계적인 절차

깊이 우선 탐색(DFS-Depth first search)=

n개의 정점과 m개의 간선을 가진 그래프에 O(n+m)의 시간 소요

해결 가능한 문제

1. G의 모든 정점과 간선을 방문
2. G가 연결 그래프인지 확인
3. G의 연결 요소들을 계싼
4. G의 신장 숲을 계산
5. 이중연결요소 계산

알고리즘

기본적인 그래프에 대해 그래프의 간선을

1. 모든 정점을 Fresh, 즉, 아직 방문하지 않았음으로 표시해준다.
2. 모든 간선 또한 방문하지 않았음으로 만들어준다.
3. 모든 정점을 반복문으로 돌아가며 방문하지 않았으면 rDFS(DFS의 재귀함수)를 호출한다

rDFS

1. 들어온 해당 정점을 방문했다고 표시한다.
2. 다음 정점이 방문하지 않았느냐 확인, 방문하지 않았으면 들어가서 재귀호출
3. 방문했으면 뒤로 돌아가기

신장트리(DFS tree)

위와 같은 방식으로 라벨링된 간선과 정점을 신장트리라 부른다

응용

신장숲, 연결요소, 경로, 사이클, 최단경로, 이중 연결요소

너비 우선 탐색(BFS-breadth first search)

레벨 순회와 유사한 방식

n개의 정점과 m개의 간선을 가진 그래프에 O(n+m)의 시간 소요

해결 가능한 문제

1. G의 모든 정점과 간선을 방문
2. G가 연결 그래프인지 확인
3. G의 연결 요소들을 계싼
4. G의 신장 숲을 계산
5. G의 최단경로 계산

(DFS와 같다)

기본적인 그래프에 대해 그래프의 간선을

1. 모든 정점을 Fresh, 즉, 아직 방문하지 않았음으로 표시해준다.
2. 모든 간선 또한 방문하지 않았음으로 만들어준다.
3. 모든 정점을 반복문으로 돌아가며 방문하지 않았으면 rBFS를 호출한다

rBFS

1. 들어온 해당 정점을 방문했다고 표시한다.
2. 다음 정점이 방문하지 않았느냐 확인, 방문하지 않았으면 메모리에 삽입
3. 연결된 인접 정점을 모두 확인하고 메모리의 다음 정점으로 이동
4. 모든 메모리의 정점이 없어지면 나간다.