목록진입차수 (1)

yon11b

위상 정렬- 정점의 진입차수를 이용하여

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