[자료구조] 그래프

 

1. 기본 개념

노드와 노드를 연결하는 간선을 하나로 모아 놓은 자료 구조, 연결되어 있는 객체 간의 관계를 표현하는 자료구조이다.

예) 지하철 노선도, 네트워크 연결, 도로, 페이지 랭크

 

2. 그래프 용어 정리

• 정점(node): 위치의 개념
• 간선(edge): 위치 간의 관계, 노드를 연결하는 선
• 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수

 

3. 종류

• 무방향 그래프(양방향)
  • (A, B)는 (B, A) 동일
• 방향 그래프
  • <A, B>는 <B, A>는 다름
• 가중치 그래프
  • 그래프의 간선에 비용(가중치)가 부여된 그래프
  • 최소 비용, 최단 경로 등을 찾는 경우
• 연결 그래프
  • 무방향 그래프의 모든 정점 쌍에 대해 항상 경로가 존재하는 경우
• 비연결 그래프
  • 무방향 그래프의 특정 정점 쌍 사이에 경로가 존재하지 않는 경우
• 사이클 그래프
  • 시작 정점과 종료 정점이 동일한 경우
• 비순환 그래프
  • 사이클이 존재하지 않는 그래프
• 완전 그래프
  • 그래프의 모든 정점이 간선으로 모두 연결되어 있는 그래프

4. 특징

• 아래 트리와의 차이를 비교하면 그래프의 특징을 확인할 수 있다.

트리의 각 요소

5. 구현

 

• 인접행렬
  • 그래프의 노드를 2차원 배열로 만든 것, 노드 간 연결이 되어 있는 경우 1, 연결되어 있지 않은 경우 0의 값으로 채운다.
• 인접리스트
  • 그래프의 노드를 리스트로 표현한 것, 노드 간 연결이 되어 있는 경우 해당 노드의 인덱스에 위치한 리스트에 연결된 노드 번호를 삽입해주면 된다.

공간 복잡도

인접 행렬 : O(V^2)

인접 리스트 : O(V + E)

 

시간 복잡도

1. 두 노드가 연결되었는지 확인하는데 걸리는 시간

인접 행렬 : O(1)

인접 리스트 : O(V)

 

2. 한 노드에 연결된 모든 노드들을 확인하는데 걸리는 시간이다.

인접 행렬 : O(V)

인접 리스트 : O(E)

6. 그래프 탐색

 

• 너비 우선 탐색(BFS)
  • 한 노드에서 시작해서 인접한 모든 노드를 먼저 탐색하며 뻗어 나가는 방법이다.
  • 주로 queue 자료구조를 사용해 구현한다.
  • 주로 경로 찾기, 그 중 최단 경로를 찾을 때 많이 사용된다.
• 깊이 우선 탐색(DFS)
  • 한 노드에서 시작해 해당 분기를 모두 탐색한 뒤 다음 분기로 넘어가 탐색을 이어 나가는 방법이다.
  • 재귀 호출 또는 스택을 통해 구현한다.
  • 주로 모든 노드를 방문하고자 하는 경우 사용된다.

7. 기타

면접에선 그래프 관련해서 어떤 질문을 받을 수 있을까?

• 그래프와 트리의 차이점
• 연결그래프와 완전그래프의 차이점
• 최소신장트리를 찾는 알고리즘은 어떤 것들이 있는지