그래프의 개념

🔑 그래프란 정점과 간선들로 이루어진 집합으로 표현되는 자료구조이다.

트리도 일종의 그래프라고 할 수 있다.

그래프의 종류

🔴 무방향 그래프 : 간선이 방향을 가지지 않음

🟠 방향 그래프 : 간선이 방향을 가지고 있음

🟡 가중치 그래프 : 각 간선에 가중치 정보가 포함됨. 가중치는 거리, 비용 등으로 표현 할 수 있다.

그래프의 구현

⚽ 인접 행렬 기반 그래프
각 장점간의 가중치나 간선의 유무를 행렬로 표현한다.
무방향 그래프의 경우 전치행렬이 되어도 값이 같다.

👁‍🗨 인접 리스트 기반 그래프
인접 행렬이 행렬을 이용한것과는 달리 인접 리스트로 구현한다.

💨 파이썬에서는 그냥 딕셔너리 자료형에 리스트를 넣어 쉽게 인접 리스트처럼 구현하여 사용할 수 있다.

BFS(너비 우선 탐색)

🔑 BFS는 너비 우선 탐색으로, 현재 Node(Vertex)에서 연결된 Node로 우선적으로 탐색하는 것을 뜻한다.

즉 아래 그림에서 A에서 BFS를 시작한다고 하면, B, E, I를 우선적으로 탐색하고, 그 후 B, E, I에 연결된 Node를 탐색한다.

즉 방문하는 순서는 ['A', 'B', 'E', 'I', 'C', 'F', 'H', 'J', 'D', 'G'] 순이 된다.

queue를 이용해서 구현할 수 있다.

DFS(깊이 우선 탐색)

🔑 DFS는 깊이 우선 탐색으로, 현재 Node(Vertex)에서 연결된 Node중에서 하나를 골라 더이상 진행할 수 없을때까지 탐색한다. 그 후 더이상 진행이 불가능하면, 진행이 가능한 Node 까지 되돌아 와서 탐색을 한다.

즉 위 그림에서 A에서 BFS를 시작한다고 하면, B를 우선적으로 탐색하고, 그 후 B에 연결된 Node를 탐색한다.

즉 방문하는 순서는 ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'] 순이 된다.

stack을 이용해서 구현할 수 있고, 함수의 재귀호출을 이용해서 구현할 수도 있다.