레이어 할당을위한 최장 경로 알고리즘

Question

나는 회사의 조직도를 생성하는 프로그램을 만들고있다. 나는 꼭지점을 쌓는 가장 긴 경로 알고리즘에 대해 읽었으며, 한 가지가 나를 괴롭혔다. 내가 한 글은 그래프가 아래에서부터 계층화되어야한다는 것을 제안합니다. 아래층에 자식이없는 노드를 놓은 다음 시작합니다. 그러나, 나는 또한 가장 긴 경로 알고리즘이 매우 넓은 바닥을 가진 그래프로 연결된다는 것을 읽었습니다.

부모가없고 내림차순으로 작업하는 노드부터 그래프를 위로부터 작성하려고합니다. 어쩌면 이것은 일반적인 것이고 나는 단지 그것을 사용하는 것을 보지 못했지만, 나는이 접근법을 비현실적으로 만드는 것을 보지 못하는 어떤 이유가 있다고 걱정합니다. 내가 빠진 것이 있습니까?

Answer 1

가장 긴 경로 알고리즘은 높이를 최소화하지만 본질적으로 너비를 무시합니다. 상향식에서 그래프를 겹치게하고 그래프에 싱크가 많으면 (0도를 가진 꼭지점) 넓은 바닥 레이어를 얻을 수 있습니다. 위에서 아래로 그래프를 겹치게하고 많은 소스 (0 도의 꼭지점을 가진 꼭지점)가 있으면 넓은 상단 레이어를 얻을 수 있습니다. 싱크 수를 소스 수와 비교하면 사용할 변형을 선택할 수 있습니다. 그러나 여전히 넓은 중간 레이어를 얻을 수 있습니다. 모든 레이어에서 너비를 줄이거 나 최소화하려면 Coffman-Graham algorithm과 같은 알고리즘을 살펴 봐야합니다.