데이터 구조의 그림 - 연결 분량

연결 분량 의 정의:
무방 향도 에서 정점 vi 에서 정점 vj 까지 경로 가 있 으 면 vi 와 vj 가 연결된다 고 한다.만약 에 그림 에서 임의의 두 정점 사이 가 모두 연결 된다 면 이 그림 을 연통 도 라 고 부른다. 그렇지 않 으 면 이 그림 을 비 연통 도 라 고 부른다. 그 중의 극 대 연통 자 도 를 연통 분량 이 라 고 한다. 여기 서 이른바 극 대 란 서브 맵 에 포 함 된 정점 개수 가 매우 크다 는 것 을 말한다.방향 도 에서 만약 에 모든 정점 vi 와 vj 에 대해 vi 에서 vj 까지 와 vj 에서 vi 까지 모두 경로 가 있다 면 이 그림 을 강 한 연결 도 라 고 부른다.그렇지 않 으 면 그 중의 매우 강 한 연결 자 도 를 강 한 연결 분량 이 라 고 부른다.
그림 G 에 두 개의 정점 사이 에 최소한 하나의 경로 가 존재 한다 면 두 개의 정점 이 강 한 연결 (strongly connected) 이 라 고 합 니 다.그림 G 의 두 정점 에 강 한 연결 이 있 으 면 G 는 강 한 연결 그림 이 라 고 한다.비 강 연통 도 는 그림 에 대한 매우 강 한 연통 서브 맵 이 있 는데 강 한 연통 분량 (strongly connected components) 이 라 고 합 니 다.
다음 그림 에서 서브 맵 {1, 2, 3, 4} 은 하나의 강력 한 연결 분량 으로 정점 1, 2, 3, 4 두 개 에 달 할 수 있 기 때문이다.{5}, {6} 도 각각 두 개의 강 한 연결 분량 이다.
직접 정의 에 따라 양 방향 으로 교 집합 을 옮 겨 다 니 는 방법 으로 강 한 연결 분량 을 구하 고 시간 복잡 도 는 O (N ^ 2 + M) 입 니 다.더 좋 은 방법 은 Kosaraju 알고리즘 이나 Tarjan 알고리즘 입 니 다. 이들 의 시간 복잡 도 는 모두 O (N + M) 입 니 다.본 고 는 Tarjan 알고리즘 을 소개 한다.
[Tarjan 알고리즘]
Tarjan 알고리즘 은 그림 의 깊이 를 우선 검색 하 는 알고리즘 을 기반 으로 모든 강 한 연결 분량 은 검색 트 리 의 한 그루 의 트 리 입 니 다.검색 할 때 현재 검색 트 리 에서 처리 되 지 않 은 노드 를 스 택 에 추가 하고 거 슬러 올 라 갈 때 스 택 꼭대기 에서 스 택 에 있 는 노드 가 강 한 연결 분량 인지 판단 할 수 있 습 니 다.
DFN (u) 을 노드 u 검색 의 순서 번호 (시간 스탬프) 로 정의 하고 Low (u) 는 u 또는 u 의 서브 트 리 가 거 슬러 올 라 갈 수 있 는 최초의 스 택 에서 노드 의 번 호 를 정의 합 니 다.정의 에서 얻 을 수 있다.

Low(u)=Min{    

   DFN(u), 

   Low(v),(u,v)    ，u v     

   DFN(v),(u,v)           (    )

}

DFN (u) = Low (u) 일 때 u 를 뿌리 로 하 는 검색 서브 트 리 의 모든 노드 는 강력 한 연결 분량 입 니 다.
알고리즘 위조 코드 는 다음 과 같다.

 
    
tarjan(u)
{
    DFN[u]=Low[u]=++Index       //    u       Low  
    Stack.push(u)                              //    u    
    for each (u, v) in E                       //       
        if (v is not visted)   //     v     
            tarjan(v)          //      
            Low[u] = min(Low[u], Low[v])
        else if (v in S)                   //     v    
            Low[u] = min(Low[u], DFN[v])
    if (DFN[u] == Low[u])     //     u        
        repeat
            v = S.pop        //  v  ，            
            print v
        until (u== v)
}
  
다음은 알고리즘 프로 세 스에 대한 시범 이다.
노드 1 부터 DFS 를 시작 하여 옮 겨 다 니 는 노드 를 스 택 에 넣 습 니 다.노드 u = 6 을 찾 았 을 때 DFN [6] = LOW [6] 에서 강력 한 연결 분량 을 찾 았 습 니 다.u = v 까지 스 택 을 반환 합 니 다. {6} 은 강 한 연결 분량 입 니 다.
노드 5 를 되 돌려 줍 니 다. DFN [5] = LOW [5] 를 발 견 했 습 니 다. 스 택 을 탈퇴 한 후 {5} 은 강력 한 연결 분량 입 니 다.
노드 3 을 되 돌려 노드 4 를 계속 검색 하고 4 를 스 택 에 추가 합 니 다.노드 4 방향 노드 1 이 뒤쪽 방향 이 있 고 노드 1 이 스 택 에 있 기 때문에 LOW [4] = 1.노드 6 은 이미 스 택 에서 나 왔 습 니 다. (4, 6) 은 가로 포크 이 고 3 으로 돌아 갑 니 다. (3, 4) 는 나뭇가지 옆 이기 때문에 LOW [3] = LOW [4] = 1 입 니 다.
노드 1 로 계속 돌아 가 마지막 으로 노드 2 에 접근 합 니 다.방문 변 (2, 4), 4 는 아직 스 택 에 있 기 때문에 LOW [2] = DFN [4] = 5.1 을 되 돌려 보 니 DFN [1] = LOW [1] 를 발견 하고 스 택 의 노드 를 모두 꺼 내 하나의 연결 분량 {1, 3, 4, 2} 을 구성 합 니 다.
이로써 알고리즘 이 끝났다.이 알고리즘 을 통 해 그림 의 세 개의 강 한 연결 분량 {1, 3, 4, 2}, {5}, {6} 을 구 했 습 니 다.
Tarjan 알고리즘 을 실행 하 는 과정 에서 정점 마다 한 번 씩 방문 되 었 고 스 택 에 한 번 만 드 나 들 었 으 며 각 변 에 한 번 만 접근 되 었 기 때문에 이 알고리즘 의 시간 복잡 도 는 O (N + M) 인 것 을 알 수 있 습 니 다.