목록SCC (1)

codinging

[알고리즘] 강한 연결 요소(Strongly Connected Component, SCC) 알아보기

강한 연결 요소 그래프에서 강하게 연결 되어있는 집합이다. 같은 SCC집합에 속해있는 정점끼리는 도달가능하다는 특징을 가지고 있다. 집합내 모든 두 점이 서로 도달 가능할때 강하게 연결 되어있다고 한다. 위의 그림과 같은 그래프로 설명을 할 것 이다. 위의 그래프에서의 SCC는 다음 그림과 같은 집합으로 나타낼 수 있다. 같은 집합내의 원소들은 서로 도달가능하다. 예를들어 2와 4 를 보면 2는 4로 도달이 가능하지만 4는 2로 도달할 수 없기 때문에 2, 4는 같은 SCC가 아니다. 반면에, {1,2,3} 을 보면 1에서 2, 1에서 3 / 2에서 1 ,2에서 3/ 3에서 1, 3에서 2 어떤 두 정점을 잡아도 해당 노드로 이동이 가능하기 때문에 같은 SCC에 속한다고 보면 된다. 이제 SCC의 원소를..
Algorithm 2023. 4. 9. 16:26
이전 Prev 1 Next 다음