Выполните топологический сортировку ориентированного ациклического графика
order
=
graphtopoorder(G
)
G | N-на-N разреженная матрица, которая представляет направленный ациклический график. Ненулевые значения в матричных G указать наличие ребра. |
Совет
Для получения вводной информации о функциях теории графиков, см. «Функции теории графиков».
возвращает вектор индекса с порядком узлов, отсортированных топологически. В топологическом порядке ребро может существовать между исходным узлом order
=
graphtopoorder(G
)u
и узел назначения v
, если и только если u
появляется перед v
в векторном order
. G
является N-на-N разреженной матрицей, которая представляет направленный ациклический график (DAG). Ненулевые значения в матричных G
указать наличие ребра.
Создайте и просмотрите ориентированный ациклический график (DAG) с шестью узлами и восемью ребрами.
DG = sparse([6 6 6 2 2 3 5 1],[2 5 1 3 4 5 1 4],true,6,6) DG = (5,1) 1 (6,1) 1 (6,2) 1 (2,3) 1 (1,4) 1 (2,4) 1 (3,5) 1 (6,5) 1 view(biograph(DG))
Найдите топологический порядок ДАГ.
order = graphtopoorder(DG) order = 6 2 3 5 1 4
Транспозиция узлов так, чтобы они появились в порядке упорядочения в отображение графа.
DG = DG(order,order) DG = (1,2) 1 (2,3) 1 (1,4) 1 (3,4) 1 (1,5) 1 (4,5) 1 (2,6) 1 (5,6) 1 view(biograph(DG))
[1] Siek, J.G., Lee, L-Q, and Lumsdaine, A. (2002). Руководство пользователя библиотеки График (Upper Saddle River, NJ: Pearson Education).
graphallshortestpaths
| graphconncomp
| graphisdag
| graphisomorphism
| graphisspantree
| graphmaxflow
| graphminspantree
| graphpred2path
| graphshortestpath
| graphtraverse
| topoorder