Algorithm/H. Trees & Graphs (33) 썸네일형 리스트형 130. Strongly Connected Component 유향 그래프에 존재하는 어떤 컴포넌트는 다음과 같은 조건을 만족할 경우 강결합 컴포넌트(Strongly Connected Component, SCC)라고 부른다. 컴포넌트에 속하는 임의의 두 정점 $u$와 $v$에 대해 $u$에서 $v$로 가는 경로와 $v$에서 $u$로 가는 경로가 모두 존재한다. 컴포넌트에 속하는 임의의 정점 $u$와 컴포넌트에 속하지 않는 임의의 정점 $v$에 대해 $u$에서 $v$로 가는 경로가 존재하지 않거나, $v$에서 $u$로 가는 경로가 존재하지 않는다. 그래프를 강결합 컴포넌트끼리 분리하면 같은 컴포넌트에 속한 정점들 사이에는 모두 경로가 존재하고, 다른 컴포넌트에 속한 정점들 사이에는 그렇지 않다. 따라서 같은 강결합 컴포넌트에 속한 정점들끼리 묶어서 새로운 그래프를 만.. 128. Borůvka's Algorithm 보르부카 알고리즘(Borůka's Algorithm) 또는 솔린 알고리즘(Sollin's Algorithm)은 무향 그래프의 최소 스패닝 트리를 구하는 세 번째 알고리즘이며 다음과 같이 작동한다. 1. 각각의 컴포넌트에 연결된 간선들 중 가중치가 가장 작은 간선을 하나씩 선택한다. 2. 간선을 차례로 최소 스패닝 트리에 추가하는데, 간선이 연결하는 두 정점이 이미 같은 컴포넌트에 존재한다면 추가하지 않는다. 3. 컴포넌트가 하나로 줄어들 때까지 1번과 2번 과정을 반복한다. 이번에도 설명이 짧게 끝났다. 다시 예시를 가지고 살펴보자. 처음에는 정점들이 모두 다른 컴포넌트에 존재하므로, 각 정점과 연결된 간선들 중 가중치가 가장 작은 것 하나를 모두 고른다. $\text{A}: \text{D}(2)\\ \.. 127. Prim's Algorithm 프림 알고리즘(Prim's Algorithm)은 무향 그래프의 최소 스패닝 트리를 구하는 두 번째 알고리즘으로, 다음과 같은 방법으로 작동한다. 1. 그래프에서 정점 하나를 임의로 골라서 $v$라고 한다. 2. 연결하는 한쪽 정점이 $v$와 연결된 정점들의 집합에 포함되고 다른 정점은 집합에 포함되지 않는 간선들 중 가중치가 가장 작은 간선 하나를 선택하고 최소 스패닝 트리에 추가한다. 3. 모든 정점이 $v$와 연결될 때까지 2번 과정을 반복한다. 이것도 설명이 짧아서 예시를 같이 살펴보면 편할 것이다. 앞에서 나온 그래프에서 정점 $\text{H}$가 $v$로 선택되었다면 다음과 같이 스패닝 트리가 만들어지게 된다. 먼저 정점 $\text{H}$와 연결된 간선 중 가중치가 가장 작은 간선이 최소 스패.. 126. Kruskal's Algorithm 크루스칼 알고리즘(Kruskal's Algorithm)은 무향 그래프의 최소 스패닝 트리를 구하는 알고리즘 중 하나로, 다음과 같은 방법으로 작동한다. 1. 확인하지 않은 간선들 중 가중치가 가장 작은 간선 하나를 고른다. 2. 현재까지의 최소 스패닝 트리에서 선택한 간선이 연결하는 두 정점이 연결되어 있지 않다면, 이 간선을 최소 스패닝 트리에 추가한다. 3. 모든 간선을 확인했다면 종료한다. 그렇지 않다면 1번으로 돌아간다. 설명이 매우 간단하게 끝난다. 예시를 통해서 자세히 살펴보자. 앞에서 나온 그래프이다. 여기서 가중치가 작은 간선들부터 하나씩 확인하면서 최소 스패닝 트리를 만든다. 먼저 가중치가 $2$인 간선들이 최소 스패닝 트리에 추가된다. 다음으로 가중치가 $3$인 간선을 확인하는데, 정점.. 125. Minimum Spanning Tree 무향 연결 그래프의 스패닝 트리(신장 트리, Spanning Tree)는 그래프의 모든 정점을 포함하는 트리이다. 쉽게 말해서 그래프에서 (그래프가 분리되지 않도록) 간선들을 제거해서 트리 구조가 남았을 때 이를 스패닝 트리라고 한다. 하나의 그래프에 여러 개의 스패닝 트리가 존재할 수 있다. 간선에 가중치가 있는 그래프는 스패닝 트리에 포함되는 간선의 가중치의 합이 다양하게 나올 수 있는데, 이중 가중치의 합이 가장 작은 스패닝 트리를 최소 스패닝 트리(최소 신장 트리, Minimum Spanning Tree, MST)라고 한다. 이 최소 스패닝 트리가 꽤 다양한 곳에서 사용되므로 알아 두면 좋다. 무향 연결 그래프에서 최소 스패닝 트리를 구하는 방법은 여러 가지가 있는데, 이 블로그에서는 세 가지를 .. 124. Disjoint Set & Union-Find 이번에 다루는 내용은 트리 구조를 응용한 것이다. 집합론에서 분리 집합(Disjoint Set)은 공통 원소가 없는 두 집합을 의미한다. 컴퓨터과학에서 이 개념은 한 개 이상의 집합으로 확장되며, 한 개의 집합 또는 어떤 두 집합도 공통 원소를 갖지 않는 두 개 이상의 집합을 분리 집합이라고 생각하면 된다. $0$개의 집합 같은 경우는 생각하지 않는다. 분리 집합은 아래의 두 가지 연산에 의해서 여러 활용도를 갖게 된다. 두 집합을 하나로 합친다. (Union) 원소가 현재 어떤 집합에 속해 있는지 확인한다. (Find) 이 두 연산의 이름을 따서 유니온-파인드(Union-Find)라는 이름이 생겨났다. 이 개념을 PS의 관점에서 보면, 일단 각각의 집합은 서로 구별이 가능한 식별자를 갖고 있어야 한다... 123. Topological Sorting 위상 정렬(Topological Sorting)은 DAG의 정점을 재배열하는 알고리즘으로, 정점을 재배열했을 때 간선의 방향은 모두 동일해야 한다. 모든 DAG는 위상 정렬이 가능하며, DAG가 아닌 모든 그래프는 위상 정렬이 불가능하다. 위상 정렬을 하는 방법은 다음과 같다. 1. 아직 선택하지 않은 정점들 중 진입 차수가 $0$인 정점 하나를 선택하고 정렬된 정점 목록의 맨 뒤에 추가한다. 2. 선택한 정점 및 그 정점과 연결된 간선들을 그래프에서 제거한다. 3. 모든 정점이 선택될 때까지 과정 1, 2를 반복한다. 아래의 그래프에서 위상 정렬을 실행하면 다음과 같다. 진입 차수가 $0$인 정점은 $\text{D}$ 하나이므로 정점 $\text{D}$ 및 정점 $\text{D}$와 연결된 간선들을 그.. 122. Directed Acyclic Graph DAG(Directed Acyclic Graph)는 사이클이 존재하지 않는 유향 그래프를 의미한다. 정의는 이렇게 간단하지만 응용할 수 있는 분야는 상당히 넓은 편이며, 최근에는 블록체인에서도 많이 다루면서 점점 주목받고 있는 개념이기도 하다. 사회과학에서도 등장한다고 한다. 그래프 이론의 관점에서 DAG의 큰 특징은 다음과 같이 나타낼 수 있다. 진입 차수가 $0$인 정점이 하나 이상 존재한다. 진출 차수가 $0$인 정점이 하나 이상 존재한다. 어떤 정점 및 그 정점과 연결된 간선들을 그래프에서 제거할 경우 남는 정점과 간선들로 이루어진 그래프도 DAG이다. 모든 정점을 순서대로 나열했을 때 간선의 방향이 전부 동일하게(왼쪽 → 오른쪽 또는 오른쪽 → 왼쪽) 할 수 있다. 네 번째 특징에 나온 정점 나.. 이전 1 2 3 4 5 다음
