Вступление
Мы уже знаем, как насчет топологического вида ориентированного ациклического графа. Так зачем нам пересматривать этот алгоритм? Прежде всего, я никогда не упоминал о его сложности, поэтому, чтобы понять, почему нам нужна ревизия, давайте вернемся к алгоритму.
У нас есть ориентированный ациклический граф (DAG). Там нет циклов, поэтому мы должны пойти по какому-то порядку, расположив все вершины графа в таком порядке, что если есть направленное ребро (u, v), то u должно предшествовать v в этом порядке.
Процесс размещения всех вершин DAG в таком порядке называется топологической сортировкой. Обычно используется при планировании задач или при поиске кратчайших путей в группе обеспечения доступности баз данных.
Сам алгоритм довольно прост для понимания и кодирования. Мы должны начать с вершины (вершин), которые не имеют предшественников.
Мы помещаем их в наш отсортированный список в случайном порядке. Поскольку они не зависят друг от друга, мы можем предположить, что они уже одинаково отсортированы. Действительно, думая о графике задач, если есть задачи, у которых нет предшественников (они не зависят от других задач перед ними) и которые не зависят друг от друга, мы можем расположить их в случайном порядке (и выполнить их в случайном порядке). заказ).
Когда у нас есть вершины без предшественников, мы должны удалить ребра, начиная с них. Тогда — иди опять с вершинами без предшественников.
Это так просто, так зачем нам пересматривать этот алгоритм? Ну, в основном из-за его эффективности.
обзор
Как мы знаем, большинство алгоритмов графа зависят от того, как граф представлен в нашем приложении. В качестве двух основных представлений мы рассматриваем матрицу смежности…
… и списки смежности.
Давайте сначала рассмотрим некоторые из основных подходов, чтобы получить топологически отсортированный список в конце алгоритма.
Что мы можем сделать, чтобы найти вершины без предшественников? Мы можем только отсканировать весь список вершин.
Матрица смежности
В случае, если мы используем матрицу смежности, нам нужно пространство | V | ^ 2 для хранения графа. Чтобы найти вершины без предшественников, мы должны просканировать весь граф, что будет стоить нам O (| V | ^ 2) времени. И мы должны будем сделать это | V | раз. Это будет | V | ^ 3 трудоемкий алгоритм, а для плотных графов это будет довольно неэффективный алгоритм.
Списки Смежности
Как насчет списка смежности? Там нам нужно | E | пространство для хранения ориентированного графа. Как быстро мы можем найти узел без предшественника? Практически нам понадобится время O (| E |). Таким образом, в худшем случае у нас снова O (| V | ^ 2) программ, отнимающих много времени.
Итак, что можно сделать, чтобы оптимизировать этот алгоритм?
Практически мы можем начать с выбора случайной вершины и «возвращаться», пока не получим узел без предшественников. Этот подход может быть очень эффективным, но также очень неэффективным. Прежде всего, если нам придется сканировать весь путь до узла без предшественников, это будет стоить нам | V | время, но если мы застряли на узле, у которого нет предыдущего узла, то у нас будет постоянная скорость.
Это означает, что мы можем немного изменить алгоритм, чтобы значительно улучшить алгоритм. Нам просто нужно сохранить как входящие, так и исходящие ребра и немного изменить списки смежности.
Какой сейчас алгоритм?
Сначала мы легко находим узлы без предшественников. Затем, используя очередь, мы можем сохранить узлы без предшественников, и в каждой очереди мы можем удалить ребра от узла ко всем остальным узлам.
Псевдокод
Represent the graph with two lists on each vertex (incoming edges and outgoing edges) Make an empty queue Q; Make an empty topologically sorted list T; Push all items with no predecessors in Q; While Q is not empty a. Dequeue from Q into u; b. Push u in T; c. Remove all outgoing edges from u; Return T;
Такой подход даст нам лучшую производительность, чем подход «грубой силы». Сложность времени выполнения O (| V | + | E |). Проблема в том, что нам нужно дополнительное пространство и рабочая очередь, но этот подход является прекрасным примером того, как, используя дополнительное пространство, вы можете получить более эффективный алгоритм.