bfsearch

Busca em largura: nós na ordem em que são descobertos, por distância em número de arestas.

Categoria: Mathematics > Graph and Network Algorithms

Sintaxe

v = bfsearch(G, s)

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

Descrição

A busca visita s, depois todos os seus vizinhos, depois todos os vizinhos ainda não visitados deles, e assim por diante, uma camada de cada vez. Dentro de uma camada, os vizinhos são tomados em ordem de índice. Nós que não podem ser alcançados a partir de s não aparecem.

As camadas dão o número mínimo de arestas de s até cada nó, o que faz da busca em largura a ferramenta para caminhos mínimos sem pesos. Para caminhos com pesos use shortestpath.

Argumentos de entrada

G

Um graph ou digraph.

s

Nó inicial, como índice ou nome.

events

Nome de evento que escolhe o que é informado. 'edgetonew' dá as arestas da árvore.

Argumentos de saída

v

Vetor coluna de índices de nós, começando por s.

E

Matriz com duas colunas na forma 'edgetonew'.

Exemplo

Ordem e arestas da árvore

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

ans = 1×5

     1     2     3     4     5
ans = 4×2

     1     2
     1     3
     2     4
     4     5

Observações

O MatLivre retorna listas simples de nós para 'allevents' e outros nomes de evento, 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

dfsearch shortestpath conncomp neighbors