[Note] 그래프를 알아보자

[saseungmin]

📚 쉽게 배우는 알고리즘 책 Chapter 10: 그래프

🎈 그래프의 표현

• 인접 행렬
  • 행렬 표현법은 이해하기 쉽고 간선의 존재 여부를 즉각 알 수 있다는 장점이 있다.
  • 대신 n x n 행렬이 필요하므로 n²에 비례하는 공간이 필요하고, 행렬의 준비 과정에서 행렬의 모든 원소를 채우는 데만 n²에 비례하는 시간이 든다. 그러므로 O(n²) 미만의 시간이 소요되는 알고리즘이 필요한 경우에 행렬 표현법을 사용하면 행렬의 준비 과정에서만 ɵ(n²)의 시간을 소모해버려 적절하지 않다.
  • 간섭의 밀도가 아주 높은 그래프에서는 인접 행렬 표현이 적합하다.
  • JavaScript 예제
• 인접 리스트
  • 인접 리스트는 공간이 간선의 총수에 비례하는 양만큼 필요하므로 대체로 행렬 표현에 비해 공간의 낭비가 없다. 모든 가능한 정점 쌍에 비해 간선의 수가 적을 떄 유용하다. 하지만, 거의 모든 정점 쌍에 대해 간선이 존재하는 경우에는 오히려 리스트를 만드는 데 필요한 오버헤드만 더 든다. 그래서 간선의 밀도가 높은 경우에는 적합하지 않다.
  • JavaScript 예제

🎈 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)

• BFS
  • BFS는 먼저 루트의 자식을 차례로 방문한다. 다음으로 루트 자식의 자식, 즉 루트에서 두 개의 간선을 거쳐서 도달할 수 있는 정점을 방문한다.
  • BFS의 수행 시간은 ɵ(V + E)이다
  • 경주로 건설: 2020 카카오 인턴쉽
• DFS
  • DFS는 루트의 자식 정점을 하나 방문한 다음 아래로 내겨갈 수 있는 곳까지 내려간다. 더 이상 내려갈 수가 없으면 위로 되돌아오다가 내겨갈 곳이 있으면 즉각 내려간다.
  • DFS의 수행시간은 ɵ(V + E)이다.
• DFS & BFS JavaScript 문제 예제

🎈 최소 신장 트리

• 프림 알고리즘
  • 프림 알고리즘은 집합 S를 공집합에서 시작하여 모든 정점을 포함할 때까지(즉, S=V가 될때까지) 키워나간다. 맨 처음 정점을 제외하고는 정점을 하나 더할 때마다 간선이 하나씩 확정된다.
  • 프림 알고리즘의 수행 시간은 최소힙을 사용했을 때 O(ElogV)이다.
• 크루스칼 알고리즘
  • 크루스칼(Kruskal) 알고리즘은 사이클을 만들지 않는 범위에서 최소 비용 간선을 하나씩 더해가면서 최소 신장 트리를 만든다.
  • 크루스칼 알고리즘의 수행 시간은 O(ElogV)이다.
• 프로그래머스 섬 연결하기 문제를 크루스칼과 프림 알고리즘을 사용해 문제 풀이

🎈 위상 정렬

• 작업 i와 작업 j 사이에 간선 (i, j)가 존재한다면 작업 i는 반드시 작업 j보다 먼저 수행된다. 모든 간선에 대해서 이 성질만 만족하면 어떤 순서라도 좋다. 이러한 성질을 만족하는 정렬을 위상 정렬이라 한다.
• 간선(i, j)가 존재하면 정렬 결과에서 정점 i는 반드시 정점 j보다 앞에 위치해야 한다.
• 만약 그래프에 사이클이 있다면 이 성질은 결코 만족될 수 없으므로 위상 정렬은 할 수 없다.
• 위상 정렬 알고리즘의 수행 시간은 for 루프는 n번 반복된다. 매 반복 때마다 1개의 정점이 선택되고 해당 정점이 연결된 진출 간선이 모두 제거된다. 각 간선은 단 한 번씩만 취급된다. 그러므로 총 수행 시간은 ɵ(V + E)이다.

🎈 최단 경로

• 다익스트라 알고리즘
  • 모든 간선 가중치가 음이 아닌 일반적인 경우로, 다익스트라 알고리즘으로 문제를 푼다.
  • 다익스트라 알고리즘은 프림 알고리즘과 거의 유사하고 수행 시간도 동일하다 힙을 이용하면 O(ElogV) 시간이 소요된다.
  • 힙을 사용하지 않고 배열을 사용할 시 O(EV) 시간이 소요. JavaScript 경우 우선순위큐를 직접 구현해야 한다.
  • 프로그래머스 가장 먼 노드
  • 프로그래머스 배달
  • JavaScript 다익스트라 알고리즘 예제
• 벨만-포드 알고리즘
  • 음의 가중치가 존재하는 경우로. 벨만-포드 알고리즘이 이 유형의 문제를 푼다. (음의 가중치는 허용하지만 가중치 합이 음인 사이클은 절대 허용하지 않는다.)
  • 벨만-포드 알고리즘은 음의 사이클이 존재하면 문제 자체가 성립되지 않는다.
  • 벨만-포드 알고르즘을 사용해야 하는 곳에 다익스트라 알고리즘을 사용하면 제대로 해를 구하지 못한다. 반대로 다익스트라 알고리즘을 사용해 해를 구할 수 있는 경우에는 항상 벨만-포드 알고리즘을 써도 된다. 그러나 벨만 포드 알고리즘은 O(ElogV) 시간이 소요되는 다익스트라 알고리즘에 비해 시간이 많이 걸린다.
  • JavaScript 예제
• 모든 쌍 최단 경로 알고리즘(플로이드-워샬 알고리즘)
  • 플로이드-워샬 알고리즘은 동적 프로그래밍의 원리를 이용하지만 ɵ(n³)에 해결한다.
  • 이 알고리즘의 수행 시간은 ɵ(n)의 for 루프가 세 겹 중첩되었고, 각 경우에 단 두 가지 경우의 대소를 비교하는 것으로 상수 시간이 걸려 ɵ(n³) 시간에 수행된다.
  • 프로그래머스 순위
  • 플로이드-워샬 알고리즘 JavaScript 예제
• 사이클이 없는 그래프의 최단 경로
• 다익스트라 알고리즘, 벨만-포드 알고리즘, 사이클이 없는 그래프의 최단 경로 알고리즘은 하나의 시작 정점에서 다른 모든 정점까지 최단 경로를 구한다.
• 모든 쌍 최단 경로 알고리즘은 모든 정점 쌍 간의 최단 경로를 구한다. 즉, 전자의 알고리즘은 n-1개의 경로를 구하지만, 후자의 알고리즘은 n(n-1)개의 경로를 구한다. 그래서 앞의 유형을 단일 시작점 최단 경로 문제라 하고, 뒤의 유형은 모든 쌍 최단 경로 문제라고 한다.

🎈 강연결 요소

• 유향 그래프 G=(V, E)에서 V의 모든 정점 쌍(u, v)에 대해서 경로 u -> v와 v -> u가 존재하면 그래프 G는 강하게 연결되었다고 말한다. 즉, 어떤 두 정점을 잡더라도 양방향으로 서로에게 이르는 경로가 존재하면 강하게 연결되었다고 한다. 그래프에서 강하게 연결된 부분 그래프들을 각각 강연결 요소(Strongly Connected Component)라 한다.
• 강연결 요소 구하기 알고리즘은 수행 시간은 1번의 DFS는 ɵ(V+E)시간이 든다. 2의 그래프 G^R을 만드는 과정도 모든 간선을 한 번씩 훑으면서 방향만 바꾸어주면 되니까 ɵ(V+E)시간이 든다. 3번의 DFS도 ɵ(V+E)시간이 든다. 그러므로 알고리즘의 총 수행 시간은 ɵ(V+E)이다.

책에 있는 예제를 공부하고 예제를 JavaScript로 풀어보기