toposort

Топологический порядок направленного графа без петель

свернуть все на странице

Синтаксис

n = toposort(G)
n = toposort(G,'Order',algorithm)
[n,H] = toposort(___)

Описание

пример

n = toposort(G) возвращает топологический порядок узлов в G таким образом, что i < j для каждого ребра (n(i),n(j)) в G. Ориентированный граф G не может иметь никаких циклов.

пример

n = toposort(G,'Order',algorithm) задает алгоритм упорядоченного расположения. Например, toposort(G,'Order','stable') использует устойчивый алгоритм упорядоченного расположения на основе лексикографического порядка узлов.

пример

[n,H] = toposort(___) дополнительно возвращает ориентированного графа H чьи узлы находятся в данном топологическом распоряжении. Можно использовать любую из комбинаций входных аргументов в предыдущих синтаксисах.

Примеры

свернуть все

Скрипт Open Live Script

Создайте и постройте график, который представляет прогрессию курсов Математики университетского уровня. Ребро между двумя курсами показывает требование курса.

A = [0 1 1 0 0 0 0
     0 0 0 1 0 0 0
     0 1 0 1 0 0 1
     0 0 0 0 1 1 0
     0 0 0 0 0 0 0
     0 0 0 0 1 0 0
     0 0 0 0 1 0 0];
names = {'Calculus I','Linear Algebra','Calculus II', ...
    'Multivariate Calculus','Topology', ...
    'Differential Equations','Real Analysis'};
G = digraph(A,names);
plot(G)

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

N = toposort(G)
N = 1×7

     1     3     7     2     4     6     5


G.Nodes.Name(N,:)
ans = 7x1 cell
    {'Calculus I'            }
    {'Calculus II'           }
    {'Real Analysis'         }
    {'Linear Algebra'        }
    {'Multivariate Calculus' }
    {'Differential Equations'}
    {'Topology'              }
Скрипт Open Live Script

Создайте ориентированного графа с помощью логической матрицы смежности, и затем постройте график.

rng default;
A = tril(sprand(10, 10, 0.3), -1)~=0;
G = digraph(A);
[~,G] = toposort(G);
plot(G)

Найдите топологическую сортировку вершин графика. Даже при том, что G уже находится в топологическом порядке, (1 2 3 4 5 6 7 8 9 10)toposort переупорядочивает узлы.

toposort(G)
ans = 1×10

     2     1     4    10     9     8     5     7     3     6

Задайте Order как 'stable' использовать устойчивый алгоритм упорядоченного расположения, так, чтобы порядки сортировки узлы с меньшими индексами сначала. Устойчивая сортировка не перестраивает G если это уже находится в топологическом порядке.

toposort(G,'Order','stable')
ans = 1×10

     1     2     3     4     5     6     7     8     9    10

Входные параметры

свернуть все

Введите график в виде digraph объект. G должен быть направленный граф без петель. Использование isdag подтвердить тот G не содержит циклы.

Использование digraph создать ориентированного графа.

Пример: G = digraph([1 2],[2 3])

Упорядоченное расположение алгоритма в виде 'fast' или 'stable':

'fast' (значение по умолчанию)

На основе поиска в глубину. Узел добавляется к началу списка после рассмотрения всех его потомков.

Если G уже находится в топологическом порядке, этот метод может все еще переупорядочить узлы.

'stable'

На основе лексикографического порядка. n(1) узел с самым маленьким индексом, n(2) следующий самый маленький данный n(1), и так далее.

Если G находится в топологическом порядке затем H неизменно и n 1:numnodes(G).

Пример: [n,H] = toposort(G,'Order','stable')

Выходные аргументы

свернуть все

Индексы узла, возвращенные как вектор-строка.

Топологически отсортированный график, возвращенный как digraph объект. H тот же график как G, но переупорядочили узлы согласно n.

Больше о

свернуть все

Топологический порядок

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

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

Смотрите также

| |

Введенный в R2015b

Документация MATLAB

Поддержка

Для просмотра документации необходимо авторизоваться на сайте