graph (7) 썸네일형 리스트형 [Algorithm] Prim's Algorithm (프림 알고리즘) 1. Prim's Algorithm 프림 알고리즘은 크루스칼과 달리 정점을 기준으로 MST를 구성하는 방법이다. MST에 포함된 정점 집합과 아직 포함되지 않은 정점 집합, 두가지를 가지고 수행되는 알고리즘이다. 매 순서마다 두 집합을 연결하고 있는 edge들을 모두 확인하여 가장 작은 가중치를 가지고 있는 edge를 선택하여 해당 edge와 연결되어 있는 정점을 MST에 포함시키는 방식으로 확장한다. 2. 프림 알고리즘 구현 1) MST에 포함된 정점을 저장할 집합을 선언하고 MST에 포함되어 있는 정점을 추가하여 초기화한다. 2) 각 정점의 거리를 표현하는 공간을 선언하고 MST에 포함된 정점은 0으로 나머지는 무한대로 초기화한다. 3) 아직 MST에 포함되지 않은 정점 중 가장 최단 거리를 가지고 .. [Algorithm] Kruskal's Algorithm (크루스칼 알고리즘) 1. Kruskal's Algorithm 크루스칼 알고리즘은 edge를 그리디하게 선택하여 MST를 구성하는 알고리즘이다. edge를 가중치 기준으로 오름차순으로 정렬한 후 가장 작은 edge부터 순서대로 subtree에 추가하여 MST를 구성한다. 이때 해당 edge가 cycle을 이루는지 확인을 해야하는데, 이때 union-find 알고리즘은 사용하는데, 각 정점에 index를 주어서 정점들이 연결될 때마다 해당 그룹의 정점들이 모두 같은 index를 가지도록 하여 이를 비교하여 같은 index를 가지는 경우 cycle로 인식한다. 2. 크루스칼 알고리즘 구현 1) 그래프의 간선을 오름차순으로 정렬한다. 2) 가장 작은 간선을 선택하여 cycle을 그리는지 확인한다. 3) cycle을 그리는 경우는 .. [Algorithm] Floyd-Warshall's Algorithm (플로이드-와샬 알고리즘) 1. Floyd-Warshall's Algorithm 플로이드 와샬 알고리즘은 모든 정점간의 최단 거리를 구하는 All pairs shortest path solving 알고리즘이다. 플로이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 최단 거리를 구한다. 두 정점의 최단 거리를 구할 때 다른 모든 정점을 후보로 각 정점들을 거쳐갈 때의 거리를 비교하여 최소가 되는 경로를 찾는다. 소스 코드를 보면 가장 간단한 알고리즘이다. 2. 플로이드 와샬 알고리즘 구현 플로이드 와샬 알고리즘은 모든 정점 쌍에 대해서 다른 정점들을 중간 경로로 거치는 경로의 거리를 비교하여 최단 거리를 구한다. 1) 먼저 현재 그래프의 간선들을 기준으로 각 정점간의 거리를 저장할 행렬을 초기화한다. 2) 중간 경로가 될 정점을 선택한.. [Algorithm] Dijkstra's Algorithm (다익스트라 알고리즘) 1. Dijkstra's Algorithm 다익스트라 알고리즘은 한 정점으로부터 다른 정점으로의 최단 경로를 찾는 알고리즘이다. 매반복마다 현 시점에서 가장 가까운 정점을 찾아 해당 정점에 인접한 간선들을 통해 경로를 찾아 확장해 나가는 방식이다. 그래프의 방향 유무는 상관없으나 간선이 음수 가중치를 가지는 경우에는 사용할 수 없다. 2. 다익스트라 알고리즘 구현 1) 초기에 출발점으로부터 해당 정점으로의 거리를 저장할 공간과 방문여부를 저장할 공간을 선언한다. 2) 해당 배열에서 출발점은 0, 나머지 정점은 무한대로 초기화한다. 3) 최단 거리를 저장하는 배열에서 미방문 정점 중 가장 거리가 가까운 정점을 선택한다. 4) 해당 정점을 방문한 정점으로 저장한다. 5) 선택된 정점에 간선으로 연결된 인접한.. [Algorithm] DFS 1. DFS (Depth First Search, 깊이 우선 탐색) 그래프 탐색 방법 중의 하나로 시작 노드로 부터 탐색을 진행할 때 해당 분기 (branch)에서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 분기를 완벽하게 탐색한다는 것은 해당 노드에 대해서 깊이를 우선적으로 탐색한다는 의미이다. 그래프의 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 우선 탐색한다. 더이상 연결되어 있지 않을 때까지 탐색하고 다시 되돌아가서 탐색하지 않은 방향의 정점, 분기로 탐색을 진행한다. 모든 정점을 방문할 때까지 탐색을 반복한다. DFS는 자기 자신을 반복해서 호출하는 순환 알고리즘의 형태를 가지고 있다. 트리 탐색에서의 depth-first traversal (preorder tr.. [DS] Graph MST & Shortest path - 이전 글: [DS] Graph 개념과 탐색방법 3. MST (Minimum Spanning Tree) 최소 신장 트리 (MST)는 그래프의 최소 연결 트리를 의미한다. 최소 연결 트리란 edge의 weight가 최소인 spanning tree를 말한다. spanning tree는 그래프의 모든 정점을 cycle 없이 연결한 형태를 말한다. 최소 신장 트리는 N개의 정점과 N-1개의 간선으로 연결되어 있으며 가중치의 합이 신장 트리 중에 최소인 값이 되어야 하기 때문에 단순히 가장 적은 간선을 사용한다고 해서 최소 비용을 얻을 수 없다. MST를 찾는 대표적인 방법으로는 Kruskal 알고리즘과 Prim 알고리즘이 있다. 1) Kruskal algorithm greedy 한 방법으로 간선을 선택하여서 .. [DS] Graph 개념과 탐색방법 1. Graph 그래프는 비선형 자료구조로 정점(vertex, 또는 노드 node)과 정점들을 있는 간선(edge)으로 이루어져 있다. 간선은 E(u,v)로 표현할 수 있는데, 이는 vertex u 와 vertex v를 연결하는 간선이라는 뜻이다. undirected graph 에서는 (u,v)와 (v,u)가 같은 의미를 가지지만 directed graph 에서는 (u,v)와 (v,u) 이 서로 방향이 다르기 때문에 다른 간선을 의미한다. 간선은 weight, value, cost 등의 가중치를 주어서 실제 문제에 적용하기도 한다. 1) 용어 Undirected Graph: 정점과 간선의 연결관계에서 간선의 방향성이 존재하지 않는 그래프 Directed Graph: 정점과 간선의 연결관계에서 간선의 방향.. 이전 1 다음
