Graph::topSort
Топологическая сортировка вершин
Блокноты MuPAD® будут демонтированы в будущем релизе. Используйте live скрипты MATLAB® вместо этого.
Live скрипты MATLAB поддерживают большую часть функциональности MuPAD, хотя существуют некоторые различия. Для получения дополнительной информации смотрите, Преобразуют Notebook MuPAD в Live скрипты MATLAB.
Синтаксис
Graph::topSort(G)
Описание
Graph::topSort(G) вычисляет топологическую сортировку графика G, т.е. нумерация T вершин, таких, что T i <T j каждый раз, когда существует ребро [i, j] в графике. Одна вершины расположены вначале.
Graph::topSort возвращает список, содержащий две таблицы. Первая таблица содержит упорядоченное расположение вершин. Вторая таблица показывает предшественников каждой вершины. Если несколько вершин u, i предшествует вершине v, первая вершина в упорядоченном расположении u i, являются предшественником v. Если никакой предшественник не будет существовать, значением будет infinity.
Примечание
Если G содержит любой цикл затем, топологическая сортировка не существует и вызов Graph::topSort результаты по ошибке.
Примеры
Пример 1
График "бабочки", который анализируется в трех строго связанных компонентах:
G1 := Graph([a, b, c, d, e, f],
[[a, b], [a, c], [a, d], [c, e], [d, e]],
Directed):
Graph::topSort(G1)
Первая таблица показывает упорядоченное расположение вершин. Левая сторона содержит порядок для каждой вершины, тогда как правая сторона содержит имя вершины. Вторая таблица показывает предшественников каждой вершины. Если никакой предшественник не существует, правая сторона содержит infinity. В противном случае правая сторона содержит вершину, которая является прямым предшественником вершины на левой стороне. Чтобы видеть, как график выглядит, графическое изображение помогает:
plot(Graph::plotGridGraph(G1,
VertexOrder = [None, b, f,
a, c, None,
None, None, e,
None, d, None],
VerticesPerLine=3))
Параметры
|
График |
Возвращаемые значения
Перечислите содержащий две таблицы.