toposort
Топологический порядок направленного графа без петель
Описание
n = toposort(G)G таким образом, что i < j для каждого ребра (n(i),n(j)) в G. Ориентированный граф G не может иметь никаких циклов.
Примеры
Топологическая сортировка узлов
Создайте и постройте график, который представляет прогрессию курсов Математики университетского уровня. Ребро между двумя курсами показывает требование курса.
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' }
Стабильная топологическая сортировка
Создайте ориентированного графа с помощью логической матрицы смежности, и затем постройте график.
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 | isdag | reordernodes