본문 바로가기

알고리즘 문제/Graph

Prim's algorithm using priority_queue Prim 알고리즘 개요 가중치가 있는 무방향 그래프에서 MST(최소 스패닝 트리)를 구할 때 Prim's 알고리즘을 이용할 수 있다. 본 포스팅에서는 인접 리스트로 표현된 그래프에서 PQ 자료구조를 이용해 MST를 구하는 방법을 알아 본다. 시간 복잡도는 O(E log(V)) 가 된다. ※ 참고: 인접 행렬로 구한 Prim 알고리즘 : O(V^2) Prim 알고리즘에 PQ를 이용하기 위해서는 아래 두가지 연산이 필요하다. - ExtractMin: MST에 아직 포함되지 않은 모든 정점에서 최소 키 값을 가진 정점을 가져온다. - DecreaseKey: 정점을 추출한 후 인접한 정점의 키를 업데이트 해야 하며, 새 키가 더 작으면 업데이트 한다. 알고리즘 1) 모든 정점을 무한 값을 키 값으로 가지게 초기.. 더보기
A* 알고리즘(A Star Algorithm) 1. 개념 2. 시각화 3. 코드 1. 개념 최단경로를 찾는 그래프 탐색 알고리즘 중 하나입니다. 다익스트라 알고리즘과 유사하나 차이점은 각 꼭지점 x에 대해 그 꼭지점을 통과하는 최상의 경로를 추정하는 순위값인 "휴리스틱 추정값" h(x)를 매기는 방법을 이용한다는 점에서 차이가 있습니다. (h(x) 값을 정확하게 구할 수 없어도 괜찮습니다) 시작노드와 목적지 노드를 분명하게 정해 놓고, 이 두 노드간의 최단 경로를 파악합니다. 휴리스틱 추정값을 어떤 방식으로 제공하느냐에 따라 최단경로 파악 성능이 결정됩니다. A* 알고리즘은 출발 꼭지점으로 부터 목표 꼭지점까지의 최적 경로를 탐색하기 위한 것입니다. 이를 위해서는 각각의 꼭지점에 대한 평가 함수 f(n)를 정의해야 합니다. $ f(x) = g(x) .. 더보기
최소비용 신장트리(Minimum Cost Spanning Tree) 학습 목표 - 신장트리(Spanning Tree) 개념과 특징을 이해할 수 있다 - 최소비용 신장트리(Minimum Cost Spanning Tree) 개념과 특징을 이해할 수 있다 - 최소비용 신장트리 사용 사례 - 구현 방법 신장 트리 개념과 특징 무향방 연결 그래프 $G=(V,E)$ 가 주어질때 모든 노드를 포함하고 연결되어 있으면서, 간선 비용의 합이 최소인 트리 - 하나의 그래프에서 많은 신장 트리가 존재할 수 있다 - 모든 정점이 연결되어 있어야 하고, 사이클이 존재해선 안된다. - n개의 정점을 n-1개 간선으로 연결한다. 최소비용 신장트리 개념과 특징 신장 트리 중에서 가중치 합이 최소인 트리 최소비용 신장트리 사용 사례 1. 군집 분석(Cluster Analysis) 2. 필기 인식(Ha.. 더보기
이분 그래프 & 최대 이분 매칭 (Bipartite Graph & Maximum Bipartite Matching) 1. 이분 그래프(Bipartite Graph)란 "In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets Uand V such that every edge connects a vertex in U to one in V" 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두가지 색으로만 칠할 수 있는 그래프 (그림 상으로 파란색, 초록색으로 인접 노드가 분할이 가능하다) 존재하는 모든 간선의 양 끝 정점이 서로 다른 그룹에 속하는 형태의 그래프를 의미 위의 세가지 모두 이분 그래프를 .. 더보기