본문 바로가기
programming/algorithm

[graph] BFS,DFS

by 힐무새 2017. 7. 23.

graph를 나타내는 2가지 방식

  • 인접 행렬(Adjacency matrix)

nxn 형태의 행렬로 나타냄. M(i,j)는 정점 i와 j를 연결하는 간선이 존재한다는 의미가 된다. 무방향그래프라면 i와 j가 서로 연결된 상태이며 M(i,j)=M(j,i)인 상태이다.
저장공간은 O(n^2)이며, 어떤 노드 v에 인접한 모든 노드를 찾는것은 행렬의 한 row를 전부 탐색하는 것과 같기 때문에 O(n)이고, 어떤 간선 E(u,v)가 존재하는지 확인하는 것은 M(i,j)를 확인하면 되므로 O(1)이다.
  • 인접 리스트(Adjacency list)

정점 집합을 표현하는 하나의 배열과 각 정점마다 인접한 정점들의 연결리스트이다. 예를 들면 간선 E(1,2), E(1,5), E(5, 4)가 존재한다고 할 때 정점의 배열의 원소 중 1번 정점은 2번, 5번으로 연결된 리스트를 가지고 있게 되고 5번은 4번 정점이 헤드에 있는 리스트를 갖게 된다. 무방향그래프라면 시작 정점과 도착 정점에 모두 리스트에 추가하면 된다. 저장 공간은 정점의 개수 n과 간선의 갯수 m의 합인 O(n+m)이고, 인접 정점 검사는 O(degree(v))이다. degree(v)는 v 정점에 연결된 정점의 갯수를 나타낸 것이다. 어떤 간선 E(u,v)이  존재하는지 검사하는데 걸리는 시간은  O(degree(u))이다.


그래프 순회: 모든 노드를 방문하는 일

BFS(너비우선탐색)

너비우선탐색은 그래프에 존재하는 정점 중 같은 단계를 같는 정점을 우선 탐색하는 기법이다.  시작 정점 s를 level 1 이라고 할 때, s의 인접 정점들은 level 2라고 하고, ,level 1, level 2에 속하지 않으면서 level 2 정점과 인접한 정점을 level 3이라고 하면, 방문 순서는 level 1, level 2, level 3 순으로 진행된다. 이러한 알고리즘은 큐를 사용하여 쉽게 구현할 수 있다.

  1. 시작 정점 s를 방문했다고 기록
  2. 시작 정점 s를 큐에 삽입
  3. 큐가 비어있지 않았다면
    1. 큐로부터 원소 1개(v)를 뽑아낸다.
    2.  뽑아낸 정점 v와 인접하면서 방문하지 않은 정점들에 대해 큐에 삽입한다.
    3. 3번 반복.

참고로, BFS에서 level i에 속한 노드까지의 최단 경로는 i가 된다. (모든 간선의 거리가 1인 경우)


DFS(깊이우선탐색)

깊이우선탐색은 BFS와는 다르게 정점을 방문 할 때 그 깊이의 끝까지 방문하는 방식이다. 이는 마치 재귀호출에서 base case를 만날 때 까지 탐색을 반복하고 돌아오는 방식과 유사하다.
DFS(v,R)
  1. 시작 정점 v를 방문했다고 기록
  2. 정점 v에 대해 인접한 모든 정점 u에 대하여
    1. 만약 정점 u가 방문되지 않았다면 DFS(u,R);  


'programming > algorithm' 카테고리의 다른 글

[boj-1504]특정한 최단경로  (0) 2017.07.31
[graph]위상정렬  (0) 2017.07.25
[boj-4811]알약  (0) 2017.07.15
(Recursion) 미로 찾기  (0) 2017.07.09
Recursive(재귀 함수)  (0) 2017.07.08