Алгоритм самого длинного пути для назначения слоя

Question

Я работаю над программой для создания организационной структуры компании. Я читал об алгоритме самого длинного пути для наложения вершин, и одна вещь меня беспокоила. Чтение, которое я сделал, предполагает, что график должен быть послойным снизу вверх, начиная с размещения узлов без дочерних элементов на нижнем слое, а затем работая вверх. Тем не менее, я также читал, что алгоритм самого длинного пути приводит к графам с очень широким дном.

Я думал, что попробую построить график сверху вниз, начиная с узлов, у которых нет родителей, и прокладывая себе путь вниз. Может быть, это обычное дело, и я просто не видел, чтобы оно использовалось, но я беспокоюсь, что есть какая-то причина, по которой я не вижу, которая делает этот подход нецелесообразным. Я что-то упускаю?

Answer 1

Алгоритм самого длинного пути минимизирует высоту, но по существу игнорирует ширину. Если вы наслоите график снизу вверх, а на графике будет много стоков (вершин с нулевой степенью отклонения), то вы получите широкий нижний слой. Если вы наслоите график сверху вниз, и у него будет много источников (вершин с нулевым градусом), то вы получите широкий верхний слой. Если вы сравните количество приемников с количеством источников, вы можете выбрать, какой вариант использовать. Тем не менее, вы все равно можете получить широкие промежуточные слои. Чтобы уменьшить (не минимизировать) ширину по всем слоям, вам нужно взглянуть на алгоритм, такой как алгоритм Кофмана-Грэма.