기록
[Algorithm] Kruskal 알고리즘 (JAVA 구현)
- 크루스 칼(Kruskal) 알고리즘이란? 크루스 칼 알고리즘이란, 각 정점을 최소 비용으로 연결시키는 최소 비용 신장 트리를 만드는 대표적인 알고리즘으로 일반적인 그래프에서 각 정점을 연결하는 간선에 비용을 추가해 최소 비용으로 모든 정점을 순환하는 그래프로 만드는 것이다. 크루스칼 알고리즘으로 그래프를 구현할 때 비용은 최소가 되어야 하기 때문에 두 정점과 그 간선에 소모되는 비용을 하나의 클래스로 정의하여 비용을 기준으로 오름차순 정렬을 한 후 가장 적은 비용부터 차례대로 정점을 연결해 나가면 된다. 또한 각 정점에서 사이클이 발생하지 않고, 간선의 수가 정점의 수 -1 개가 연결될 때까지 진행한다. 정점의 수 -1 개의 간선이 연결되면 모든 정점이 연결될 수 있기 때문이다. 이때 사이클의 발생여..
[Algorithm] Union-Find 알고리즘 (JAVA 구현)
-Union Find 알고리즘이란? 서로소 집합 알고리즘과 같은 개념으로 여러 개의 노드가 존재하는 그래프에서 두 노드가 연결되어있는지 판별하는 알고리즘이다. 구현에 필요한 자료구조로는 1) 모든 정점들의 부모 정점을 표현하기 위한 배열이 필요하다. 다음과 같이 6개의 독립적인 노드가 존재한다고 할 때 배열을 이용해서 원소에 해당 노드의 부모 노드를 표시하게 된다. 현재는 모두 독립된 노드이기 때문에 자기 자신을 부모로 삼는다고 할 수 있다. 1 2 3 4 5 6 1 2 3 4 5 6 이와 같은 상태에서 만약 1번 정점과 2번 정점이 연결을 수행하게 되면 두 정점을 합치는 Union작업이 수행되게 되는데, 이 과정을 거치고 나면 아래와 같이 2번 정점의 원소를 부모 정점인 1로 바꿔주게 된다. 이 과정에..
[Algorithm] 깊이 우선 탐색 알고리즘(JAVA 구현)
-깊이 우선 탐색(DFS)이란? 그래프의 순회 방식에는 두 가지가 존재한다. 첫 번째는 깊이 우선 탐색(DFS) 두 번째는 너비 우선 탐색(BFS). 이러한 방식들은 기본적으로 그래프를 구성하고 있는 모든 노드들을 한 번씩 반드시 방문하게 되며 이를 그래프의 순회라고 한다. 그중 깊이 우선 탐색은 아래와 같은 순서를 따른다. 시작 정점(V)을 방문한다. V에 인접한 정점들 중 방문하지 않은 정점을 방문하며 스택(Stack)에 삽입한다. 인접한 정점이 없는 정점까지 2번을 반복한다. 이후 인접한 정점이 없는 경우 다시 스택에서 pop() 후 2~3번을 반복한다. 즉 깊이 우선 탐색의 경우에는 인접한 정점이 없는 정점에 도달할 때까지 인접한 정점을 반복해서 방문하며 Stack에 넣는 작업을 한다. 깊이 우선..
[Algorithm] 너비 우선 탐색 알고리즘(JAVA 구현)
-너비 우선 탐색(BFS)란? 그래프의 순회 방식에는 두 가지가 존재한다. 첫 번째는 깊이 우선 탐색(DFS) 두 번째는 너비 우선 탐색(BFS). 이러한 방식들은 기본적으로 그래프를 구성하고 있는 모든 노드들을 한 번씩 반드시 방문하게 되며 이를 그래프의 순회라고 한다. (또한 너비 우선 탐색은 두 정점 사이의 최단 거리를 구하거나 임의의 경로를 구할 때 사용한다고 하는데, 필자도 현재까지는 단순한 구현과 개념의 이해정도 수준에 그치기 때문에 후에 추가적으로 작성할 예정이다.) 그중 너비 우선 탐색은 아래와 같은 순서를 따른다. 시작 정점(V)을 방문한다. V에 인접한 정점들 중 방문하지 않은 정점을 차례로 방문하며 큐(Queue)에 삽입한다. 인접한 정점을 모두 방문했다면, 큐에 삽입했던 정점을 반환..