Graph

✔️ 그래프

◾그래프는 정점과 간선으로 이루어진 자료구조이다.

◾ 연결되어 있는 정점 간의 관계를 표현할 수 있다.

◾ 무방향 그래프 : 연결 관계에 있어서 방향성이 없는 그래프

◾ 방향 그래프 : 간선에 방향정보가 포함된 그래프

◾ 완전 그래프 : 각각의 정점에서 다른 모든 정점을 연결한 그래프

◾ 가중치 그래프 : 간선에 가중치 정보가 있는 그래프

 

✔️ 그래프를 구현하는 두 가지 방법

◾ 인접 행렬(adjacent matrix) 기반 그래프 : 정방 행렬을 활용

◾ 인접 리스트(adjacent list) 기반 그래프 : 연결 리스트를 활용

 

인접 행렬(adjacent matrix) 기반 그래프

 

 

인접 리스트(adjacent list) 기반 그래프

✔️ 그래프의 탐색

 

1️⃣ 깊이 우선 탐색(Depts First Search, DFS)

◾ 깊이 우선 탐색은 탐색의 각 과정에서 가능한 한 그래프 안으로 '깊이' 들어가려고 시도하며, 막힌 정점에 도달하지 않는 한 뒤로 돌아가지 않는다.

◾ 각 정점을 방문할 때마다 모든 인접 정점을 하나씩 검사하다가, 아직 방문하지 않은 정점이 있다면 그 정점을 방문한다.(반복)

◾ 이 과정을 반복하다가 더 이상 갈곳이 없는 막힌 정점에 도달하면 포기하고, 마지막에 따라왔던 간선을 따라 뒤로 돌아간다.

◾ 깊이 우선 탐색의 중요한 특성은 더 깊이 들어갈 정점이 없다면, 이전정점 으로 돌아간다는 점이다.

◾ 위를 구현하기 위해서는 지금까지 거쳐온 정점들을 모두 저장해 둬야한다. 재귀 호출을 사용하면 이를 간단하게 할 수 있다. (재귀 호출한 함수가 종료하면 호출한 위치로 다시 돌아가기 때문이다.)

 

 

---

2️⃣ 너비 우선 탐색(Breadth First Search, BFS)

◾ 너비 우선 탐색은 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘이다.

◾ 너비 우선 탐색은 각 정점을 방문할 때마다 모든 인접 정점들을 검사한다.

◾ 이 중 처음 보는 정점을 발견하면 정점을 저장한다.(=방문한다. = 큐에 넣는다.)

◾ 인접한 정점을 모두 검사하고 나면, 지금까지 저장한 목록에서 다음 정점을 꺼내서 방문한다.(큐에서 뺀다.)

◾ 목록에 먼저 넣은 정점은 항상 먼저 꺼내야한다. 따라서 정점 목록으로 큐를 사용하면 된다.

◾ 너비 우선 탐색은 대개 딱 하나의 용도로 사용된다. 바로 그래프에서 최단 경로 문제를 푸는 것이다.(가중치가 없는 그래프에서의 최단 경로를 찾을 수 있다.)

 

 

⏱️ DFS와 DFS의 시간 복잡도

◾ DFS, BFS  둘 다 모든 정점을 탐색하기 때문에 시간 복잡도는 아래와 같다.

◾ 인접 리스트 : O(V+E) -> O(N) ( V : 정점의 개수, E : 간선의 개수)

◾ 인접 행렬 : O(V^2)

 

👀 시각화

 

DFS 시각화

 

 

 

 

BFS 시각화