학습목표 1. 무방향 그래프에서 싸이클 탐색을 학습 1. 싸이클(Cycle)이란 무엇인가? 그래프의 특정 노드에서 출발하여 방향(Edge)를 따라 다시 출발한 노드로 올 수 있는 상황을 싸이클이 있다고 합니다. 아래의 그림은 싸이클이 있는 그래프와 없는 그래프를 표현한 것입니다. 왼쪽이 싸이클이 존재하는 그래프이고 오른쪽이 싸이클이 존재하지 않는 그래프입니다. 2. 무방향 그래프의 싸이클을 탐색하기 위한 접근 방법 무방향 그래프에서 싸이클을 탐색하기 위해서 DFS(Depth First Search) 순회 방법을 이용해서 할 수 있습니다. DFS는 특정 노드에서 시작하여 해당 노드의 인접 노드로 이동하면서 더이상 인접 노드가 없다면 시작 했던 노드로 되돌아가는 재귀적인 순회방법입니다. 싸이클을 탐색하기 위..

학습목표 1. 방향 그래프에서 싸이클이 있는지 탐색하는것을 학습 1. 싸이클(Cycle)이란 무엇인가? 그래프의 특정 노드에서 출발하여 방향(Edge)를 따라 다시 출발한 노드로 올 수 있는 상황을 싸이클이 있다고 합니다. 아래의 그림은 싸이클이 있는 그래프와 없는 그래프를 표현한 것입니다. 왼쪽이 싸이클이 존재하는 그래프이고 오른쪽이 싸이클이 존재하지 않는 그래프입니다. 2. 싸이클을 탐색하기 위한 접근 방법 및 수행과정 한 그래프에는 0개 이상의 연결된(connected) 트리들이 존재할 것입니다. 이러한 트리들에 대해서 DFS(Depth First Search, 깊이우선탐색) 순회 방법을 사용하여 그래프의 싸이클을 탐색할 수 있습니다. DFS의 수행과정은 아래 글과 같습니다. https://yong..

학습목표 1. Kruskal 알고리즘의 개념에 대해서 학습 2. Kruskal 알고리즘의 수행과정에 대해서 학습 3. 왜 Kruskal 알고리즘을 수행하면 최소비용 신장트리가 탐색되는지에 대해서 학습 1. 크루스칼(Kruskal) 알고리즘이란 무엇인가? 크루스칼 알고리즘이란 무방향 가중치 그래프가 존재할때 해당 그래프에서 최소비용 신장트리를 탐색하는 알고리즘입니다. 이때 최소비용 신장트리란 그래프 내의 모든 정점을 포함하고 사이클(cycle)이 없는 연결 선을 그렸을 때, 가중치의 합이 최소가 되는 트리를 의미합니다. 이러한 최소비용 신장 트리를 탐색하는 알고리즘이 크루스칼 알고리즘입니다. 2. 크루스칼(Kruskal) 알고리즘의 수행과정 크루스칼 알고리즘의 수행과정은 다음과 같습니다. 에지들을 가중치의..

학습목표 1. 최소비용 신장 트리(Minimum Spanning Tree, MST)가 무엇인지 학습 2. Generic MST 알고리즘에 대해서 학습 3. 안전한 에지가 무엇인지 학습 1. 최소비용 신장 트리(Minimum Spanning Tree, MST)가 무엇인가? 최소비용 신장 트리는 무방향 가중치 그래프에서 n개의 노드들을 최소의 비용만으로 서로 연결한 트리입니다. 예를 들어 아래의 그림은 무방향 가중치 그래프입니다. 위의 그림에서 가중치의 합이 최소가 되고 모든 노드들이 연결되는 해를 찾아야 합니다. 아래의 그림은 이러한 해 중에 하나입니다. 위의 그림은 최소 비용 신장 트리가 되는 해중에 하나인데 해는 유일하지는 않습니다. 예를 들어 (b,c) 에지 대신 (a,h) 에지를 연결 할 수도 있습..

학습목표 1. DAG(Directed Acyclic Graph)에 대해서 학습 2. 위상 정렬에 대해서 학습 3. 위상 정렬 알고리즘의 수행과정을 학습 4. 위상 정렬 알고리즘 구현 1. DAG(Directed Acyclic Graph)란 무엇인가? DAG는 방향 사이클(directed cycle)이 없는 방향 그래프를 의미합니다. 방향 사이클이란 어느 특정 노드에서 시작하여 순회하고 다시 시작한 노드로 돌아올 수 있다면 그 그래프는 방향 사이클이 존재하는 그래프입니다. 아래의 그림은 방향 사이클이 존재하는 그래프입니다. 반대로 DAG는 방향 사이클이 없기 없는 방향 그래프이기 때문에 어느 특정 노드에서 시작하여도 다시 시작한 노드로 돌아 올 수 없습니다. 아래의 그림은 방향 사이클이 없는 방향 그래프입..

학습목표 1. DFS은 무엇인지 학습 2. DFS의 수행과정을 학습 3. DFS의 시간복잡도에 대해서 학습 1. DFS(Depth-First Search, 깊이우선탐색)이란 무엇인가? DFS는 그래프의 순회 방법 중 하나로써 특정 노드에서 시작하여 인접 노드 중 미방문한 노드를 탐색하여 계속해서 이동하는 순회방법을 의미합니다. 이진 트리로 따지면 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder)와 비슷합니다. 2. DFS(Depth-First Search, 깊이우선탐색)의 수행과정 3. Java 언어 기반 DFS 순회 구현 // 인접리스트 기반 무방향 그래프의 BFS순회 public class UndirectedGraph implements Graph{ privat..