[자료구조] graph

1. graph란?

노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료 구조 ex) 지도, 지하철 노선도, 선수 과목 등을 표현 할 수 있는 자료구조.

 

크게 아래 방식으로 구분함.

- 방향 그래프 vs 무방향 그래프

- cyclic vs acyclic (싸이클의 존재 유무)

 

 

2. graph 용어 정리

정점(vertex): 위치라는 개념. (node 라고도 부름) 간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름) 인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름) 진출 차수(out-degree): 방향 그래프에서 외부로 향하는 간선의 수 (외차수 라고도 부름) 방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수) 경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우 사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우

 

 

3. graph 구현

1) 인접 행렬

그래프를 2차원 배열로 표현. 노드 간 서로 연결되었으면 1, 연결되어있지 않으면 0 으로 표현.

✅ 인접행렬 장점

1. 2차원 배열 안에 모든 정점들의 간선 정보를 담기 때문에 배열의 위치를 확인하면 두 점에 대한 연결 정보를 조회할 때 O(1) 의 시간 복잡도면 가능.

2. 구현이 비교적 간편.

✅ 인접행렬 단점

1. 모든 정점에 대해 간선 정보를 대입해야 하므로 O(n²) 의 시간복잡도가 소요.

2. 무조건 2차원 배열이 필요하기에 필요 이상의 공간이 낭비.

 

2) 인접리스트

배열에 모든 노드를 집어 넣고, 인접한 노드들은 인접리스트로 저장한다.

✅ 인접리스트 장점

1. 정점들의 연결 정보를 탐색할 때 O(n) 의 시간이면 가능하다. (n: 간선의 갯수)

2. 필요한 만큼의 공간만 사용하기때문에 공간의 낭비가 적다.

✅ 인접리스트 단점

1. 특정 두 점이 연결되었는지 확인하려면 인접행렬에 비해 시간이 오래 걸림. (배열보다 search 속도느림)

2. 구현이 비교적 어려움.

 

 

4. graph 탐색

1) 깊이 우선 탐색 (DFS, Depth First Search)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다. 사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다. 깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단하다.

stack을 이용해 구현한다.

 

2) 너비 우선 탐색 (BFS, Breadth First Search)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다. 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다. Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다. 너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색

queue를 이용해 구현한다.