Kruskal
-
Graph자료구조 2019. 9. 3. 17:12
Vertex와 Edge로 이루어진 자료구조 G=(V,E) Undirected graph - Vertex를 잇는 Edge에 방향이 없는 그래프. 최대 edge 수 n(n-1)/2 (n은 vertex개수) Directed graph - Vertex를 잇는 Edge에 방향이 있는 그래프. 최대 edge 수 n(n-1) Connected component - 현재 연결성을 유지하면서 더 이상 vertex나 edge를 추가할 수 없는 최대한의 subgraph. connected graph에는 오직 하나의 connected component만이 존재 Cycle - 그래프에서 edge를 통한 순환. cycle은 DFS를 활용해 O(V+E)만에 찾을 수 있음 # 사이클 찾기 그래프 문제를 풀다 보면 '사이클을 찾아라'..
-
Disjoint Sets자료구조 2019. 9. 2. 18:55
n개의 원소를 하나의 자료구조로 합쳐 조작하고 탐색하기 용이하게 만드는 자료구조 n개의 원소가 n개의 set으로 초기화됨 (MakeSet()) Tree를 사용하는 것이 효율적. Tree의 구현은 각 node의 parents를 저장하는 배열로 (parents[i] = j) Union() -> 두 set을 하나의 set으로 합치는 작업 (O(n)) void simpleUnion(int i, int j) {parent[i] = j;} 효율적인 union을 위해 set의 height정보도 같이 저장하고 union시 높이가 낮은 set을 높이가 큰 set에 붙여서 합침 두 set의 height가 같으면 union된 set의 height 증가 Find() -> 어떤 set안에 특정 element가 들어있나 찾음(포..