친구를 맺어주는 소셜 네트워크를 만들어보자.
철수가 영희의 친구라면, 영희 역시 철수의 친구다. 이처럼 친구 관계는 서로 상호적이다.
이러한 데이터를 조직할 수 있는 간단한 방법은 '2차원 배열'로 리스트를 저장하는 것이다.
String[][] friendShips = {
{"Alice", "Bob"},
{"Bob", "Cynthia"},
{"Cynthia", "Diana"},
{"Diana", "Bob"},
{"Elise", "Fred"},
{"Fred", "Alice"}
}
하지만 이 방식으로는 'Alice'의 친구가 누구인지 빠르게 알 수 없다. 컴퓨터는 목록 내 관계를 일일이 확인해야만 친구 관계를 알 수 있다. 이것은 O(N)이 걸리는 매우 느린 방법이다.
'그래프(graph)'라는 자료 구조를 사용하면 앨리스의 친구를 O(1) 시간 만에 찾을 수 있다!
17. 1 그래프
그래프는 '관계'에 특화된 자료 구조로서 "데이터가 서로 어떻게 연결되는지" 쉽게 이해시켜 준다.
한 사람은 한 '노드'로, 사람 간 친구 관계는 각 '선'으로 표현한다. 앨리스 노드가 밥, 다이애나, 프레드 노드와 선으로 연결되므로 각각 친구 사이다.
사실 "트리도 그래프의 한 종류"다. 두 자료 구조 모두 서로 연결되는 노드로 구성된다.
그렇다면 차이는 무엇인가?
정답은 "모든 트리는 그래프이지만, 그래프가 모두 트리는 아니다".
그래프에는 '사이클'을 형성하는 노드, 즉 서로 순환적으로 참조하는 노드가 있을 수 있지만, 트리로 규정되는 그래프에는 '사이클(cycle)'이 없으며, 모든 노드가 서로 '연결'되어 있어야 한다. 사이클이 있는 그래프는 '트리'가 아니다!
또한 트리는 직간접적으로 모든 노드들이 서로 연결되는 반면, 그래프는 완전히 연결되지 않을 수 있다.
위 네트워크에는 두 쌍의 친구 관계가 있다. 하지만 누구도 다른 쌍의 누군가와 친구가 아니다. 또 '비키'는 아예 친구가 없다. 이와 달리 트리에는 나머지 트리와 연결되지 않은 노드가 없다.
그래프에만 쓰이는 '용어'들이 있다.
흔히 각각의 데이터를 노드라고 부르지만, 그래프에서는 각 노드를 '정점(vertex)'이라 부른다. 각 정점을 잇는 선도 '간선(edge)'이라 부른다. 간선으로 연결된 정점은 서로 '인접한다(adjacent)'고 말한다. 인접한 정점을 '이웃(neighbor)'이라고도 한다.
위 예제처럼 그래프에는 다른 정점과 전혀 연결되지 않은 정점이 있을 수 있다. 모든 정점이 어떻게든 서로 연결된 그래프를 따로 '연결 그래프(connected graph)'라고 부른다.
17. 2 방향 그래프
어떤 소셜 네트워크에서는 관계가 상호적이지 않다. 한 소셜 네트워크에서 앨리스는 밥을 팔로우할 수 있지만, 밥이 반드시 앨리스를 팔로우하진 않는다.
누가 누구를 팔로우하는지 보여주는 새로운 그래프는 다음과 같다.
이와 같은 그래프를 '방향 그래프(directed graph)'라 부른다. 화살표는 관계의 방향을 나타낸다.
17. 3 그래프 탐색
'정점 찾기(탐색)'는 가장 흔한 그래프 연산이다. 그래프 어딘가에 있는 특정한 정점을 찾는 것이다.
더 나아가 그래프에서의 탐색은 보다 특정한 의미를 지닌다. "그래프 내 한 정점에 접근할 수 있을 때 그 정점과 어떻게든 연결된 또 다른 특정 정점을 찾는 것"이다.
현재 앨리스의 정점에 접근할 수 있을 때, '이레나'를 찾는다는 것은 앨리스에서 이레나로 가는 경로를 찾는다는 뜻이다.
이때 가장 짧은 경로는 다음과 같다.
Alice → Derek → Gina → Irena
하지만 조금 더 긴 경로를 택할 수도 있다.
Alice → Elaine → Derek → Gina → Irena
'경로(path)'라는 용어는 한 정점에서 다른 정점으로 가는 간선들의 순열을 뜻한다.
그래프 탐색(한 정점에서 다른 정점으로 가는 것)은 다양한 유스케이스에 효과적으로 쓰인다. 임의의 정점 하나만 접근할 수 있으면 탐색으로 전체 그래프 내 어떤 정점이든 찾을 수 있다.
그래프 탐색의 또 다른 사례는 두 정점이 연결되어 있는지 알아내는 것이다. 만약 앨리스와 이레나가 네트워크 상에서 어떤 식으로든 연결되어 있는지 알고 싶을 때 그래프 탐색을 이용한다.
그래프 탐색에는 '깊이 우선 탐색'과 '너비 우선 탐색'이 있다.
17. 4 깊이 우선 탐색
'깊이 우선 탐색'과 '너비 우선 탐색' 모두 널리 쓰인다. 둘 다 그래프를 탐색하지만 특정 상황에서 각각 고유한 이점을 제공한다.
우선 '깊이 우선 탐색(Depth-First Search, DFS)'은 '이진 트리 순회 알고리즘'과 매우 유사하다.
어떤 그래프 탐색 알고리즘이든 핵심은 지금까지 어떤 정점을 방문했는지 기록하는 것이다. 그렇지 않으면 무한 사이클에 빠지고 만다.
만약 앞서 방문했던 정점을 따로 기록하지 않으면 위 코드는 영원히 순환할 것이다. 사이클이 없는 트리에서는 발생하지 않은 문제지만 그래프에는 사이클이 있을 수 있으므로 이 문제를 해결해야 한다.
방문했던 정점을 기록하는 한 가지 방법은 '해시 테이블'을 사용하는 것이다. 각 정점을 방문할 때마다 그 정점을 키로 해서 해시 테이블에 추가하고, 불리언 값 true 같은 임의의 값을 그 '키'로 할당한다. 해시 테이블에 어떤 정점이 있으면 이미 방문했다는 뜻이다.
해시 테이블을 사용하는 '깊이 우선 탐색' 알고리즘은 다음과 같이 동작한다.
(1) 그래프 내 임의의 정점에서 시작한다.
(2) 현재 정점을 해시 테이블에 추가해 방문했던 정점임을 표시한다.
(3) 현재 정점의 인접 정점을 순회한다.
(4) 방문했던 인접 정점이면 무시한다.
(5) 방문하지 않았던 인접 정점이면 그 정점에 대해서 재귀적으로 깊이 우선 탐색을 수행한다.
1. 그래프 내 임의의 정점에서 시작하고, 현재 정점을 해시테이블에 추가해서 방문한 정점임을 표시한다.
앨리스에서 시작한다. 체크 부호는 방문한(그리고 해시 테이블에 추가한) 정점이라는 표시다.
이어서 루프로 앨리스의 이웃을 순회한다. 이웃은 '밥', '캔디', '데릭', '일레인'이 있다. 어떤 이웃을 먼저 방문하는지 순서는 중요하지 않다. 아무나 먼저 방문하자.
2. 밥에 깊이 우선 탐색을 수행한다.
이미 앨리스에 대해 깊이 우선 탐색을 수행하던 중이었으니, 이는 재귀 호출이다. 모든 재귀가 그러하듯이 컴퓨터는 어떤 함수 호출을 수행하던 중이었는지 기억해야 하므로 앨리스를 먼저 호출 스택에 추가한다.
밥에 깊이 우선 탐색을 시작하며 밥이 현재 정점이 된다. 밥에 방문했다고 표시한다.
3. 이어서 밥의 인접 정점을 순회한다.
앨리스는 이미 방문했으니 무시한다. 이제 이웃은 '프레드'만 남았다. 프레스의 정점에 깊이 우선 탐색 함수를 호출한다. 그리고 먼저 밥을 호출 스택에 추가해 밥을 탐색하던 중이었음을 기록한다.
이제 프레드를 깊이 우선 탐색을 수행한다. 현재 정점은 프레드고, 프레드에 방문했다고 표시한다.
4. 이어서 프레드의 인접 정점을 순회한다. 밥은 이미 방문한 정점이라 무시한다. 나머지는 헬렌뿐이다.
헬렌에 깊이 우선 탐색을 재귀적으로 수행하지 앞서 먼저 프레드를 호출 스택에 추가한다.
5. 이제 헬렌에 깊이 우선 탐색을 시작한다. 헬렌이 현재 정점이므로 방문했다고 표시한다.
프레드는 이미 방문했으므로 캔디만 남았다. 갠디에 깊이 우선 탐색을 재귀적으로 수행한다.
먼저 헬렌을 호출 스택에 추가해야 한다.
6. 캔디에 깊이 우선 탐색을 수행한다. 캔디가 현재 정점이므로 방문했다고 표시한다.
캔디에는 인접 정점이 앨리스와 헬렌 둘이다.
7. 앨리스는 이미 방문했으니 무시한다.
8. 헬렌도 이미 방문했으니 무시한다.
캔디에 다른 이웃이 없으니 캔디에 대한 깊이 우선 탐색은 여기서 끝이다. 이제 호출 스택을 해제하기 시작한다.먼저 호출 스택에서 헬렌을 팝한다. 헬렌의 이웃을 모두 순회했으니 헬렌에 대한 깊이 우선 탐색이 끝났기 때문이다. 이후 프레드, 밥, 앨리스도 팝한다.
9. 이제 데릭이나 일레인은 방문하지 않았다. 계속해서 데릭에 깊이 우선 탐색을 수행한다.
...
이렇게 각 정점을 하나씩 팝하며 호출 스택을 해제한다.
17. 5 너비 우선 탐색
'너비 우선 탐색(Breadth-First Search)', 즉 BFS는 그래프를 탐색하는 또 다른 방법이다.
일단 깊이 우선 탐색과 달리 재귀를 쓰지 않는다. 대신 앞서 배웠던 '큐'로 문제를 해결한다. 다시 말해 FIFO 자료 구조로서 먼저 들어간 데이터를 먼저 처리한다.
너비 우선 순회 알고리즘은 다음과 같다.
(1) 그래프 내 아무 정점에서나 시작한다. 이 정점을 '시작 정점'이라 부른다.
(2) 시작 정점을 해시 테이블에 추가해 방문했다고 표시한다.
(3) 시장 정점을 큐에 추가한다.
(4) 큐가 빌 때까지 실행하는 루프를 시작한다.
(5) 루프 안에서 큐의 첫 번째 정점을 삭제한다. 이 정점을 '현재 정점'이라 부른다.
(6) 현재 정점의 인접 정점을 순회한다.
(7) 이미 방문한 인접 정점이면 무시한다.
(8) 아직 방문하지 않은 인접 정점이면 해시 테이블에 추가해 방문했다고 표시한 후 큐에 추가한다.
(9) 큐가 빌 때까지 루프(4단계부터)를 반복한다.
시작을 위해서 앨리스를 시작 정점으로 삼자. 앨리스에 방문했다고 표시한 후 큐에 추가한다.
1. 큐에서 첫 번째 정점을 삭제해 현재 정점으로 만든다. 현재 큐에 항목은 앨리스뿐이니, 현재 정점은 앨리스다. 이 시점에 큐는 비어있다. 앨리스가 현재 정점이므로 앨리스의 인접 정점을 순회한다.
2. 밥으로 넘어간다. 밥에 방문했다고 표시한 후 큐에 추가한다.
앨리스 주변이 여러 선으로 둘러싸여 있으니 여전히 현재 정점은 앨리스다. 하지만 밥에 방문했다고 표시했고 큐에도 추가했다.
3. 앨리스의 다른 인접 정점으로 넘어간다. 캔디에 방문했다고 표시한 후 큐에 추가한다.
4. 데릭에 방문했다고 표시하고 큐에 추가한다.
5. 일레인에 방문했다고 표시하고 큐에 추가한다.
6. 현재 정점(앨리스)의 이웃을 모두 순회했으므로 큐에서 첫 번째 항목을 삭제한 후 그 정점을 현재 정점으로 만든다. 이때 큐의 맨 앞에 밥이 있으니 밥을 디큐(dequeue)래서 현재 정점으로 만든다.
7. 앨리스는 이미 방문했으니 무시한다.
8. 프레드는 아직 방문하지 않았으니 방문했다고 표시하고 큐에 추가한다.
9. 밥에게도 더 이상 인접 정점이 없다. 따라서 큐에서 첫 번째 항목을 삭제해 현재 정점으로 만든다. 바로 캔디다.
10. 앨리스는 이미 방문했으니 무시한다.
11. 헬렌은 아직 방문하지 않았다. 헬렌에 방문했다고 표시하고 큐에 추가한다.
...
큐에서 모든 항목이 삭제되면 모든 정점을 순회한 것이다.
17. 6 깊이 우선 탐색 vs 너비 우선 탐색
'깊이 우선 탐색'의 경우, 시작하는 앨리스로 다시 돌아가기 전까지 앨리스에게서 즉시 최대한 멀리 떨어진다.
'너비 우선 탐색'의 경우, 앨리스와 바로 연결된 정점부터 먼저 순회하고 이어 바깥으로 나선형으로 퍼져 나가며 점차적으로 멀어진다.
다시 말해 너비 우선 탐색은 시작 정점과 가장 가까운 정점을 모두 순회한 후 멀어지는 반면, 깊이 우선 탐색은 즉시 시작 정점에서 최대한 멀어진다. 탐색이 막히면 그제야 시작 정점으로 돌아오는 특징을 가진다.
둘 중 어떤 게 더 나은지는 상황에 따라 다르다. 탐색하려는 그래프의 특성과 탐색하는 대상에 따라 달라진다.
만약 소셜 네트워크에서 어떤 사람과 직접 관계된 사람만 찾는다고 가정하자. 즉 앨리스와 직접 관계된 진짜 친구만 찾고 싶다. 너비 우선 방식으로 해보면 "2차" 커넥션으로 이동하지 않고 앨리스와 직접 관계된 친구를 바로 찾는다. 하지만 깊이 우선 탐색은 여러 정점을 순회하느라 훨씬 많은 시간을 낭비할 수 있다.
또 다른 예시는 '가계도(family tree)'다.
Ruby의 증손주인 '루스(Ruth)'를 찾고 싶다. 너비 우선 탐색을 사용하면 첫 번째 증손주에 닿기도 전에 모든 자식과 손주를 순회해야 하는 비효율이 발생한다. 반면 깊이 우선 탐색을 사용하면 즉시 그래프 다음으로 내려가 증손주에 도달한다.
그래서 이렇게 물어야 한다.
"그래프를 탐색하는 동안, 시작 정점 가까이 있고 싶은가? 아니면 무조건 멀리 떨어지고 싶은가?"
가까이 있고 싶다면 '너비 우선 탐색'이 좋고, 빨리 멀어져야 한다면 '깊이 우선 탐색'이 좋다.
17. 7 그래프 탐색의 효율성
빅 오 표기법으로 그래프 탐색의 시간 복잡도는 어떻게 표현할까?
깊이 우선 탐색과 너비 우선 탐색 모두 최악의 시나리오에선 모든 정점을 순회한다. 어떤 경우든 그래프 내 정점을 전부 확인하니 언뜻 정점이 N개일 때 O(N)처럼 보인다.
하지만 두 탐색 알고리즘은 순회하는 각 정점의 인접 정점까지 모두 순회한다. 이미 방문했던 정점이면 무시할 수 있으나 방문했는지 알려면 어차피 정점을 확인하는 단계가 필요하다. 즉 방문하는 각 정점의 인접 이웃까지 확인하는 단계를 포함해서 정점마다 인접 정점의 개수가 다르니 빅 오 표기법으로 딱 고정해서 말하기 어렵다.
그래프 내 정점 개수만으로는 단계를 셀 수 없다. 각 정점의 인접 정점이 몇 개인지도 함께 고려해야 한다.
컴퓨터 과학자는 그래프 탐색의 효율성을 O(V + E)로 묘사한다. V는 '정점(vertex)', E는 '간선(edge)'을 뜻한다. 다시 말해 그래프 내 정점 수에 그래프 간선 수를 더한 값이 곧 단계 수라는 뜻이다.
O(V + E)는 너비 우선 탐색이든 깊이 우선 탐색이든 똑같다.
17. 8 마무리
그래프는 관계를 포함하는 데이터를 처리할 때 매우 강력한 도구이다.
해당 글은 '누구나 자료구조와 알고리즘' 책의 내용을 기반으로 작성되었습니다.
오로지 학습용으로 작성하였음을 밝힙니다.
더 자세한 내용을 확인하고 싶다면 해당 저서를 참고하시길 바랍니다.
'자료구조 & 알고리즘' 카테고리의 다른 글
| Ch.16 트라이(trie)해 보는 것도 나쁘지 않다 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.06.13 |
|---|---|
| Ch.15 힙으로 우선순위 유지하기 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.06.11 |
| Ch.14 이진 탐색 트리로 속도 향상 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.06.10 |
| Ch.13 노드 기반 자료 구조 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.06.09 |
| Ch.12 속도를 높이는 재귀 알고리즘 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.06.09 |
