대표적인 그래프 탐색 알고리즘 DFS/BFS 이론

Before

 

그래프(Graph)

Node와 그 노드(or vertex)간의 선(edge)으로 이루어진 자료 구조를 의미함. Tree 도 Graph의 일종.

Node는 그 안에 value가 있다. 여려 value가 있을 수도 있다. 주로 node를 구분하기 위한 key를 가지고 있음.

edge는 node간의 관계를 의미한다. 방향이 있을 수 있고, 그 edge의 weight(가중치)가 있을 수 있다.

edge로 연결된 node를 adjacent node(인접 노드)라고 한다.

 

그래프를 프로그래밍에서 크게 2가지 방식으로 표현할 수 있다.

 

1. 인접 행렬 방식 : 2차원 배열로 각 노드간의 연결관계를 표현하는 방식. n개의 node가 있을 때 n*n의 matrix를 만들어 각 값에 연결 관계를 표현한다. weight가 있는 경우 weight 값을, 아닌 경우 0,1로 표현한다.

                              모든 관계를 다 저장하기 때문에 메모리가 많이 사용된다. (node가 많아질 수록 0이 엄청 많게 됨)

                              두 노드가 연결되었는지는 한 번에 확인할 수 있다.

 

2. 인접 리스트 방식 : 각 노드에서 연결된 노드에 대한 정보를 차례로 연결해서 저장한다.

                                 행렬 방식에 비해 메모리를 효율적으로 저장한다.

                                 두 노드가 연결되었는지 확인하기 위해 리스트 탐색이 필요하다.

 

그래프 예시

 

•  인접 행렬 방식

node	0	1	2
0	0	3	7
1	3	0	0
2	7	0	0

 

• 인접 리스트 방식

인접 리스트 방식

 

 

 

DFS

 

깊이 우선 탐색 (Depth First Search) 그래프의 가장 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

탐색을 수행할 때 걸리는 시간 : node가 N개일 때 O(N)

 

시작 node를 Stack에 넣고 시작.

시작 node에서 방문하지 않은 인접 node가 있으면 인접 node를 Stack에 넣는다. (주로 번호가 낮은 순부터 탐색)

한 번 방문한 node는 다시 삽입되지 않도록 체크해둔다. 

Stack의 가장 위에 있는 node를 다시 시작으로 두고 반복한다.

만약 방문하지 않은 인접 node가 없을 시 스택의 최상단 node를 꺼낸다.

위와 같은 방식으로 시작 node가 주어졌을 때 그래프 전체를 탐색할 수 있다.

 

Stack을 이용하지만 재귀함수를 이용해 구현할 수도 있음.

 

 

 

BFS

 

너비 우선 탐색 (Breadth First Search) 시작 노드에서 가장 가까운 노드부터 탐색하는 알고리즘이다.

탐색을 수행할 때 걸리는 시간 : node가 N개일 때 O(N)

 

시작 node를 Queue에 넣고 시작.

시작 node를 Queue에서 꺼내고 인접한 node 중 방문하지 않은 모든 node를 모두 Queue에 삽입한다.

한 번 방문한 node는 다시 삽입되지 않도록 체크해둔다.

Queue에서 노드를 꺼내 해당 노드의 인접 node중 방문하지 않은 것을 모두 Queue에 삽입하는 것을 반복한다.

위와 같은 방식으로 시작 node가 주어졌을 때 그래프 전체를 탐색할 수 있다.

 

Tip : 시간 복잡도는 같지만 일반적인 경우 수행 시간은 BFS가 조금 더 빠르다. DFS는 보통 재귀함수를 이용해 구현하기 때문. stack으로 구현하면 시작복잡도가 조금 줄어든다.

 

 

기본 그래프와 DFS/BFS 구현 코드 : maru20564.tistory.com/7

C++ 그래프 탐색 알고리즘 기본 DFS/BFS 구현