그래프 알고리즘 썸네일형 리스트형 최소신장트리(Minimum Spanning Trees)프림(prim) 알고리즘 최소신장트리(Minimum Spanning Trees)프림(prim) 알고리즘 프림 알고리즘(Prim's algorithm) - 프림 알고리즘은 다익스트라(Dijkstra) 알고리즘과 유사하게 동작한다. - 알고리즘이 동작되는 동안에, 트리에 연결되지 않은 정점들은 큐에 배정되어 있다. - 각 정점들은 key 값을 가지고, 인접한 정점 중 최소 비용으로 이동가능한 정점을 선택한다. 1. 동작 원리 (1) 각 정점들의 key 값과, 다른 정점을 가르키는(pre) 값을 초기화한다. (2) 모든 정점들을 큐에 배정하고, 시작 위치의 key값을 0으로 초기화한다. (3) 큐에 배정된 정점 중, key 값이 가장 작은 정점을 꺼낸다. (4) 꺼내온 정점을 기준으로, 인접한 정점 중에 큐에 아직 배정되어 있고(=트.. 더보기 최소신장트리(Minimum Spanning Trees) 크루스칼(Kruskal) 알고리즘 최소신장트리(Minimum Spanning Trees) 크루스칼(Kruskal) 알고리즘 신장트리란? - 사이클을 형성하지 않고 그래프의 모든 정점이 간선으로 연결되어 있는 것 최소 신장 트리(MST : Minimum Spanning Trees)란? - 최소한의 비용(가중치)로 신장 트리를 형성하는 것 크루스칼(Kruskal) 알고리즘 - 최소 신장 트리를 형성하기 위한 알고리즘 - Disjoint-set을 사용한다. * 대표 원소(representitive)를 통해 각 set을 분별하는 방식. * 이에 대해서는 차 후에 자세하게 다루겠다. 1. 동작원리 (1) 모든 정점들(vertices)을 독립적인 원소(set)로 만든다. (2) 모든 선분들(edges)을 가중치를 기준으로 정렬한다. (3) 가중치가.. 더보기 벨먼-포드 알고리즘(Bellman-Ford algorithm) 벨먼-포드 알고리즘(Bellman-Ford algorithm) - 가중치 그래프에서 시작점에서 목표점까지의 최단 경로를 찾는 알고리즘이다. - 다익스트라 알고리즘과 흡사하지만, 다익스트라보다 조금 더 느리다. + 음수 가중치를 판단할 수 없는 다익스트라에 비해 조금 더 유연하다. 동작 원리 (1) 시작점을 제외한 모든 점의 거리를 무한으로 초기화한다. ( 시작점의 거리는 0 ) (2) 모든 점의 수 만큼 반복적으로 가중치가 있는 모든 선분을 검사한다. (3) 갱신 가능한 거리가 있으면 최단거리를 갱신한다. (4) 음수 싸이클이 있는지 검사하고, 검사 결과를 반환한다. [ Fig. 1 ] process of bellmanford. cite : introduction to algorithm 3/E 함수 설명.. 더보기 A* (A star) 알고리즘 A* (A star) 알고리즘 - 주어진 출발점에서 목표점까지 가는 최단 경로를 찾아내는 그래프 알고리즘 중 하나이다. - 적절한 휴리스틱 추정값 h(x) 을 가지고 이 알고리즘을 사용하면 최적의 해를 얻을 수 있다. - A* 알고리즘은 최적의 경로를 탐색하기 위해, 각각의 지점에서 다음과 같은 함수 f(n)을 이용하여 가중치를 고려한다. f(n) = g(n) + h(n) g(n) : 출발점으로부터 현재 위치까지의 경로 가중치 h(n) : 현재 위치로부터 목표점까지의 추정 경로 가중치 1. 동작 원리 (1) 현재 위치(시작점)에서 이동할 수 있는 지점을 열린 목록(open list)에 추가한다. (2) 현재 위치를 다시 확인할 필요가 없는 닫힌 목록(closed list)에 추가합니다. (3) 열린 목록.. 더보기 너비우선탐색(BFS : Breadth First Search) 너비우선탐색(BFS : Breadth First Search) - 자노드를 탐색하기 전 같은 위치의 노드를 먼저 탐색하는 방식이다. - BFS의 시간 복잡도 및 공간 복잡도는 O(nⁿ)이다. ( 주어진 모든 노드를 저장하기 때문 ) - 무한히 깊은 트리에 효과적이다. [ Fig. 1] BFS 탐색 순서 1. 동작 원리 (1) 시작 노드를 큐(Queue)에 삽입한다. (2) 큐가 비어있다면 수행을 중단한다. (3) 큐에서 노드를 꺼낸다. (4) 꺼내온 노드를 기준으로 인접한 정점 중 탐색하지 않은 노드를 탐색한다. (5) 탐색한 노드를 순차적으로 큐에 삽입한다. (6) (2 - 5) 과정을 반복한다. 2. 함수 구현 #include #define MAX 6 #define VISITED 2 #define A.. 더보기 깊이우선탐색(DFS : Depth First Search) 깊이우선탐색(DFS : Depth First Search) - 해가 존재할 가능성이 있으면 계속해서 같은 방향으로 탐색하는 알고리즘이다. - 스택 구조( 재귀 )를 이용한다. - 진행 중이던 방향이 막혀 있을 경우 이전으로 되돌아가서 위의 과정을 반복한다. - 모든 곳을 방문했을 때 탐색을 종료한다. - 넓은 트리에 효과적이나 목표 노드가 없는 경로에 깊이 빠질 수 있는 단점이 있다. [ Fig. 1 ] DFS 탐색 순서 1. 동작 원리 (1) 현재(초기) 노드를 방문으로 표시한다. (2) 현재 노드와 인접한 노드 중 방문하지 않은 노드가 있는지 탐색한다. (3) (2)의 조건에 맞는 노드를 탐색하면, 해당 노드를 중심으로 (1 - 2) 과정(재귀)을 반복한다. (4) 방문하지 않은 노드가 없을 경우 종.. 더보기 그래프의 행렬 표현법(Representations of graphs) 그래프의 행렬 표현법(Representations of graphs) 1. 방향성이 없는 그래프와 방향성이 있는 그래프 (1) 방향성이 없는 그래프 [ 출저 : Introduction to algorithms 3/E ] 위의 그림을 보면 (a)의 그래프는 5개의 꼭지점과 7개의 선을 가지고 있다. (a)의 그래프를 인접 리스트로 표현해놓은 것이 (b)의 그림이다. 꼭지점 1의 경우 2와 5에 인접해 있고, 꼭지점 2의 경우 모든 다른 꼭지점과 인접해 있다. 이것을 행렬로 표현하면 (c)와 같다. 행은 현재 꼭지점이 되는 것이고, 열은 다른 꼭지점이라고 생각하면 된다. 즉 위의 그림과 무관하게 아래 행렬을 살펴보자. 1 2 3 4 5 1 0 0 1 0 0 2 0 0 1 1 0 3 1 1 0 0 0 4 0 .. 더보기 이전 1 다음
