분리형 데이터 구조를 사용하면 Graph의 연결 구성 요소를 쉽게 얻을 수 있습니다. 그리고, 그것은 단지 Incremental Connected Components을 지원합니다.연결된 구성 요소를 동적으로 찾는 방법
내가 연결된 구성 요소 (가장자리를 추가 및 제거 포함) 완전히 동적으로 을 유지 할 수있는 알고리즘 또는 새로운 구조를 찾고 있어요 있도록하지만, 내 경우, 가장자리를 제거하는 것은 매우 일반적인
감사
Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity (Holm, de Lichtenberg and Thorup 2001)은 O (log (n)^2) 상각 시간을 사용하는 업데이트 (삽입 및 삭제)와 임의의 순서의 에지 삽입, 삭제 및 연결 쿼리를 허용하는 알고리즘을 제공하며 O (log (n)/log log (n))) 시간이며, n은 그래프의 정점 수입니다. 이 시간 범위는 그래프가 가장자리없이 시작된다고 가정합니다.
38 페이지 중 첫 번째 2 개를 건너 뛰었지만 두렵지는 않습니다. 동적 그래프에 새 알고리즘이 많이 있습니다 (즉, 그래프는 효율적으로 수정할 수 있습니다. 시간)이 가장 단순합니다.
[Wikipedia 기사] (http://en.wikipedia.org/wiki/Connected_component_ (graph_theory))에는 참조가 있습니다. –
@ n.m. 어느 것? "로그 공간에서의 비 방향 연결성"? – Chang
"온라인 엣지 삭제 문제" –