연결성을 결정하는 함수

Question

n 고유 점 P1, P2,...,Pn이 있다고 가정합니다.

연결성 매트릭스 M=(c_ij)을 크기 n의 정사각 행렬로 정의하십시오. 은 i=j 인 경우 또는 Pi과 Pj 사이의 선분이있는 경우 true을 제공합니다.

두 점 사이에 하나 이상의 경로 (선분 집합)가있는 경우 점 집합이 연결됩니다. 우리는 연결된 점 집합을 적절한 그래프라고 부릅니다. 점 자체가 적절한 그래프가 될 수 있습니다.

첫 번째 그래프의 어느 지점에서 두 번째 그래프의 어떤 지점으로도 연결이없는 경우 두 개의 적절한 그래프가 연결이 끊어집니다.

연결 상태는 연결이 끊긴 적절한 그래프의 수로 정의됩니다. 예를 들어

,

 P1 P2 P3 P4 P5 
P1 true false true false false 
P2 false true false false false 
P3 true false true false true 
P4 false false false true true 
P5 false false true true true 

두 끊긴 적절한 그래프 P2와 {P1,P3,P4,P5} 즉있다.

제 문제는 연결 매트릭스를 받아들이고 연결되지 않은 적절한 그래프 목록을 반환하는 함수를 작성하는 방법입니다. 예를 들어 위의 예는 list(list(1,3,4,5),list(2))을 반환해야합니다.

Answer 1

그래프의 연결된 구성 요소를 찾고 있습니다.

O (n^2)보다 빠르지 않기 때문에 불행히도 이와 같은 인접성 매트릭스는 상당히 차선입니다. 다음에서는 사용할 수있는 두 가지 솔루션에 대해 설명합니다. 첫 번째 방법은 이웃에 직접 액세스 할 때 더 좋으며, 두 번째 방법은 가장자리에 직접 액세스하는 경우 더 좋습니다. 귀하의 시나리오에는 해당 사항이 없습니다. 두 솔루션에 대한 시간 복잡도는 인접성 매트릭스에서 동일합니다. 따라서 실제로 측정해야 할 것이 있습니다. 실제로 더 빠릅니다.

이웃에 직접 액세스 할 수있는 데이터 구조가있는 경우 BFS 또는 DFS를 사용하여 연결된 구성 요소를 가져올 수 있습니다. 이 방법은 this answer에 설명되어 있습니다. 이 답변에 명시된 시간 복잡성은 시나리오에 적용되지 않습니다.

가장자리에 액세스 할 수있는 경우 union-find data structure을 사용할 수 있습니다. 다음을 수행 할 수 있습니다.

Initialize union-find uf with n entries 
for every edge (i, j) 
    uf.union(i, j) 
next 
initialize map int -> list of vertices 
for every vertex v 
    p <- uf.representative(v) 
    map[p].insert(v) 
next 

지도의 목록은 연결된 구성 요소입니다.