Development/알고리즘

누구나 자료구조와 알고리즘 - (13) 그래프

레오나르도 다빈츠 2023. 10. 3. 19:42

 

 

 

 

 

 

그래프

 

모든 트리는 그래프이다.

 

1.1 그래프 vs. 트리

  • 그래프는 서로 순환적으로 참고하는 노드가 있을 수 있으나 트리는 사이클이 있을 수 없다.
  • 트리는 간접접으로라도 다른 노드와 연결되지만 그래프는 완전히 연결되지 않을 수 있다.

 

1.2 용어

  • 정점(vertex): 각 노드를 정점이라고 한다.
  • 간선: 정점을 잇는 선
  • 인접한다: 간석으로 연결된 정점에 대해 서로 인접한다고 말한다.
  • 이웃: 인접한 정점

 

예제 1. 그래프를 해시테이블로 구현하기

friends = {
    "Alice" => ["Bob", "Diana", "Fred"]
    "Bob" => ["Alice", "Diana"]
    "Diana" => ["Bob"]
    "Fred" => ["Bob"]
}

 

 

1.3. 그래프 탐색

정점 찾기는 가장 흔한 그래프 연산 중 하나이다. 그래프에서 탐색은 그래프 어딘가에 있는 특정 정점을 찾는 것이다. 배열에서 값을 찾거나 해시 테이블에서 키-값 쌍을 찾는 것과 비슷하다. 하지만 탐색은 그래프에서 보다 특정한 의미를 갖는데, 그래프 내 한 정점에 접근할 수 있을 때 그 점점과 어떻게든 연결된 또 다른 특정 정점을 찾는 것이다.

 

그래프 탐색에는 깊이 우선 탐색과 너비 우선 탐색 두 방식이 널리 쓰인다.

 

 

1.3.1 깊이 우선 탐색

사이클이 있는 그래프는 모두 연결되어 있기 때문에 앞서 방문했던 정점을 기록하지 않으면 영원히 순환할 수 있다. 따라서 해시 테이블을 사용하여 정점을 방문할 때 마다 Boolean 같은 값을 사용하여 키에 할당하는 방법으로 해결할 수 있다.

1. 재귀적으로 아래로 내려가며서 탐색한다.

2. 하위에 정점이 있는 경우나 이웃이 있는 경우 호출스택에 추가해가며 깊이 우선 탐색을 재귀적으로 수행하고 모두 수행한 뒤에 더 이상 순회할 이웃이 없는 경우 하나씩 팝한다.

3. 방문한 경우 방문했다는 키를 할당한다.

4. 모든 정점마다 모든 이웃을 순회한 경우 끝이 난다.

 

 

1.3.2 너비 우선 탐색

깊이 우선 탐색과 달리 너비 우선 탐색은 재귀를 쓰지 않고 큐로 문제를 해결한다.

1. 시작 정점(루트)에 있는 인접 정점을 모두 순회하고 스택에 추가한다.

2. 그 다음 첫번째 항목을 삭제하고 삭제한 항목의 인접 정점을 순회한다.

3. 방문하지 않은 정점을 스택에 추가한다.

4. 방문한 경우 방문했다는 키를 할당한다.

5. 큐가 빌 때 까지(=모두 순회했다는 뜻) 2-4단계를 반복한다.

 

 

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

너비 우선 탐색은 시작 정점과 가장 가까운 정점을 모두 순회한 후 멀어진다.

깊이 우선 탐색은 즉시 시작 정점에서 최대한 멀어진다.

 

따라서 그래프를 탐색하는 동안 시작 정점 가까이 있고 싶은 경우 너비 우선 탐색을, 빠르게 멀리 떨어져야한다면 깊이 우선 탐색을 선택한다.

 

 

1.3.4 빅오로 표현하기

O(V + 2E)이다. 하지만 빅 오에서는 상수를 버리므로 O(V + E)로 나타낸다.

V는 정점을 뜻하고 E는 간선 수를 뜻한다.

 

 

 

출처

제이 웹그로우, 누구나 자료구조와 알고리즘 (길벗, 2021)

 

 

 

 

개인적으로 공부한 내용을 정리하는 블로그로
잘못된 개념을 게시하지않도록 주의하고 있으나 오류가 있을 수 있습니다.

 

 

저작자표시