Википедия объясняет граф зависимостей очень интуитивно (IMO), ссылаясь на то, что грань идет от a => b, когда a зависит от b.Другими словами, мы можем сразу же найти прямые зависимости любого узла (если они есть), посмотрев на его соседей, доступных в списке смежности.
Кажется, что это разумный способ реализовать зависимости;это позволяет нам выполнять топологическую сортировку в основном так же легко, как выполнять обход в глубину (DFS от каждого узла в графе).Если узлы представляют «задачи», то мы можем выполнить / посетить задачу только тогда, когда все ее переходные зависимости были выполнены / посещены.Листовые узлы посещаются первыми и т. Д.
Страница Википедии для топологической сортировки объясняет определение следующим образом:
В информатикеТопологическая сортировка или топологическое упорядочение ориентированного графа - это линейное упорядочение его вершин, такое, что для каждого направленного ребра uv от вершины u до вершины v, u предшествует v в упорядочении.
Этопротивоположность того, что я ожидал, учитывая «граф зависимостей».Мы только что объяснили, что если a зависит от b, существует направленное ребро a => b, и мы должны посетить / выполнить b до a.Однако, с помощью приведенного выше графика, поскольку мы выполняем / посещаем задачу u до v, очевидно, что v зависит от u.Так что, если я не ошибаюсь, кажется, что входной граф, который ожидает страница сортировки топографических данных Вики, является «графом зависимостей» с перевернутыми ребрами.Алгоритмы на странице подтверждают это;например, их подход DFS будет начинаться с узла n, повторяться на узлах, которые зависят от n (не от n зависимостей), после чего предваряет n к головенекоторого списка, поэтому он появляется раньше, чем его иждивенцы.Результат тот же, что и у ДПФ, который я объяснил, и, чтобы быть ясным, я не говорю, что на обеих страницах нет ничего неправильного, он просто демонстрирует несколько способов сделать что-то.
Хотя это вики действительно кажется страннымимеет это определение графа зависимостей, но, похоже, использует его инверсию на странице топологической сортировки, повторяя через обратные зависимости и по существу обращая список вывода.
Вопрос
Мой единственный вопрос:: есть ли какая-то явно очевидная причина, по которой мне не хватает, что ожидаемый граф на странице топологической сортировки в основном противоположен dfn «графа зависимостей»?Кажется неочевидным, что мы переходим от n к n зависимым и эффективно обращаем вывод, записывая что-то вроде стека.
В более общем случае график, который, как кажется, ожидает топологическая страница сортировкиВ любом случае, это не очень хороший граф зависимостей.Если бы мы считали этот граф каноническим «графом зависимостей», то для того, чтобы найти зависимости n, нам пришлось бы перебирать весь граф с вопросом «Указывает ли этот узел на n?», Что выглядит странно.