트리2 크루스칼 알고리즘 스패닝 트리 스패닝 트리란 무향 그래프의 모든 정점을 연결하는 부분 그래프이다. 간선의 개수는 \(V-1\) 개로 트리 구조이다. 그림 1은 7개의 정점을 6개의 간선을 이용해 연결하는 올바른 스패닝 트리이다. 반면에 그림 2는 0-1-2의 정점으로 이루어진 사이클이 있으며 2, 4번 정점은 연결되어 있지 않으므로 스패닝 트리가 아니다. 그림 1 그림 2 최소 스패닝 트리 최소 스패닝 트리란 가중치가 있는 무향 그래프의 스패닝 트리 중에서 가중치의 합이 최소인 스패닝 트리이다. 최소 스패닝 트리를 구하는 알고리즘은 크루스칼 알고리즘과 프림 알고리즘이 대표적이다. 크루스칼 알고리즘 가중치가 큰 간선과 가중치가 작은 간선 중 어떤 간선이 최소 스패닝 트리에 포함될 가능성이 높을까? 당연히 가중치가 작은 간선.. 2022. 8. 31. 오일러 투어 테크닉 오일러 투어 테크닉(euler tour technique) 오일러 투어 테크닉이란 DFS로 트리를 탐색하면서 임의 정점 \(v\)의 진입 시점과 탈출 시점을 기록하여 트리의 서브 트리를 일차원 배열로 관리하는 테크닉이다. 과정 1. 루트부터 DFS를 시작해 각 정점의 진입 순서를 left 배열에 기록하자. (0-base, 1-base 상관없다.) 2. 탈출 순서를 right 배열에 기록하자 3. 트리와 left, right 배열을 한 번에 보면, 정점 v를 루트로 하는 서브 트리에 속한 정점들의 방문, 탈출 순서가 모두 루트 정점에 진입, 탈출 순서 사이에 있다. 즉, 각 정점을 루트로 하는 서브 트리가 하나의 구간으로 나타난다. 구현 진입 순서와 탈출 순서를 어떻게 관리할까? 전역 변수를 이용하여 관리.. 2022. 6. 10. 이전 1 다음