티스토리 뷰
그래프 - SCC
SCC란?
SCC(Strongly Connected Component)는 방향 그래프에서 임의의 두 정점 U,V가 있을때, U->V로 가는 경로가 존재한다면 그 그룹은 SCC라 부를 수 있습니다. 이때, U->V로 가는 경로는 직, 간접적인 경로를 의미합니다.
SCC의 특징
1. 같은 SCC내에서 뽑은 임의의 U,V점에서 U->V 혹은 V->U의 경로(직/간접적)는 항상 존재합니다.
2. SCC는 Maximal한 성질을 가지고 있어 SCC가 형성된다면 형성될 수 있는 가장 큰 집합으로 형성이됩니다.
--강한결합요소끼리는 서로 일방향적으로 연결되어 있습니다.
구현 코드
반응형