topological sort1 위상정렬, DAG(Directed Acyclic Graph) 그래프의 분류 중 하나로 DAG,사이클이 없는 방향그래프가 있다. DAG에서는 항상 위상정렬이 가능하고 그 후에 동적 계획법을 적용하는 것이 가능하다. ㅁ 정점u에서 정점v로 가는 최단/최장 경로는 무엇인가? ㅁ 경로 중 간선의 개수가 가장 적은/많은 경우 간선은 몇 개인가? ㅁ 모든 경로에 포함된 정점은 어떤 것이 있는가? ㅁ 서로 다른 경로의 개수는 몇 개인가? 등등.. 위상정렬된 순서대로 처리하면 구할 수 있다. 또한 모든 동적 계획법 문제는 DAG로 나타낼 수 있다. 이 때 정점은 dp상의 상태에, 간선은 상태간의 관계에 대응된다. ex)동전문제, 냅색.. 사이클이 없는 그래프에서 정점의 탐색이 끝난 순서 (fin[u]=true)의 반대 순서로 처리하면 위상정렬 순서 (예)https://suunt.. 2019. 8. 18. 이전 1 다음
