[24.06.12] 99클럽 코테 스터디 24일차 TIL - 그래프 자료구조, BFS와 DFS 각기 사용하면 좋을 때

1. 그래프 자료구조

그래프 자료구조는 노드와 엣지(간선)으로 이루어진 구조이다.

그래프는 기준에 따라 다양한 종류로 분류가 된다. 

 

1.1 연결 방식에 따른 분류

단방향 그래프

• 간선이 방향성을 가지는 그래프.
• 즉 각 간선은 한 노드에서 다른 노드로의 단방향 관계를 나타낸다.
• ex) 작업 A가 완료된 후에만 작업 B를 시작할 수 있는 경우

양방향 그래프

• 간선이 양방향인 관계를 나타내는 그래프.
• 각 간선은 두 노드간의 쌍방향 연결을 나타내며, 노드 A와 B가 연결되있다면 A에서 B로, B에서 A로 모두 이동이 가능
• ex) 사용자 A와 B가 친구관계라면 A에서 B로, B에서 A로 모두 연결되어 있음.

무향 그래프

• 연결 간 방향이 정해지지 않은 그래프.
• 각 간선은 노드 간의 관계만을 나타낸다.

1. 2 연결 가중치에 따른 분류

가중치 그래프

• 간선에 가중치가 존재하는 그래프 
• 가중치는 간선의 비용, 거리, 시간 등을 나타낼 수 있다.
• ex) 각 도로는 두 도시를 연결하며, 도로의 거리가 가중치로 나타낼 수 있다.

 

비가중치 그래프

• 간선에 가중치가 따로 없는 그래프
• 간선이 연결의 유무만을 나타낸다. 
• ex) 사람들 간의 관계를 나타낼 때, 각 연결은 단순히 관계의 존재만을 나타내고 관계의 강도를 나타내지 않는다.

 

2. DFS와 BFS

2.1 DFS(깊이 우선 탐색)

DFS은 한 노드에서 출발하여 가능한 깊이 탐색한 후, 더 이상 갈 수 없을 때 백트래킹하여 다시 다른 경로를 탐색하는 방식이다.

 

DFS를 사용하기 좋은 경우

• 경로 찾기 : 출발점에서 도착점까지의 경로를 찾는 경우
• 사이클 검출 : 방향,무방향 그래프 모두에서 사이클을 유무를 판단해야하는 경우
• 탐색의 깊이가 중시될 경우

.2 BFS(너비우선탐색)

BFS는 그래프의 한 노드에서 시작하여 인접한 모든 노드를 탐색한 후, 다음 깊이의 노드를 탐색하는 방식이다.

 

BFS를 사용하기 좋은 경우

• 최단 경로 찾기 : 무가중치 그래프에서 최단(최소) 경로를 찾는 경우
• 레베 순 탐색 : 트리 구조에서 각 레벨의 노드를 차례로 탐색하는 경우
• 가장 가까운 해답 찾기 : 여러 해답이 존재하고 가장 가까운 해답을 찾아야 하는 경우