Уровень вычисления узлов в графе

Question

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

Ожидаемый результат:

Vertex | Level
1      | 0
2      | 1
3      | 2
4      | 1
5      | 3
6      | 4

В этом конкретном случае, если мы начнем с применения DFS на 4 , то все результаты для вершин 4, 3, 5 и 6 будут неверными, так как 1 имеет уровень 0. Я старался всегда учитывать наилучший результат для каждого из узлов, поэтому в данном случае результаты для 3 , 5 и 6 заменяются при применении DFS на 1. Он работает, но я не могу найти способ правильно вычислить уровень вершины 4.

Я работаю только с направленными ациклиями c графики.

Я не включаю сюда какой-либо код, потому что это довольно простая реализация DFS, и я не борюсь с реализацией.

Любые подсказки были бы очень признательны.

Answer 1

Вы можете вычислять уровни, начиная с каждой вершины, не имея входящего ребра. Затем вы можете сохранить максимальное значение для каждой вершины до конца. Например: - Вершина 3 будет иметь значения 1 и 2 при переходе от начальных точек вершины 1 и вершины 4 соответственно. Наконец, вы можете обновить вершины, не имеющие входящего ребра (номер на дочернем элементе -1). Если есть ситуация, когда у такой вершины есть несколько дочерних элементов, вы можете выбрать дочерний элемент с максимальным числом на нем для замены, а затем снова запустить алгоритм из этой вершины, чтобы увидеть, не изменились ли номера, назначенные любому из других дочерних элементов. .