Алгоритм недели: топологическая сортировка графа

Вступление

Давайте предположим, что у нас есть список задач для выполнения. Некоторые задачи зависят от других, поэтому мы должны быть очень осторожны с порядком их выполнения. Если бы отношения между этими задачами были достаточно простыми, мы могли бы представить их в виде связанного списка, что было бы здорово, и мы бы знали точный порядок их выполнения. Проблема заключается в том, что иногда отношения между различными задачами являются более сложными, а некоторые задачи зависят от двух или более других задач, которые, в свою очередь, зависят от одной или нескольких задач и т. Д.

Таким образом, мы не можем смоделировать эту проблему, используя связанные списки или деревья. Единственное рациональное решение — смоделировать задачу с помощью графика. Какой график нам нужен? Ну, нам определенно нужен ориентированный граф, чтобы описать отношения, и у этого графа не должно быть циклов. Поэтому нам нужен так называемый ориентированный ациклический граф (DAG).

Чтобы отсортировать граф с помощью топологической сортировки, нам нужен ацикличный и направленный граф!

Почему у нас нет того, что цикл в графе? Ответ на этот вопрос прост и очевиден. В случае циклического графа мы не сможем определить приоритет выполнения задачи, поэтому мы не сможем правильно отсортировать задачи.

Теперь решение, которое мы хотим, состоит в том, чтобы отсортировать вершины графа в некотором порядке, поэтому для каждого ребра (u, v) u будет предшествовать v. Тогда у нас будет линейный порядок всех задач и, начав их выполнение, мы узнаем что все будет хорошо.

Результатом топологической сортировки должен быть список вершин!

Этот вид сортировки также известен как «топологическая» сортировка (или топсорт), и это один из самых основных графовых алгоритмов.

обзор

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

Изначально мы получаем только вершины без предшественника!

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

Как видно из рисунка выше, даже для вершин с предшественниками наша топологическая сортировка может изменяться. Таким образом, [9, 6, 2, 7, 4, 1] является допустимым топологически отсортированным графом, но [6, 9, 2, 7, 4, 1] также является допустимой топологической сортировкой из того же графа!

Теперь мы можем обобщить алгоритм в несколько основных шагов.

1. Составьте пустой список L и пустой список S;
2. Поместите все вершины без предшественников в L;
3. Пока в L есть предметы;
3.1. Возьмите предмет из L — n и нажмите на S;
3.2. Для каждой вершины m, смежной с n;
3.2.1. Удалить (n, m);
3.2.2. Если у m нет предшественников — нажмите на L;

Изображение выше объясняет шаг 3.2. из алгоритма!

Код

Вот самая базовая реализация PHP . Как видите, короткая реализация показывает нам, насколько прост этот алгоритм. Однако его значение для информатики и программирования огромно.

class G
{
    protected $_g = array(
        array(0, 1, 1, 0, 0, 0, 0),
        array(0, 0, 0, 1, 0, 0, 0),
        array(0, 0, 0, 0, 1, 0, 0),
        array(0, 0, 0, 0, 1, 0, 0),
        array(0, 0, 0, 0, 0, 0, 1),
        array(0, 0, 0, 0, 0, 0, 1),
        array(0, 0, 0, 0, 0, 0, 0),
    );
    protected $_list = array();
    protected $_ts   = array();
    protected $_len  = null;
 
    public function __construct()
    {
        $this->_len = count($this->_g);
 
        // finds the vertices with no predecessors
        $sum = 0;
        for ($i = 0; $i < $this->_len; $i++) {
            for ($j = 0; $j < $this->_len; $j++) {
                $sum += $this->_g[$j][$i];
            }
 
            if (!$sum) {
                // append to list
                array_push($this->_list, $i);
            }
            $sum = 0;
        }
    }
 
    public function topologicalSort() 
    {
        while ($this->_list) {
            $t = array_shift($this->_list);
            array_push($this->_ts, $t);
 
            foreach ($this->_g[$t] as $key => $vertex) {
                if ($vertex == 1) {
                    $this->_g[$t][$key] = 0;
 
                    $sum = 0;
                    for ($i = 0; $i < $this->_len; $i++) {
                        $sum += $this->_g[$i][$key];
                    }
 
                    if (!$sum) {
                        array_push($this->_list, $key);
                    }
                }
                $sum = 0;
            }
        }
 
        print_r($this->_ts);
    }
}
 
$g = new G();
/*
Array
(
    [0] => 0
    [1] => 5
    [2] => 1
    [3] => 2
    [4] => 3
    [5] => 4
    [6] => 6
)*/
$g->topologicalSort();

заявка

Как я уже упоминал выше, этот алгоритм практически используется для сортировки выполнения различных задач, которые зависят друг от друга. Однако это не единственное его использование. Фактически любые виды объектов, которые зависят друг от друга, могут быть смоделированы с помощью графика. Действительно, иногда эти графы могут быть деревьями, но в большинстве случаев это не так.

Похожие сообщения:

1. Компьютерные алгоритмы: поиск по ширине графика
2. Компьютерные алгоритмы: поиск по глубине графика
3. Компьютерные алгоритмы: Graph Best-First Search
4. Компьютерные алгоритмы: графики и их представление
5. Компьютерные алгоритмы: Shell Sort