Graph recorridos
Graph recorrido significa visitar cada vértice y borde exactamente una vez en un pozo -orden definido. Al usar ciertos algoritmos de gráficos, debe asegurarse de que cada vértice del gráfico se visite exactamente una vez. El orden en que se visitan los vértices es importante y puede depender del algoritmo o pregunta que esté resolviendo.
Durante un recorrido, es importante que realice un seguimiento de los vértices que se han visitado. La forma más común de rastrear vértices es marcarlos.
Breadth First Search (BFS)
Hay muchas formas de recorrer gráficos. BFS es el enfoque más utilizado.
BFS es un algoritmo de desplazamiento en el que debe empezar a desplazarse desde un nodo seleccionado (nodo de origen o de inicio) y atravesar el gráfico por capas, explorando así los nodos vecinos (nodos que están directamente conectados al nodo de origen). Luego debe moverse hacia los nodos vecinos del siguiente nivel.
Como sugiere el nombre BFS, debe recorrer el gráfico a lo ancho de la siguiente manera:
- Primero muévase horizontalmente y visitar todos los nodos de la capa actual
- Mover a la siguiente capa
Considere el siguiente diagrama. 
La distancia entre los nodos en la capa 1 es comparativamente menor que la distancia entre los nodos en la capa 2. Por lo tanto, en BFS, debe atravesar todos los nodos en la capa 1 antes de pasar a los nodos en la capa 2.
Atravesando nodos secundarios
Un gráfico puede contener ciclos, lo que puede llevarlo al mismo nodo nuevamente mientras recorre el gráfico. Para evitar el procesamiento del mismo nodo nuevamente, use una matriz booleana que marca el nodo después de que se procesa. Mientras visita los nodos en la capa de un gráfico, guárdelos de manera que pueda atravesar los nodos secundarios correspondientes en un orden similar.
Para facilitar este proceso, utilice una cola para almacenar el nodo y márquelo como «visitado» hasta que todos sus vecinos (vértices que están directamente conectados a él) estén marcados. La cola sigue el método de puesta en cola First In First Out (FIFO) y, por lo tanto, los vecinos del nodo se visitarán en el orden en que se insertaron en el nodo, es decir, el nodo que se insertó primero se visitará primero, por lo que en.
Pseudocódigo
Proceso de desplazamiento 
El proceso de desplazamiento comenzará desde el nodo de origen y enviará s en la cola. s se marcarán como «visitados».
La primera iteración
- s se sacarán de la cola
- Se atravesarán los vecinos de s ie 1 y 2
- 1 y 2, que no se han atravesado anteriormente, se atraviesan. Serán:
- Puestos en la cola
- 1 y 2 se marcarán como visitados
Segunda iteración
- Se saca 1 de la cola
- Vecinos de 1 ie sy 3 se atraviesan
- s se ignora porque está marcado como «visitado»
- 3, que no se ha atravesado anteriormente, se atraviesa. Es:
- Insertado en la cola
- Marcado como visitado
Tercera iteración
- 2 se extrae de la cola
- Vecinos de 2, es decir, 3 y 4 se atraviesan
- 3 y s se ignoran porque están marcados como «visitados»
- 4, que no se ha atravesado anteriormente, se atraviesa. Es:
- Insertado en la cola
- Marcado como visitado
Cuarta iteración
- Se saca 3 de la cola
- Vecinos de 3, es decir, 1, 2 y 5 se atraviesan
- 1 y 2 se ignoran porque están marcados como «visitados»
- 5, que no se ha atravesado anteriormente, se atraviesa. Es:
- Insertado en la cola
- Marcado como visitado
Quinta iteración
- 4 saldrán de la cola
- Vecinos de 4, es decir, 2 se atraviesan
- 2 se ignora porque ya está marcado como «visitado»
Sexta iteración
- 5 se extrae de la cola
- Vecinos de 5, es decir, 3 se atraviesa
- 3 se ignora porque es ya marcado como «visitado»
La cola está vacía y sale del ciclo. Todos los nodos se han atravesado utilizando BFS.
Si todos los bordes de un gráfico tienen el mismo peso, entonces BFS también se puede utilizar para encontrar la distancia mínima entre los nodos en un gráfico.
Ejemplo
Como en este diagrama, comience desde el nodo fuente, para encontrar la distancia entre la fuente nodo y nodo 1. Si no sigue el algoritmo BFS, puede pasar del nodo de origen al nodo 2 y luego al nodo 1. Este enfoque calculará la distancia entre el nodo de origen y el nodo 1 como 2, mientras que el mínimo la distancia es en realidad 1. La distancia mínima se puede calcular correctamente utilizando el algoritmo BFS.
Complejidad
La complejidad temporal de BFS es O (V + E), donde V es el número de nodos y E es el número de aristas.
Aplicaciones
1. ¿Cómo determinar el nivel de cada nodo en el árbol dado?
Como sabe en BFS, recorre los niveles. También puede utilizar BFS para determinar el nivel de cada nodo.
Implementación
Este código es similar al código BFS con solo la siguiente diferencia:
nivel] = nivel + 1;
En este código, mientras visita cada nodo, el nivel de ese nodo se establece con un incremento en el nivel de su nodo padre. Así es como se determina el nivel de cada nodo.
2 . 0-1 BFS
Este tipo de BFS se utiliza para encontrar la distancia más corta entre dos nodos en un gráfico, siempre que los bordes del gráfico tengan los pesos 0 o 1. Si aplica el BFS explicado anteriormente en este artículo, obtendrá un resultado incorrecto para la distancia óptima entre 2 nodos.
En este enfoque, una matriz booleana no se usa para marcar el nodo porque la condición de la distancia óptima se verificará cuando visite cada nodo. Se utiliza una cola de dos extremos para almacenar el nodo. En 0-1 BFS, si el peso del borde = 0, entonces el nodo se empuja al frente de la cola. Si el peso del borde = 1, entonces el nodo se empuja hacia la parte posterior de la cola.
Implementación
Q es una cola de dos extremos. La distancia es una matriz donde, la distancia contendrá la distancia desde el nodo inicial al nodo v. Inicialmente, la distancia definida desde el nodo de origen a cada nodo es infinita.
Comprendamos este código con el siguiente gráfico:
La lista de adyacencia del gráfico será la siguiente:
Aquí «s» se considera 0 o nodo fuente.
0 – > 1 – > 3 – > 2
bordes.primero = 1, bordes.segundo = 1
bordes.primero = 3, bordes.segundo = 0
bordes.primero = 2, bordes.segundo = 1
1 – > 0 – > 4
bordes.first = 0, bordes.segundo = 1
bordes.first = 4 , bordes.segundo = 0
2 – > 0 – > 3
bordes.first = 0 , bordes.segundo = 0
bordes.primero = 3, bordes.segundo = 0
3 – > 0 – > 2 – > 4
bordes.first = 0, bordes.segundo = 0
bordes.primero = 2, bordes.segundo = 0
bordes.first = 4, bordes.segundo = 0
4 – > 1 – > 3
bordes.primero = 1, bordes.segundo = 0
bordes.primero = 3, bordes.segundo = 0
Si usa el algoritmo BFS, el resultado será incorrecto porque le mostrará la distancia óptima entre s y el nodo 1 y sy el nodo 2 como 1 respectivamente. Esto se debe a que visita a los hijos de sy calcula la distancia entre sy sus hijos, que es 1. La distancia óptima real es 0 en ambos casos.
Procesando
Comenzando desde el nodo de origen, es decir, 0, se moverá hacia 1, 2 y 3. Dado que el peso del borde entre 0 y 1 y 0 y 2 es 1 respectivamente , 1 y 2 se colocarán al final de la cola. Sin embargo, dado que el peso del borde entre 0 y 3 es 0, 3 se colocará al frente de la cola. La distancia se mantendrá en la matriz de distancias en consecuencia.
Luego se sacarán 3 de la cola y se aplicará el mismo proceso a sus vecinos, y así sucesivamente.