강 한 연결 분기 및 kosaraju 알고리즘

도 론 에서 가장 중요 한 구 조 는 많은 도 론 문제 가 강 한 연결 지점 으로 전환 되 어 처리 의 복잡 도 를 낮 출 수 있다.강 한 연결 지점 의 모든 점 은 서로 연결 되 어 있 으 며, 이 를 하나의 점 으로 수축 시 켜 그림 의 처 리 를 간소화 할 수 있다.강 한 연결 지점 중의 점 집합 은 가장 큰 집합 이다. 즉, 어떤 다른 점 을 더 넣 어도 연결 되 지 않 는 다.
 
인용 1: 그림 G 의 두 개의 강력 한 연결 지점 인 C, C '가 존재 한다 면 u 는 C 에 속 하고 u 는 C 에 속 하 며 (u, u) 는 G 의 한 변 이 라면 반드시 다른 변 (v', v) 이 존재 하지 않 고 v '는 C 에 속 하 며 v 는 C 에 속한다.
반증 법 은 이러한 변 (v ', v) 이 존재 한다 고 가정 하면 강 한 연결 지점 C 와 C' 는 서로 연 결 된 것 이다. 즉, 강 한 연결 지점, 모순 에 속한다.이로부터 분지 도의 개념 을 가 질 수 있다
 
정의: 그림 G 의 분기 도 GSCC = (VSCC, ESCC) 는 그림 G 의 모든 강 한 연결 가 지 를 하나의 점 으로 간주 합 니 다. 이 점 은 VSCC 에 속 합 니 다. 즉, 분기 도 GSCC 의 포 인 트 는 그림 G 의 강 한 연결 분기 수 입 니 다. G 의 강 한 연결 가 지 를 C1, C2,..., Ck 로 설정 하면 분기 도의 점 집 GSCC 는 v1, v2,.., vk 입 니 다.정의 변 (vi, vj) 은 ESCC 에 속 하고 G 에 한 변 (x, y) 만 있 고 x 는 Ci 에 속 하 며 y 는 Cj 에 속 하 며 인용 1 로 이 변 의 방향 을 확보 하 는 것 이 유일한 것 입 니 다.
 
인용 2: 그림 G 의 분지 도 GSCC 는 유향 무 환 도 (DAG)
반증 법 은 인용 1 과 유사 하 다 는 것 을 증명 한다. 만약 에 하나의 고리 가 존재 한다 고 가정 하면 이 고리 의 모든 강 한 연결 가 지 는 서로 도달 할 수 있 고 여러 개의 강 한 연결 분기 와 모순 된다.그래서 분기 도 GSCC 는 방향 무 환 도 입 니 다.
 
연습 문제 22.5 - 1 한 변 을 늘 리 는 것 은 그림 G 의 강 한 연결 지점 수 에 어떤 영향 을 줍 니까?
한 변 (u, v) 을 추가 하면 u 는 강 한 연결 지점 Ci 에 속 하고 v 는 강 한 연결 지점 Cj 에 속 합 니 다.
(1) 만약 에 i = = j, 즉 같은 강 한 연결 지점 에 속 하면 이 변 을 추가 하면 강 한 연결 지점 의 갯 수 에 영향 을 주지 않 습 니 다.
(2) 만약 에 Cj 에서 Ci 까지 경로 가 없 으 면 이 변 을 추가 하면 강 한 연결 지점 의 개수 에 영향 을 주지 않 습 니 다.
(3) 만약 에 Cj 가 Ci 에 하나의 경로 가 존재 한다 면 이 변 을 추가 한 후에 Cj, Ci,... Cj 를 사용 하여 하나의 링 을 형성 하고 이 링 에 있 는 모든 강 한 연결 지점 은 새로운 연결 지점 이 되 며 전체적인 강 한 연결 지점 수 는 줄어든다.
 
정의: 그림 G 의 전환 그림 GT 는 그림 G 의 모든 변 의 방향 을 GT 로 바 꾸 고 G = (V, E), GT = (V, ET), ET = {(u, v): (v, u) 는 E} 에 속한다.
 
인용 3: 그림 GT 와 G 는 같은 강 한 연결 지점 을 가지 고 있다
그림 G 의 강력 한 연결 지점 인 Ci, 그림 GT 에서 Ci 가 대응 하 는 CiT 를 가정 하면 이 서브 맵 은 서로 연결 되 는 동시에 매우 큰 연결 서브 맵 이기 도 한다. 그렇지 않 으 면 점 u 가 존재 하여 CiT 와 u 가 서로 연결 되면 그림 G 에서 Ci 와 u 도 서로 연결 되 고 모순 된다.
이로써 그림 GT 와 G 의 강 한 연결 지점 이 같다 는 것 을 증명 한다.
 
연습 문제 22.5 - 4 증명 (GT) SCC) T = GSCC
인용 3GT 와 G 의 강 한 연결 지점 이 같 으 면 (GT) SCC) T 는 GSCC 와 같은 점 집합 을 가지 고 있 으 며, 그 변 집합 도 같다 는 것 만 증명 하면 된다.
가설 변 (x, y) 은 GSCC 에 속한다. 즉, G 에 두 개의 강력 한 연결 지점 이 존재 한다. Ci, Cj, x 는 Ci 에 속 하고 y 는 Cj 에 속 하 며 (y, x) 는 반드시 (GT) SCC 에 속 하기 때문에 (x, y) 는 반드시 (GT) SCC 에 속한다. T
만약 에 변 (x, y) 이 (GT) SCC) T 에 속한다 고 가정 하면 (y, x) 는 반드시 (GT) SCC 에 속 하고 (x, y) 는 반드시 GSCC 에 속한다.
 
 
인용 4: 어떤 강 한 연결 지점 이 든 그림 G 의 DFS 과정 에 포 함 된 하위 트 리 입 니 다.
증명, 하나의 강 한 연결 지점 C, 그림 G 의 DFS 과정 에서 강 한 연결 지점 C 에서 첫 번 째 방문 점 이 u 라 고 가정 하면 C 중의 다른 점 은 모두 u 에서 도달 할 수 있 고 흰색 경로 의 정리 에 따라 C 중의 나머지 모든 점 은 u 의 자손 결점 이다. 이렇게 u 를 나무 뿌리 로 하 는 서브 트 리 에는 반드시 이 연결 지점 C 가 포함 되 어 있다.
인용 4 에서 알 수 있 듯 이 임의의 결점 부터 DFS 는 모든 강 한 연결 지점 을 반드시 특정한 DFS 트 리 에 포함 시 킬 것 이다. 즉, 하나의 DFS 트 리 는 반드시 몇 개의 강 한 연결 지점 으로 구 성 될 것 이다.이 동시에 이 도입 도 강 한 연결 분기 Tarjan 알고리즘, Kosaraju 의 기초 이다.
 
DFS 과정 에서 결점 의 종료 시간 f (v) 가 있 습 니 다. 여기 서 결점 집합 의 종료 시간 f (U) 를 정의 합 니 다.
f (U) = max {f (u): u 는 U} 에 속 합 니 다. 즉, 결산 점 집합 에서 DFS 의 결산 시간 을 마지막 으로 완성 합 니 다.
 
인용 5: 그림 G 의 임의의 두 개의 강 한 연결 지점 C, C ', 한 변 (u, v) 이 존재 하면 u 는 C 에 속 하고 v 는 C 에 속 하 며 f (C) > f (C))
증명: C 와 C '라 는 두 집합 에서 첫 번 째 방문 의 결산 점 을 고려 합 니 다.
(1) 첫 번 째 방문 의 결산 점 x 는 C 에 속 하고 흰색 경로 의 정리 에 따라 C 와 C '의 나머지 결산 점 은 모두 u 의 자손 결산 점 이기 때문에 결산 점 x 가 마지막 에 끝나 고 f (C) > f (C) 가 분명 하 다.
(2) 첫 번 째 방문 의 결산 점 x 는 C '에 속 하고 x 에서 반드시 C 에 접근 할 수 없 기 때문에 C' 의 나머지 결산 점 은 모두 x 의 자손 결산 점 f (C) = f (x) 이다. 결산 점 x 가 결산 점 에 접근 할 때 C 중의 결산 점 은 방문 되 지 않 았 기 때문에 f (C) > f (C) 가 분명 하 다.
이 인용 은 무 환 도 에 토폴로지 서열 이 있 는 성질 로 볼 수 있다. 즉, 무 환 도 에 한 변 (u, v) 이 존재 하 는 경우 f (u) > f (v) 가 있어 야 한다. 강 한 연결 가 지 를 한 점 으로 수축 하면 곧 그림 G 를 그 분기 도 GSCC 로 볼 것 이다.
그 전환 도 GT 에 대해 말하자면 결론 은 정반 대 이다. 만약 에 변 (u, v) 이 GT 에 속 하고 u, v 가 두 개의 강 한 연결 지점 C, C 에 속한다 면 f (C) < f (C) 가 있다.
 
Kosaraju 알고리즘: 첫 번 째 DFS 에서 그림 G 의 토폴로지 순 서 를 얻 은 다음 에 토폴로지 순 으로 그림 GT 에 대해 DFS 를 한 번 진행 하여 얻 은 DFS 숲 은 서로 다른 강 한 연결 지점 입 니 다.
이 알고리즘 은 두 번 의 DFS 가 필요 하 며, 아래 의 모든 f 는 첫 번 째 DFS 과정 을 대상 으로 한다.수학 귀납법 을 사용 하여 증명 하 였 으 며, 두 번 째 DFS 시 앞의 k 개의 DFS 트 리 가 모두 강 한 연결 지점 이 라 고 가정 하 였 으 며, k = 0 시 에 분명 하 다.
귀납 적 가설 에 의 하면 앞의 k 개의 DFS 트 리 는 모두 강 한 연결 지점 이 고 두 번 째 DFS 과정 에서 남 은 모든 점 중 가장 늦게 끝 난 결점 u 를 취한 다. u 가 강 한 연결 지점 C 에 속한다 고 가정 하면 아직 방문 하지 않 은 다른 연결 지점 C 에 대해 f (u) = f (C) > f (C) 가 있 고 인용 5 에서 알 수 있 듯 이 C 에서 C 까지 의 변 이 존재 하지 않 는 다. 그래서 방문 u 부터 시작한다.DFS 프로 세 스 가 C 에 접근 한 후에 끝 났 는데 마침 완전한 강 한 연결 지점 C 이다.
G 를 GSCC 로 보고 Kosaraju 알고리즘 을 이해 합 니 다. 첫 번 째 DFS 는 GSCC 를 토폴로지 정렬 한 것 과 같 습 니 다. GSCC 는 방향 이 있 고 고리 가 없 기 때 문 입 니 다.그 다음 에 두 번 째 DFS 를 할 때 GSCC 의 토폴로지 역순 으로 GT 에 DFS 를 하 는 것 은 (GT) SCC 역 토폴로지 정렬 방식 으로 DFS 를 하 는 것 과 같 기 때문에 모든 DFS 트 리 는 (GT) SCC 의 한 점 집합, 즉 G 의 강 한 연결 지점 과 (GT) SCC) T = GSCC, 두 번 째 DFS 는 GSCC 의 토폴로지 정렬 에 대응 하 는데 이것 은 Kosaraju 알고리즘 의 숨겨 진 성질 이다.
 
이 알고리즘 은 처음에는 신기 하 게 보 였 습 니 다. 간단 한 DFS 두 번 이면 강력 한 연결 가 지 를 얻 을 수 있 고 다른 데이터 구 조 를 거의 사용 하지 않 습 니 다. Kosaraju 라 는 인도 인 에 게 감 사 드 립 니 다.
마지막 으로 코드 구현:

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>

#include "list.h"               /* list from Linux_kernel */
#include "graph.h"

static void print_scc(struct list_head *head, int scc_no)
{
    struct link_vertex *v = NULL;

    printf("The %d SCC:
", scc_no);
    list_for_each_entry(v, head, qnode) {
        printf("%d ", v->vindex);
    }
    printf("
");
}

int find_scc(struct link_graph *G)
{
    int *color, i = 0;
    struct link_graph GT;
    struct link_vertex *v = NULL;
    struct list_head topo_head, scc_head;
    
    color = malloc(sizeof(int) * G->vcount);
    for (i = 0;i < G->vcount;i++) {
        color[i] = COLOR_WHITE;
    }

    INIT_LIST_HEAD(&topo_head);
    graph_topo_sort(G, &topo_head);

    printf("

Output all components of this graph

");
    graph_transpos(G, >);
    i = 0;
    list_for_each_entry(v, &topo_head, qnode) {
        INIT_LIST_HEAD(&scc_head);
        if (color[v->vindex] == COLOR_WHITE) {
            DFS_visit_topo(>, GT.v + v->vindex, color, &scc_head);
            print_scc(&scc_head, i++);
        }
    }
    link_graph_exit(>);
    free(color);
    printf("This graph has %d scc components

", i);

    return 0;
}