Campus Livre
toposort
Ordem topológica dos nós de um grafo direcionado acíclico.
Categoria: Mathematics > Graph and Network Algorithms
Sintaxe
N = toposort(G)Retorna os índices dos nós do digraph G em uma ordem na qual toda aresta vai de um nó anterior para um posterior.
Descrição
Uma ordem topológica lista os nós de modo que, para cada aresta u -> v, o nó u apareça antes de v. Ela só existe quando o grafo não tem ciclo direcionado, e é usada, por exemplo, para ordenar tarefas que dependem umas das outras.
Normalmente há várias ordens válidas; toposort retorna uma delas. Se o grafo tiver um ciclo, a função gera um erro.
Argumentos de entrada
G- Um objeto
digraph. Não pode ter ciclos direcionados.
Argumentos de saída
N- Vetor linha com os índices dos nós em ordem topológica.
Exemplo
Ordenando um pequeno grafo de dependências
G = digraph([1 1 2 3], [2 3 4 4]);
N = toposort(G)Saída
N = 1×4
1 3 2 4