타잔 SCC 시각화
DFS 기반으로 방향 그래프의 강연결 요소(Strongly Connected Components)를 찾는 과정을 학습하세요
그래프★★★
속도
1 / 1SCC 수: 0
현재 탐색 노드 스택 위 미방문 SCC 그룹
DFS로 정점을 탐색하며 discovery/low-link 값을 추적하고 SCC를 추출하는 과정을 관찰하세요.
DFS로 정점을 탐색하며 discovery/low-link 값을 추적하고 SCC를 추출하는 과정을 관찰하세요.
타잔 SCC란?
한 번의 DFS로 방향 그래프의 모든 강연결 요소(SCC)를 찾는 알고리즘입니다. SCC란 모든 정점 쌍이 서로 도달 가능한 최대 부분그래프입니다.
사용 방법
- 1방향 그래프를 생성하고 실행하세요
- 2DFS 탐색 순서와 discovery/low-link 값 변화를 관찰하세요
- 3스택에서 SCC가 추출되는 순간을 확인하세요
- 4같은 색의 노드가 하나의 SCC입니다
동작 원리
- 1DFS로 정점을 방문하며 discovery time과 low-link value를 할당합니다
- 2방문한 정점을 스택에 넣고, 자손의 low-link 값으로 자신의 low-link를 갱신합니다
- 3정점의 low-link == discovery이면 SCC의 루트 → 스택에서 해당 SCC 원소를 모두 팝합니다
- 4시간복잡도 O(V + E)로 한 번의 DFS에 완료됩니다
실무 활용
- •컴파일러 의존성 분석에서 순환 의존성 그룹 검출
- •소셜 네트워크의 커뮤니티/그룹 탐지
- •웹 크롤러의 링크 구조 분석
- •2-SAT 문제 풀이의 핵심 서브루틴
비슷한 알고리즘
- •코사라주(Kosaraju) — DFS 2회로 SCC 탐색, 구현이 더 직관적이나 그래프 전치 필요
- •가보우(Gabow) — 스택 2개 사용, 타잔과 같은 복잡도
- •위상정렬 — DAG 전용, SCC를 축약한 후 적용 가능
학습 팁
- •discovery와 low-link 값의 의미를 먼저 이해하세요
- •작은 그래프에서 수동으로 값을 추적해본 후 시각화와 대조하세요
- •SCC 축약(condensation graph) 개념과 연결하여 학습하세요
자주 묻는 질문
Q. SCC가 왜 중요한가?
A. 순환 의존성 분석, 2-SAT, 그래프 축약 등 많은 알고리즘의 기반이 됩니다.
Q. 무방향 그래프에서도?
A. 무방향 그래프에서는 연결 요소(Connected Component) 문제이며, 단순 DFS/BFS로 풀 수 있습니다.