본문 바로가기

자료구조

Union-Find 연산 Region Merging을 구현할 때 필요한 "Disjoint Set"을 위한 자료구조이다. 본 내용은 "C로 쓴 자료구조론, Horowitz, Sahni, Anderson-Freed 저, 이석호 역" 에서 발췌하였다. 부족한 부분은 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, "Introduction To Algorithms", The MIT Press, 440-461, 1999.을 참조해야 한다. 트리를 사용하여 집합을 표현하는 방법에 대해 살펴보자. 여기서 집합의 모든 원소는 0, 1 , 2, ..., n-1 등의 수라고 가정하자. 이 수들은 실제 원소의 이름이 저장되어 있는 심볼 테이블의 인덱스를 의미할 수도 있다. 그리고 모든 집합들은.. 더보기
크루스칼 알고리즘 안녕하세요~ (블로그에 포스팅할때는 도대체 누굴 대상으로 글을 쓰는지 늘 스스로 의문입니다?) 최소신장트리에 대해 써볼까 합니다. 처음에 최소신장트리라는 용어를 접했을때 해석할 수 없는 '신장'의 의미 때문에 용어와 의미를 좀처럼 연결시키지 못했던 기억이납니다. 신장(spanning)이라는 용어는 "걸치다" 라는 의미로 번역되는데, 쉽게 말해 그래프 상에서 트리가 모든노드에 걸쳐 연결되어 있다는 의미로 사용됩니다. 여기서 모든 노드에 걸쳐있다는 의미는 path를 만들어 순회한다는 개념이 아닌 모든 노드가 연결되어있다는 의미 입니다. 좀더 형식적으로 정의해보면 신장트리(spanning tree)는 그래프 G=(V,E) 에서 |V| - 1 개의 edge를 제외한 모든 edge를 제거하여 트리가 되도록 만든 .. 더보기

티스토리툴바