Travessia do gráfico
Travessia do gráfico significa visitar cada vértice e aresta exatamente uma vez em um poço ordem definida. Ao usar certos algoritmos de gráfico, você deve garantir que cada vértice do gráfico seja visitado exatamente uma vez. A ordem em que os vértices são visitados é importante e pode depender do algoritmo ou questão que você está resolvendo.
Durante uma travessia, é importante que você rastreie quais vértices foram visitados. A maneira mais comum de rastrear vértices é marcá-los.
Pesquisa em amplitude (BFS)
Existem muitas maneiras de percorrer os gráficos. BFS é a abordagem mais comumente usada.
O BFS é um algoritmo de passagem onde você deve começar a fazer a passagem de um nó selecionado (nó de origem ou nó inicial) e atravessar o gráfico em camadas, explorando assim os nós vizinhos (nós que estão diretamente conectados ao nó de origem). Você deve, então, mover-se para os nós vizinhos do próximo nível.
Como o nome BFS sugere, você deve percorrer o gráfico em largura da seguinte forma:
- Primeiro mova horizontalmente e visite todos os nós da camada atual
- Mova para a próxima camada
Considere o seguinte diagrama. 
A distância entre os nós na camada 1 é comparativamente menor do que a distância entre os nós na camada 2. Portanto, no BFS, você deve atravessar todos os nós na camada 1 antes de mover para os nós na camada 2.
Percorrendo nós filhos
Um gráfico pode conter ciclos, que podem levá-lo ao mesmo nó novamente enquanto percorre o gráfico. Para evitar o processamento do mesmo nó novamente, use um array booleano que marca o nó após ele ser processado. Ao visitar os nós na camada de um gráfico, armazene-os de maneira que você possa atravessar os nós filhos correspondentes em uma ordem semelhante.
Para facilitar esse processo, use uma fila para armazenar o nó e marque-o como “visitado” até que todos os seus vizinhos (vértices que estão diretamente conectados a ele) sejam marcados. A fila segue o método de enfileiramento First In First Out (FIFO) e, portanto, os vizinhos do nó serão visitados na ordem em que foram inseridos no nó, ou seja, o nó que foi inserido primeiro será visitado primeiro, e assim sobre.
Pseudocódigo
Processo de cruzamento 
O cruzamento iniciará a partir do nó de origem e enviará s na fila. s serão marcados como “visitados”.
Primeira iteração
- s será retirado da fila
- Vizinhos de s, ou seja, 1 e 2 serão percorridos
- 1 e 2, que não foram percorridos anteriormente, são percorridos. Eles serão:
- Colocados na fila
- 1 e 2 serão marcados como visitados
Segunda iteração
- 1 é retirado da fila
- Vizinhos de 1, ou seja, se 3 são percorridos
- s é ignorado porque está marcado como “visitado”
- 3, que não foi percorrido anteriormente, é percorrido. É:
- Colocado na fila
- Marcado como visitado
Terceira iteração
- 2 é retirado da fila
- Vizinhos de 2, ou seja, s, 3 e 4 são atravessados
- 3 es são ignorados porque estão marcados como “visitados”
- 4, que não foi percorrido anteriormente, é percorrido. É:
- Colocado na fila
- Marcado como visitado
Quarta iteração
- 3 é retirado da fila
- vizinhos de 3, ou seja, 1, 2 e 5 são atravessados
- 1 e 2 são ignorados porque estão marcados como “visitados”
- 5, que não foi percorrido anteriormente, é percorrido. É:
- Colocado na fila
- Marcado como visitado
Quinta iteração
- 4 será retirado da fila
- vizinhos de 4, ou seja, 2 é atravessado
- 2 é ignorado porque já está marcado como “visitado”
Sexta iteração
- 5 é retirado da fila
- vizinhos de 5, ou seja, 3 é atravessado
- 3 é ignorado porque é já marcado como “visitado”
A fila está vazia e sai do loop. Todos os nós foram percorridos usando BFS.
Se todas as arestas em um gráfico tiverem o mesmo peso, então o BFS também pode ser usado para encontrar a distância mínima entre os nós em um gráfico.
Exemplo
Como neste diagrama, comece a partir do nó de origem, para encontrar a distância entre a fonte nó e nó 1. Se você não seguir o algoritmo BFS, você pode ir do nó de origem para o nó 2 e depois para o nó 1. Esta abordagem irá calcular a distância entre o nó de origem e o nó 1 como 2, enquanto o mínimo a distância é na verdade 1. A distância mínima pode ser calculada corretamente usando o algoritmo BFS.
Complexidade
A complexidade de tempo do BFS é O (V + E), onde V é o número de nós e E é o número de arestas.
Aplicativos
1. Como determinar o nível de cada nó na árvore dada?
Como você sabe no BFS, você atravessa o nível. Você também pode usar o BFS para determinar o nível de cada nó.
Implementação
Este código é semelhante ao código BFS com apenas a seguinte diferença:
nível] = nível + 1;
Neste código, enquanto você visita cada nó, o nível desse nó é definido com um incremento no nível de seu nó pai. É assim que o nível de cada nó é determinado.
2 . 0-1 BFS
Este tipo de BFS é usado para encontrar a distância mais curta entre dois nós em um gráfico, desde que as arestas do gráfico tenham os pesos 0 ou 1. Se você aplicar o BFS explicado anteriormente em neste artigo, você obterá um resultado incorreto para a distância ideal entre 2 nós.
Nesta abordagem, uma matriz booleana não é usada para marcar o nó porque a condição da distância ideal será verificada quando você visite cada nó. Uma fila dupla é usada para armazenar o nó. Em 0-1 BFS, se o peso da borda = 0, o nó é empurrado para a frente do desenfileiramento. Se o peso da aresta = 1, então o nó é empurrado para trás do desenfileiramento.
Implementação
Q é uma fila dupla. A distância é uma matriz onde distância irá conter a distância do nó inicial ao nó v. Inicialmente, a distância definida do nó de origem até cada nó é infinita.
Vamos entender este código com o seguinte gráfico:
A lista de adjacências do gráfico será a seguinte:
Aqui, “s” é considerado 0 ou nó de origem.
0 – > 1 – > 3 – > 2
bordas.first = 1, bordas.segundo = 1
bordas.first = 3, bordas.segundo = 0
bordas.first = 2, bordas.segundo = 1
1 – > 0 – > 4
bordas.first = 0, bordas.second = 1
bordas.first = 4 , bordas.second = 0
2 – > 0 – > 3
bordas.first = 0 , bordas.segundo = 0
bordas.first = 3, bordas.segundo = 0
3 – > 0 – > 2 – > 4
bordas.first = 0, bordas.second = 0
bordas.first = 2, bordas.segundo = 0
edge.first = 4, edge.second = 0
4 – > 1 – > 3
bordas.first = 1, bordas.segundo = 0
bordas.first = 3, bordas.segundo = 0
Se você usar o algoritmo BFS, o resultado será incorreto porque mostrará a você a distância ideal entre s e nó 1 es e nó 2 como 1, respectivamente. Isso ocorre porque ele visita os filhos de se calcula a distância entre s e seus filhos, que é 1. A distância ótima real é 0 em ambos os casos.
Processamento
Começando no nó de origem, ou seja, 0, ele se moverá em direção a 1, 2 e 3. Como o peso da aresta entre 0 e 1 e 0 e 2 é 1, respectivamente , 1 e 2 serão colocados no final da fila. No entanto, como a espessura da borda entre 0 e 3 é 0, 3 será empurrado para a frente da fila. A distância será mantida na matriz de distância de acordo.
3 serão então retirados da fila e o mesmo processo será aplicado aos seus vizinhos, e assim por diante.