왜 위상 정렬을 이용하면 그래프 사이클이 있는지 판단할 수 있을까요?
그래프에 사이클이 있는지 없는지 판단하는 방법 중 하나는 위상 정렬을 이용하는 것입니다. 어떻게 이용한다는 것일까요? 방향성이 있는 그래프에서, indegree가 0인 게 하나도 없다면 사이클이 있다고 판단합니다. 물론, indegree가 0인 노드가 있는데 사이클이 있는 경우도 있습니다만, 이건 글의 말미에 잠깐 다루겠습니다. 먼저, 아래와 같이 조건을 제한해 보겠습니다. 방향성이 있는 그래프에서 아래 조건이 성립합니다. 이 경우, indegree 값이 0인 노드가 존재하지 않는 그래프에 대해서 판단하는 것 보다는 조금이나마 더 쉽습니다. 사이클이란, i에서 i로 가는 경로를 의미합니다. 제한된 조건을 만족하는 노드 갯수가 n인 그래프를 생각해 봅시다. 일단 indegree 값이 1이므로, 나가는 것이..
자료알고/알고리즘
2021. 5. 3. 06:45
최근댓글