그래프 표현, DFS/BFS, 최단경로

그래프란?

그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조로, 데이터간의 관계를 표현하는데 사용된다.

정점 : 데이터(노드)

간선 : 정점과 정점을 연결하는 관계

 

그래프 표현방법

그래프는 메모리에서 주로 두 가지 방식으로 표현된다.

1. 인접 리스트(Adjacency List)

각 정점마다 연결된 정점들을 리스트 형태로 저장하는 방식이다.

특징

• 실제로 연결된 간선만 저장 → 메모리 효율 좋음
• 특정 정점에 연결된 노드 탐색이 빠름
• 일반적으로 가장 많이 사용되는 방식

시간/공간 특징

• 공간복잡도 : O(V+E)
  • V : 정점 개수
  • E : 간선 개수
• 특정 정점의 인접 노드 탐색: O(연결된 간선 수)

2. 인접 행렬(Adjacency Matrii)

정점 수 x 정점 수 크기의 2차원 배열을 사용하여 연결 여부를 저장하는 방식이다.

특징

• 두 정점이 연결되어 있는지 즉시 확인 가능
• 구현이 단순함
• 간선이 적은 경우 메모리 낭비 발생

시간/공간 특징

• 공간 복잡도 : O( V² )
• 특정 간선 존재여부 확인 : O(1)

그래프 탐색 : DFS / BFS

그래프를 표현한 이후에는 그것을 탐색하는 알고리즘이 있다.

DFS(Depth - First Search )

• 한 방향으로 깊게 탐색 후 되돌아오는 방식
• 스택 또는 재귀 사용

특징

• 모든 경로를 탐색해야 하는 문제에 적합

BFS ( Breadth - First Search )

• 가까운 정점부터 순차적으로 탐색
• 큐 사용

특징

• 가중치가 없는 그래프에서 최단거리 보장

최단 경로 알고리즘

BFS 기반 최단 경로

• 가중치가 없는 경우 사용
• BFS 자체가 최단 거리 보장

다익스트라

• 가중치가 있는 그래프에서 사용
• 우선순위 큐 기반
• 음수 가중치는 사용 불가

플로이드 워셜

• 모든 정점 간 최단경로 계산
• 시간 복잡도 O( N³)