[자료구조] 그래프 순회 (graph traversals), 그래프 표현

그래프 순회 방법 (graph traversal)

 

그래프의 각 정점(node)을 방문하는 그래프 순회(graph traversals) 방법에는 크게

• 깊이 우선 탐색 (DFS : depth first search)
• 너비 우선 탐색 (BFS : breadth first search)

방법이 있다.

 

 

DFS는 수학자 찰스 피에르 트레모가 미로찾기를 풀기 위한 전략을 찾다가 고안한 것으로 알려져있으며, BFS보다 널리 쓰인다.

코딩테스트에서도 대부분의 그래프 탐색은 DFS로 진행한다고 한다.

• 자료구조 수업을 들으며 DFS, BFS를 이용하여 미로문제를 풀었던 경험이 있는데,
• 수학자가 미로문제를 풀다가 DFS를 고안했다니 신기하다.

 

DFS는 주로 stack이나 재귀를 이용하여 구현하고, back-tracking을 통해 뛰어난 효용을 보인다.

반면 BFS는 주로 queue를 이용하여 구현하고, 그래프의 최단 경로를 구하는 문제에서 주로 사용된다.

• DFS로 search 했을 때의 최단경로는 global minimum을 보장하지 않기 때문에
• global minimum을 보장하는 BFS를 이용하여 최단 경로를 구하는 것 같다.

---

그래프를 표현하는 방법

그래프를 표현하는 방법에는 크게

• 인접 행렬 (adjacency matrix)
• 인접 리스트 (adjacency list)

방법이 있다.

 

두 방법에 대해 차이를 기록한 글 중 잘 정리된 글이 있어 공유한다.

sarah950716.tistory.com/12

[그래프] 인접 행렬과 인접 리스트

 

내 글을 내가 다시 읽었을 때 다시 기억하기 쉽도록 짧게 정리해보려고 한다.

 

1. 인접행렬

• 정의
  • 인접행렬은 그래프의 연결관계를 이차원 배열으로 나타내는 방식
  • 노드의 개수가 V개라면, 인접행렬의 크기는 V*V
  • adj[i][j] : 노드 i에서 노드 j로 가는 간선이 있으면 1, 없으면 0
• 특징
  • 방향성 그래프에서는 인접행렬이 비대칭행렬이다.
  • 무방향성 그래프에서는 인접행렬이 대칭행렬이다.
• 장점
  • 구현하기 쉽다
  • 노드 i와 노드 j가 연결되어 있는지 확인하기 위해서는 adj[i][j]의 값만 확인하면 된다. = O(1)
• 단점
  • 특정 노드와 연결된 노드를 확인하고 싶은 경우 O(V)의 시간이 걸린다 (여기서 V = 노드의 개수)
  • 전체 노드에 대한 탐색 : O(V*V)

 

2. 인접리스트

• 정의
  • 그래프의 연결관계를 리스트로 나타내는 방식
  • adj[i] : 노드 i와 연결된 노드를 원소로 갖는 리스트
• 장점
  • 간선의 개수에 비례하는 메모리만 차지 (인접행렬은 노드의 개수*노드의 개수만큼의 공간 필요)
  • 전체 노드에 대한 탐색 : O(E) (cf. 인접행렬은 O(V*V) : 여기서 E = edgd의 개수, V = node의 개수)
• 단점
  • 노드 i와 노드 j가 연결되어 있는지 확인하기 위해서는 adj[i]를 탐색해야 한다 = O(V)

 

 

인접행렬과 인접리스트의 장/단점이 정반대이다.