Algorithm1 그래프에서 SCC (Strongly Connected Component) 찾기 SCC에 대한 증명을 위한 글이 아님을 알려드립니다! SCC란 그래프에서 서로 다른 노드 u, v 2개를 뽑았을때, u->v로도 직간접적으로 갈 수 있고, v->u로도 역시 직간접적으로 갈 수 있는 노드들의 집합이다. 위의 그림에서 SCC를 추출해보자면, [1, 2, 3], [4, 5], [6] 으로 나뉠 것이다. 사람의 눈으로 직관적인 분리는 쉽지만, 이를 코드로 구현할 때를 생각해보자 그런데! SCC를 찾기 아주 조금 전에 우선적으로 생각해볼 문제가 있다. 1->2로 가는 그래프가 있다 가정해보자. 1번 노드에서 시작해 후위표기 즉 post number를 각 노드에 붙인다 하면, 1번 노드가 2번이 되고 2번 노드는 1번이 될 것이다. 2에서 시작하는 후위표기를 하면 이 역시 1번 노드가 2번, 2번.. 2023. 12. 7. 이전 1 다음
