dukongmon

[그래프 용어]노드(Node) = 정점 : 그래프에서 동그라미에 해당되는 부분간선(Edge) = 거리(가중치) : 그래프에서 선에 해당되는 부분오른쪽 예시에서는 4개의 노드와 5개의 엣지로 구성됨 1) Union-Find 알고리즘 (합집합 찾기)대표적인 그래프 알고리즘'합집합 찾기' 또는 '서로소 집합(Disjoint-Set) 알고리즘'이라고 불림여러개의 노드가 존재할 때, 2개의 노드를 선택해서 이 두 노드가 현재 서로 같은 그래프에 속하는지 판별하는 알고리즘 위와 같이 아직 연결되지 않은 8개의 노드가 있다고 하자현재는 각 노드가 자기 자신만을 원소로 갖기 때문에 8개의 집합이 생김이를 테이블로 만들면 아래와 같이 만들 수 있음 (= 모든 값이 자기 자신을 가리키도록 테이블 생성)테이블 첫 행은 각 ..