DS_2. Graph

Graph의 구조

그래프(Graph)는 정점과 간선으로 이루어진 자료구조이다. 자료구조의 그래프는 일반적으로 연상되는 선 그래프가 아닌, 네트워크망 형태를 가지고 있다. 그래프는 다음과 같은 부분으로 구성되어 있다.

• 정점(vertex): 데이터가 저장된 위치
• 간선(edge): 정점 간의 관계
• 인접 정점(adjacency vertex): 두 정점 간에 간선이 직접 이어져 있는 정점

Graph 용어

이러한 그래프를 설명하는 용어는 다음과 같다.

• 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
• 진입차수(in-degree): 방향 그래프에서 외부 노드에서 들어오는 간선의 수
• 진출차수(out-degree): 방향 그래프에서 한 노드에서 외부로 향하는 간선의 수
• 자기 루프(self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우
• 사이클(cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있는 형태

또한 그래프는 다음과 같이 다양한 형태로 나눌 수 있다.

• 무향그래프(undirected graph): 두 정점을 연결하는 간선에 방향이 없는 그래프
• 단방향 그래프(directed graph): 두 정점을 연결하는 간선에 방향이 존재하는 그래프
• 가중치 그래프(weighted graph): 두 정점을 이동할 때 비용이 드는 그래프
• 완전그래프(complete graph): 모든 정점이 간선으로 연결된 그래프

Graph의 구현

Graph의 구현은 다음의 두 가지 방식을 상황에 맞게 사용할 수 있다.

인접행렬 방식

인접행렬은 그래프의 노드를 2차원 배열로 만든 것으로, 인접한 정점은 1, 인접한 정점이 없다면 0으로 표시한다.

• 인접행렬 장점
  구현이 비교적 간단하며, 2차원 배열 안에 모든 정보를 담기 때문에 두 점에 대한 연결 정보를 쉽게 조회할 수 있다.

• 인접행렬 단점
  모든 정점에 대해 간선 정보를 대입해야 하므로 간선의 수에 비해 정점의 수가 지나치게 많은 경우 효율이 떨어진다.

인접리스트 방식

인접리스트란 그래프의 정점을 리스트로 표현한 것으로, 정점의 배열을 만들어 관계를 설정해 주는 방식으로 구현한다.

• 인접리스트 장점
  실제 연결된 정점에 대한 정보만 저장하므로, 간선의 수에 비례하는 메모리 사용만으로 구현할 수 있다.

• 인접리스트 단점
  구현이 비교적 어렵고, 특정 두 점이 연결되었는지 확인하려면 인접행렬에 비해 시간이 오래 걸린다.

Graph 탐색

그래프 탐색은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다. 이러한 탐색은 다음의 두 가지 방법으로 나누어진다.

• 깊이 우선 탐색(DFS, Depth-First Search)은 임의의 정점에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 이러한 방식은 한 방향으로 계속해서 가다가 막히면 가까운 갈림길에서 다른 방향으로 진행하는 미로찾기와 유사하다.

• 너비 우선 탐색 (BFS, Breadth-First Search)은 임의의 정점에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. 이러한 방식은 두 정점 사이의 최단 경로를 찾고 싶을 때 사용할 수 있다.

그렇다면 어떠한 상황일 때 각각의 방식을 사용해야 할까? 만약 모든 정점을 한 번씩 탐색해야 한다면 DFS를 사용하는 것이 적합하다. 그러나 페이스북과 같이 수억 명의 관계가 존재하는 그래프에서 특정인의 관계만을 찾는 경우라면 BFS가 적합할 것이다.

참고
코딩팩토리 - 자료구조 그래프(Graph)란 무엇인가?
공대사람님의 블로그 - 인접 행렬과 인접 리스트
깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)