[알고리즘개념]DFS/BFS와 인접행렬/인접리스트

graph는 정점(vertex)과 간선(edge)으로 이루어진 하나의 자료구조이다.

이 그래프를 탐색할 때는 해당 정점에 연결된 정점을 우선적으로 차수를 늘려가며 탐색하는 깊이 우선 탐색(DFS; Depth Firsh Search)과 해당 차수에 있는 모든 정점을 탐색하고 다음 차수로 넘어가는 너비 우선 탐색(BFS; Breadth First Search)을 사용할 수 있다.

 

위의 그림에서 DFS는 0에서 이어진 1로, 1에서 이어진 3으로 이동했다가 더이상 이어진 정점이 없으므로 상위 차수로 이동해 1에서 이어진 또다른 정점인 4로 이동한다. BFS는 반대로 0에서 이어진 1로 이동했다가 같은 차수의 또다른 정점인 2로 이동한 후 다음 차수의 첫번째 정점인 3으로 넘어간다.

 

일반적으로 DFS는 LIFO 방식인 Stack 자료구조를, BFS는 FIFO 방식인 Queue 자료구조를 활용한다.

 

정점들을 간선이 잇는 형태를 띠는데, 이를 나타내는 방법으로 인접행렬과 인접 리스트가 있다.

인접행렬은 2차원 배열에서 각 정점에 연결된 정점을 번호에 해당하는 항마다 1로 표시하는 식으로 나타낸다. 위의 트리 형태 그래프를 인접행렬로 나타내면 다음과 같다.

graph = [[0, 1, 1, 0, 0, 0, 0],
         [1, 0, 0, 1, 1, 0, 0],
         [1, 0, 0, 0, 0, 1, 1],
         [0, 1, 0, 0, 0, 0, 0],
         [0, 1, 0, 0, 0, 0, 0],
         [0, 0, 1, 0, 0, 0, 0],
         [0, 0, 1, 0, 0, 0, 0]]

인접리스트는 각 정점에 연결된 정점의 번호를 그대로 표시한다.

graph = [[1, 2],
         [0, 3, 4],
         [0, 5, 6],
         [1],
         [1],
         [2],
         [2]]