그래프 탐색 알고리즘

1.그래프란?

그래프는 리스트같은 구조와 달리 순차적이거나 선형적이지 않은 구조다. 정점(node)와 간선(edge)으로 구성되어있다. 쉽게 정점은 하나의 구역, 간선은 구역과 구역을 이어주는 길이라고 생각하면 된다.

2.인접행렬과 인접리스트

그래프 탐색에 사용되는 두 가지 자료가 있다.

• 인접행렬(Adjacency Matrix) : 정점개수만큼 행,열 개수를 가진 행렬이다. 즉, 모든 정점간의 정보를 표현할 수 있다.
• 인접리스트(Adjacency List) : 정점이 가진 간선에 대한 정보만 담은 리스트다.

그림을 통해 간단히 이해한다.

위 자료를 상황에 맞게 이용하면 그래프를 탐색하는데 도움이 된다.

3.DFS

그래프 탐색 알고리즘의 한 종류인 DFS(Depth Fisrt Search)는 깊이 우선 탐색으로 하나의 길을 정하고 그 길을 가장 깊이 들어갈 수 있을 때까지 들어가며 탐색을 진행하다 막다른 곳에 다다랐을 때 탐색해온 길에서 파생된 다른 길이 있는 곳을 찾아 그 곳에서 지금까지의 탐색을 반복하는 방식이다.

DFS는 재귀함수나 스택을 이용할 수 있다.

• 재귀함수를 이용하는 경우(+인접리스트 사용 경우)

1. 함수를 생성하고 파라미터로 첫번째 탐색 정점, 탐색일지를 담을 리스트를 받는다.
2. 탐색일지 리스트에 탐색 정점 추가
3. 인접리스트에서 탐색 정점에 인접한 정점 정보를 for문으로 순회한다.
4. 순회 중 해당 정점이 아직 탐색일지에 없다면 탐색일지에 추가, 탐색일지에 있다면 pass
5. for문이 종료되면 탐색일지를 리턴한다.

• 스택을 이용하는 경우(+인접리스트 사용 경우)

1. 스택을 생성하고 첫번째로 탐색할 정점을 스택에 넣는다.
2. stack이 비어있지 않다면 반복되는 while문을 생성한다.
3. stack에서 정점을 하나만 뺀다.(stack이니까 가장 최근에 넣은 정점) 만약 이미 탐색한 정점이라면 밑에 단계 무시하고 stack에서 정점 하나 더 뺌.
4. 빼낸 정점에 대한 간선정보를 얻기 위해 인접리스트에 접근한다.
5. 인접리스트에 간선정보가 있으면 stack에 간선정보 추가, 간선정보가 없으면 pass
6. while문이 stack이 빌때까지 계속된다면 첫번째로 탐색한 정점과 이어져있는 모든 정점은 DFS로 탐색이 된다.

4.BFS

그래프 탐색 알고리즘의 한 종류인 BFS(Breadth First Search)는 너비 우선 탐색으로 DFS와 달리 하나의 길을 정하고 깊이 들어가는 식이 아니라, 최대한 넓게(많은 길) 탐색하는 방식이다.

BFS는 큐를 이용할 수 있다.

• 큐를 이용하는 경우(+인접리스트 사용 경우)

1. 큐를 생성하고 첫번째로 탐색할 정점을 큐에 넣는다.
2. queue가 비어있지 않다면 반복되는 while문을 생성한다.
3. queue에서 정점을 하나만 뺀다.(queue니까 가장 옛날에 넣은 정점) 만약 이미 탐색한 정점이라면 밑에 단계 무시하고 queue에서 정점 하나 더 뺌.
4. 빼낸 정점에 대한 간선정보를 얻기 위해 인접리스트에 접근한다.
5. 인접리스트에 간선정보가 있으면 queue에 간선정보 추가, 간선정보가 없으면 pass
6. while문이 queue이 빌때까지 계속된다면 첫번째로 탐색한 정점과 이어져있는 모든 정점은 BFS로 탐색이 된다.