En un primer árbol de profundidad, los bordes definen el árbol (es decir, los bordes que se usaron en el transversal).
Hay algunos bordes sobrantes que conectan algunos de los otros nodos. ¿Cuál es la diferencia entre un borde transversal y un borde delantero?
De wikipedia:
Según este árbol de expansión, los bordes del gráfico original se puede dividir en tres clases: bordes delanteros, que apuntan desde un nodo del árbol a uno de sus descendientes, bordes posteriores, que apuntan desde un nodo a uno de sus antepasados, y bordes transversales, que no lo hacen. A veces, los bordes de los árboles, los bordes que pertenecen al árbol de expansión en sí, se clasifican por separado de los bordes delanteros. Si el gráfico original no está dirigido, entonces todos sus bordes son bordes de árbol o bordes posteriores.
No es un borde que no se use en el recorrido que los puntos de un nodo a otro establecen una relación padre-hijo?
Comentarios
- Relacionado: cs.stackexchange.com/questions/99988/… busca establecer un algoritmo que, para gráficos dirigidos, preferirá hacer bordes hacia adelante, en lugar de bordes cruzados, durante búsqueda en profundidad.
Respuesta
Wikipedia tiene la respuesta:
Todos los tipos de bordes aparecen en esta imagen. Trace DFS en este gráfico (los nodos se exploran en orden numérico) y vea dónde la intuición falla.
Esto explicará el diagrama: –
Borde hacia adelante: (u, v), donde v es un descendiente de u, pero no un borde de árbol .Es un borde sin árbol que conecta un vértice con un descendiente en un árbol DFS.
Borde transversal: cualquier otro borde. Puede ir entre vértices en el mismo árbol en profundidad o en diferentes árboles en profundidad. (lego)
Es cualquier otra arista en el gráfico G. Conecta vértices en dos árboles DFS diferentes o dos vértices en el mismo árbol DFS ninguno de los cuales es el antepasado del otro. (formal)
Comentarios
- ¿Por qué no es imposible que 6 se haya atravesado primero (primero el lado derecho)? Si eso hubiera sucedido, ¿cómo se habría llamado al borde 2- > 3?
- @soandos, le sugiero que se tome el tiempo para rastrear el algoritmo. Suponiendo que los wikipedistas ‘ no cometieron un error, la imagen describe una ejecución genuina de DFS en este gráfico, por lo que hay una manera de ajustar el algoritmo en este rastro. Los tipos de bordes se describen con bastante claridad en Wikipedia, y también puede consultar este ejemplo.
- Entiendo que esta es una forma válida de hacer un DFS. Simplemente pregunto qué pasaría si se hiciera al revés.
- Entonces los resultados serían diferentes. Lo ‘ lo siento, ‘ tendrías que resolverlo tú mismo.
- @soandos En general, hay muy bien pueden ser múltiples recorridos DFS. Las nociones utilizadas aquí son relativas a un recorrido dado y diferirán para recorridos múltiples.
Respuesta
Un recorrido DFS en un gráfico no dirigido no dejará un borde transversal, ya que se exploran todos los bordes que inciden en un vértice.
Sin embargo, en un gráfico dirigido, es posible que se encuentre con un borde que conduce a un vértice que se ha descubierto antes, de modo que ese vértice no es un antepasado o descendiente del vértice actual. Tal borde se llama borde cruzado.
Comentarios
- Aporov, Gracias por la respuesta. Todavía me parece que cuando llegas al vértice 6 en el DFS como se muestra en el diagrama de Wikipedia, tienes tres bordes para atravesar desde 6. En ese punto, el vértice 6 es » actual «. Eventualmente, atravesará el borde hasta el vértice 3. Aunque ya se ha visitado 3, sin embargo, dado que hay un borde de 6 a 3, entonces 3 es un descendiente de la » actual » vértice 6. Si es así, viola la definición de borde transversal. Debe haber algo más en la definición que no ‘ t se haga muy explícita.
- De hecho, DFS solo contiene los bordes del árbol para los bordes posteriores (Introducción a Algoritmos Thm. 22.10).
Respuesta
En un recorrido DFS, los nodos se terminan una vez que todos sus hijos están finalizado. Si marca las horas de descubrimiento y finalización de cada nodo durante el recorrido, puede comprobar si un nodo es descendiente comparando las horas de inicio y finalización. De hecho, cualquier recorrido DFS dividirá sus bordes de acuerdo con la siguiente regla.
Sea d [nodo] el tiempo de descubrimiento del nodo, del mismo modo sea f [nodo] el tiempo de finalización.
Teorema de paréntesis Para todo u, v, se cumple exactamente una de las siguientes:
1.d [u] < f [u] < d [v] < f [ v] o d [v] < f [v] < d [u] < f [u] y ninguno de u y v es descendiente del otro.
d [u] < d [v] < f [v] < f [u] y v es descendiente de u.
d [v] < d [u] < f [u] < f [v] yu es descendiente de v.
Entonces, d [u] < d [v] < f [u] < f [v] no puede suceder.
Me gusta paréntesis: () [], ([]) y [()] están bien, pero ([)] y [(]) no están bien.
Por ejemplo, considere el gráfico con bordes:
A -> B
A -> C
B -> C
Sea el orden de visita representado por una cadena de etiquetas de nodos, donde «ABCCBA» significa A -> B -> C (terminado) B (terminado) A (terminado), similar a ((())).
Entonces «ACCBBA» podría ser un modelo para «(() ())».
Ejemplos:
«CCABBA»: Entonces A -> C es una cruz borde, ya que CC no está dentro de A.
«ABCCBA»: Entonces A -> C es un borde delantero (descendiente indirecto).
«ACCBBA»: Entonces A -> C es un borde de árbol (descendiente directo).
Fuentes:
CLRS:
https://mitpress.mit.edu/books/introduction-algorithms
Notas Lecure http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm