El propósito del nodo gris en la búsqueda de profundidad en el gráfico

18

En muchas implementaciones de búsqueda de profundidad primero que vi (por ejemplo: aquí ), el código distingue entre un vértice gris (descubierto, pero no todos sus vecinos fueron visitados) y un vértice negro (descubierto y todos sus vecinos fueron visitados) . ¿Cuál es el propósito de esta distinción? Parece que el algoritmo DFS nunca visitará un vértice visitado independientemente de si es gris o negro.

usuario6805
fuente

Respuestas:

25

Al hacer un DFS, cualquier nodo se encuentra en uno de los tres estados: antes de ser visitado, durante la visita recursiva a sus descendientes y después de que todos sus descendientes hayan sido visitados (regresando a su padre, es decir, la fase de cierre). Los tres colores corresponden a cada uno de los tres estados. Una de las razones para mencionar los colores y el momento de la visita y el regreso es hacer explícitamente estas distinciones para una mejor comprensión.

Por supuesto, hay usos reales de estos colores. Considere un grafo dirigido . Suponga que desea verificar G para la existencia de ciclos. En un gráfico no dirigido, si el nodo en consideración tiene un vecino negro o gris, indica un ciclo (y el DFS no lo visita como usted menciona). Sin embargo, en el caso de un gráfico dirigido , un vecino negro no significa un ciclo. Por ejemplo, considere un gráfico con 3 vértices - A , B , y C , con bordes dirigidos como A B , B C , A C . Supongamos que el DFS comienza en AsolsolUN,si,CUNsisiCUNCUN, A continuación, visitas , luego C . Cuando ha regresado a A , verifica que C ya haya sido visitado y que esté negro. Pero no hay ciclo en el gráfico.siCUNC

En un gráfico dirigido, un ciclo está presente si y solo si se vuelve a ver un nodo antes de que todos sus descendientes hayan sido visitados. En otras palabras, si un nodo tiene un vecino que es gris, entonces hay un ciclo (y no cuando el vecino es negro). Un nodo gris significa que actualmente estamos explorando sus descendientes, y si uno de esos descendientes tiene una ventaja sobre este nodo gris, entonces hay un ciclo. Por lo tanto, para la detección de ciclos en gráficos dirigidos, debe tener 3 colores. También podría haber otros ejemplos, pero debes hacerte una idea.

Paresh
fuente
2
+1 buena explicación. Para un recorrido simple de todos los nodos en un gráfico no dirigido (como uno vinculado en el cuerpo de mi pregunta), ¿GRIS y NEGRO no tienen ninguna diferencia funcional?
user6805
1
@ user6805 Para un recorrido simple, visitando todos los nodos, del gráfico dirigido o no dirigido, no hay diferencia funcional entre gris y negro. Puede usar solo dos colores (o visitado / no visitado). Es para algoritmos más complejos que necesita colores.
Paresh
¡Lo entendí! OK, considere el siguiente caso: twitter.com/MaksimADmitriev/status/796995958043279361 Recorrimos los gráficos usando DFS. El gráfico de la izquierda es el mismo que el gráfico de esta respuesta, y no tiene ciclos. Recorramos el gráfico de la derecha que tiene un ciclo. Visitamos A y lo marcamos en gris. Visitamos B y lo marcamos en gris. Visitamos C y lo marcamos en gris. Ahora estamos a punto de visitar A, que ya está gris. Entonces, "de negro a negro" no significa que haya un ciclo, pero "de gris a gris" sí. Por eso necesitamos gris. Por favor, corrígeme si estoy equivocado
Maksim Dmitriev
Para propósitos aún más complejos, como encontrar componentes fuertemente conectados, es posible que sea necesario registrar dos veces para cada nodo: antes de la hora en que se encuentra un nodo por primera vez (es decir, la hora en que se colorea de gris) y después de la hora en que un nodo termina de visitar (es decir, la hora es de color negro). Para implementar grabaciones, se mantiene un contador, que aumenta a medida que ocurre cada evento.
Juan
2

Es un ejercicio en CLRS que puede eliminar el color gris o negro y el algoritmo funciona bien con solo dos colores, en otras palabras, no es realmente necesario. El objetivo principal de marcar vértices es asegurarse de que no nos encontremos con un bucle infinito visitando repetidamente vértices ya visitados.

La razón para usar 3 colores en el algoritmo DFS es principalmente pedagógica: es más clara desde el punto de vista conceptual, ayuda a los estudiantes a ver qué sucede durante la ejecución de cada nodo.

Kaveh
fuente
0

El vértice gris indica que ha visitado ese nodo y se ha movido a uno de sus vecinos en algún orden, pero puede haber más vértices vecinos a ese nodo. Si bien puede ser útil al retroceder para explorar vértices no visitados.

Digamos El vértice A tiene dos vecinos B y C y B tiene un vecino D .

comienza en el vértice A, que es de color blanco y lo hace gris y atraviesa a su vecino.

Digamos que al elegir el orden alfabético, visita el vértice B que está en color blanco y marca como gris.

Luego visita D de blanco -> gris D -> no más vecinos. por lo tanto marca D-> negro .

Ahora, retrocede a B en Gray y no más nieghbors. De ahí las marcas B-> negro .

Una vez más retrocede A en gris y visita la marca c en c-> Gris, no más vecinos marca C como negro

finalmente, vuelve a A y marca el vértice A como negro ya que no hay más vértices blancos y todo como negro.

NRK
fuente
No veo si la distinción entre gris y negro tiene algún propósito aquí ...
user6805
Eso es lo que tienes que entender. Si un vértice está marcado como negro, significa que no habrá vértices vecinos a ese vértice. Aquí el vértice D está marcado en negro ya que no hay vértices vecinos ... donde, como el gris sugiere, hay más vecinos para visitar y, por lo tanto, atraviesas esos.
NRK
Creo que le ahorra simplemente volver a visitar los nodos que sabe con certeza que no tienen bordes traseros (es decir, optimización)
Setheron
0

En DFS clasificamos las aristas como arista hacia adelante, arista posterior, arista cruzada y arista.

Usamos 3 colores para clasificar los bordes. y estos colores representan el estado del vértice, es decir, v. blanco: el vértice v aún no se ha descubierto.

gris: v ya se ha descubierto, pero todavía no se han descubierto todos los vértices a los que se puede acceder desde v. entonces el vértice v todavía está en la pila.

black: v ya está fuera de stack.discovered y terminado.

Al hacer el DFS si encuentra un vértice gris a través del borde e, entonces es un borde posterior. Si encuentra un vértice negro a través del borde e, entonces es un borde transversal / borde delantero. Si encuentra un vértice blanco, llamará a DFS de forma recursiva.

Neeraj Singh
fuente
OK, pero ¿cuál es el punto? Usted ha dicho que el blanco / gris / negro está relacionado con adelante / atrás / cruz / árbol, pero tampoco dice para qué sirven esas cosas. ¡Ahora hay siete cosas que el autor de la pregunta no entiende, en lugar de solo tres!
David Richerby
Estos bordes se pueden usar en diversas aplicaciones de DFS, como los bordes posteriores se usan para identificar bucles en un gráfico, los bordes delanteros y cruzados se usan para probar si existe una ruta única entre cada par de vértices.
Neeraj Singh