yon11b

위상 정렬의 방법에는 두 가지가 있다. 하나는 진입차수를 이용한 방법이고 다른 하나는 DFS를 특화한 방법이다. 여기서는 진입차수를 이용한 방법에 대해서 알아보도록 하겠다. 위상정렬은 진입간선이 0인 것들을 기준으로 삼는다. 따라서 진입간선을 알아내야 한다. 이 때 효율적으로 진입간선의 여부를 알 수 있는 방법이 있는데 바로 제일 처음에 진입 간선의 수를 다 세어 놓는 것이다. A0: A로 들어오는 간선의 수가 0개이다. B2: B로 들어오는 간선의 수가 2개이다. 맨 처음에 A를 시작 노드로 했을 때, A가 B를 가리키므로 B로 들어오는 간선의 수를 하나 감소시켜서 B1로 만든다. (고려대상에서 제외한다.) 효율적으로 진입 차수가 0인 것을 찾는 방법 다 순회하면서 찾는다.? ⇒ 너무 비효율적 해결책:..

사전 지식 DAG이란? 방향 비싸이클 그래프(Directed Acyclic Graph) 방향 사이클이 존재하지 않는 방향 그래프를 말한다. 다시 제자리로 돌아올 수 있는 경로가 없는 그래프. 위상정렬이란? DAG로부터 위상 순서를 얻는 절차이다. 자기한테 오는 간선이 없는 정점들이 맨 앞에 온다. 여기서는 A와 D가 맨 앞에 올 수 있다. 1번과 2번으로부터 들어오는 간선을 제외한 나머지 간선들을 생각해서 제일 앞에 올 수 있는 정점을 구한다. 번호를 다 매기지 않았는데 만약 진입간선이 있는 정점들밖에 남지 않았다면 이는 무엇을 의미하는가? ⇒ 싸이클이 있다는 것을 의미한다.(DAG이 아니다!)