`dfsearch`

Busca em profundidade: nós na ordem em que um percurso em profundidade os descobre.

Categoria: Mathematics > Graph and Network Algorithms

Sintaxe

v = dfsearch(G, s)

Retorna os nós alcançáveis a partir de s em ordem de profundidade.

E = dfsearch(G, s, 'edgetonew')

Retorna as arestas que levam a nós recém-descobertos.

Descrição

A busca segue um caminho até onde ele vai e depois volta ao nó mais recente que ainda tem um vizinho não visitado, continuando dali. Os vizinhos são tentados em ordem de índice. Apenas nós alcançáveis a partir de s são retornados.

A busca em profundidade está na base da ordenação topológica, da detecção de ciclos e do cálculo de componentes fortemente conexos.

Argumentos de entrada

G: Um graph ou digraph.
s: Nó inicial, como índice ou nome.
events: Nome de evento que escolhe o que é informado, como 'edgetonew'.

Argumentos de saída

v: Vetor coluna de índices de nós, começando por s.
E: Matriz de duas colunas na forma 'edgetonew'.

Exemplo

Ordem em profundidade

D = digraph([1 1 2 3 4], [2 3 4 4 5]);
dfsearch(D, 1)'
dfsearch(D, 1, 'edgetonew')

Saída

ans = 1×5

     1     2     4     5     3
ans = 4×2

     1     2
     2     4
     4     5
     1     3

Observações

O MatLivre retorna listas simples de nós para nomes de evento como 'allevents', em vez da tabela de eventos que o MATLAB monta. Use a forma padrão e 'edgetonew' para código portável.

Veja também

bfsearch conncomp isdag hascycles