코딩 테스트 합격자 되기 스터디 6주차 : 그래프

그래프

노드와 간선을 이용한 비선형 데이터 구조

그래프 용어

- 노드, 간선, 가중치

그래프 특징과 종류

- 방향 그래프, 무방향 그래프

 

그래프의 구현(인접행렬)

- 행과 열의 인덱스로 노드의 값을 나타내고, 배열의 값은 간선의 가중치가 됨

- 노드 대비 간선이 적을 경우 메모리 공간효율이 좋지 않음

인접행렬 표현방식

- 가중치가 없는 간선을 나타내는 경우 간선이 있으면 1, 없으면 0으로 표기

- 노드가 100개이고 간선이 1개인 경우에도 100 * 100 행렬이 필요함(메모리 낭비)

- 특정 노드 사이에 간선존재 여부를 한번에 알 수 있음

그래프의 구현(인접 리스트)

- 특정 시작 노드를 기준으로 연결된 노드들을 리스트로 연결하는 방식

- 실제 그래프의 노드 갯수만큼만 추가하므로 메모리 낭비 없음

- 특정 노드에 모든 노드가 연결된 경우, 탐색시 O(N)이 될 수 있음(드문 케이스)

인접 리스트 표현방식

- 노드 개수 만큼 배열을 준비한다. (각 배열 인덱스는 시작 노드 의미)

- 각 배열의 인덱스는 시작 노드를 나타냄, 해당 인덱스에 연결된 노드 추가

 

인접 행렬 VS 인접 리스트

	공간 복잡도	특정 정점의 간선을 찾는 경우	그래프의 모든 간선을 찾는 경우
인접 행렬	O(V^2)	O(1)	O(V^2)
인접 리스트	O(V+E)	O(E), 대부분은 O(E/V)	O(V+E)

 

- 노드의 갯수가 많을 때는 인접 리스트를 써야한다.

- 특정 정점의 간선을 찾는 경우가 많으면 인접행렬 고려

- 뭘 써야 할지 모른다면 인접 리스트

 

그래프의 탐색

그래프를 정해진 순서로 순회하는 방법

깊이 우선 탐색(DFS)

 

- 더 이상 탐색할 노드가 없으면 최근에 방문했던 퇴각 후, 가지 않은 노드 방문

 

깊이 우선 탐색 구현하기

1. 계속해서 깊이 탐색할 수 있어야 함

2. 더 이상 깊은 곳이 없는 경우, 가장 최근에 방문했던 노드로 퇴각해야 함

3. 이미 방문한 노드는 중복해서 방문하지 않아야 함

 

가장 최근에 방문했던 노드로 접근 방법

- LIFO로 동작하는 스택 활용

- 방문할 노드는 푸시, 방문한 노드는 팝 하면 스택의 top은 가장 최근에 방문한 노드

- 함수의 call stack도 stack과 같이 동작하므로 재귀함수로 구현하는 경우가 많음

- visited 배열을 활용해서 방문 여부를 확인 후 방문함

 

그래프의 탐색(깊이 우선 탐색, with 재귀)

- 현재 dfs(D)가 호출된 사오항이고 연결된 노드 중, 더 이상 방문할 노드가 없음 따라서 함수 종료

- call stack에 의해 dfs(B)의 남은 부분이 호출됨

- B와 연결된 노드중 아직 방문하지 않은 노드 E 확인 후 dfs(E) 호출, 노드 E 방문 처리

너비 우선 탐색(BFS)

- 현재 위치에서 가장 가까운 노드부터 방문하고 다음 노드로 넘어감, 노드 {A}에서 가장 가까운 노드 {B, C}를 방문(간선 1개를 거쳐 갈 수 있음)

 

너비 우선 탐색 구현하기

1. 루트 노드부터 시작해서, 가장 가까운 노드들부터 방문할 수 있어야 함

* 루트노드방문 -> 1개 간선으로 갈 수 있는 노드 방문 -> 2개 간선으로 갈 수 있는 노드 방문 ...(모든 노드를 방문할 때까지 반복)

 

가장 가까운 노드부터 방문하는 방법: FIFO로 동작하는 큐를 활용

1. 시작 노드 푸시

2. 팝 후 방문 처리 이후, 현재 노드에서 연결된 노드 중 방문하지 않은 노드 모두 푸시 -> 모든 노드를 방문할 때까지 2.를 반복

 

깊이 우선 탐색 vs 너비 우선 탐색

- 백트래킹은 깊이우선 탐색에만 존재

* 스토쿠 문제, 1~5를 사용해서 합이 10이 되는 모든 경우

- 너비 우선탐색으로 찾은 해만 최적해를 보장

* 시작점에서 끝지점 까지 가는데 최소 스텝수

- 너비우선탐색은 모든 다음노드를 큐에 푸시하므로 깊이우선탐색보다 메모리 사용량이 높음

- 물론 둘다 되는 경우가 존재... 애매하면 깊이 우선 탐색 먼저 시도

 

최단경로 알고리즘

두 노드를 잇는 가중치의 합을 최소로 하는 경로를 찾는 알고리즘

 

출처

코딩 테스트 합격자 되기 - C++