Pero si queremos atravesar un gráfico dirigido, deberíamos usar la clasificación topológica en lugar de DFS, ¿verdad? Por ejemplo, 1-> 2 no es lo mismo que 2-> 1 (con DFS es lo mismo).
Sí y no, no es lo mismo en la forma en que lo interpretas. Pero es lo mismo para DFS: cuando DFS está actualmente en el nodo 2, verificará a todos los vecinos, es decir, verá que hay un borde 2-> 1 e intentará visitar el nodo 1, pero no lo hará. importa el hecho de que en el gráfico no dirigido también debe existir el borde 1-> 2 (porque es lo mismo que 2-> 1) mientras que en el modo dirigido puede o no. Solo verificará el borde 2-> 1 que está allí y listo.
Ahora, cuando usa DFS para cualquier propósito práctico, es posible que desee que su DFS se implemente un poco diferente en ambos casos, porque interpreta el significado de “borde” de manera diferente en el gráfico dirigido y no dirigido. Para el ejemplo más simple, si usa DFS para tratar de encontrar si un gráfico tiene ciclos, en el gráfico dirigido simplemente dirá que si DFS alguna vez quiere intentar entrar en un vértice que ya ha visitado, ha encontrado un ciclo. Sin embargo, en el gráfico no dirigido, si ha caminado a través del borde 2-> 1, entonces ahora debe ignorar a propósito el borde 1-> 2 y no decir que hay un ciclo solo porque ha encontrado que el borde 1-> 2 va a Un vértice visitado número 2.
- ¿Cómo se mejora un algoritmo de aprendizaje automático basado en la experiencia?
- ¿Qué cosas debes saber antes de aprender algoritmos?
- ¿Qué debo hacer después de aprender Java central y resolver problemas de algoritmos y estructura de datos en HackerRank, CodeChef, etc.?
- ¿Cuál es la necesidad de determinar la complejidad temporal de un algoritmo o código?
- ¿Cuáles son los algoritmos de optimización más simples y fundamentales?
En otras palabras, DFS no es un algoritmo que usará en la misma forma docenas de veces. DFS es un boceto de un algoritmo al que puede agregar algo para obtener docenas de cosas diferentes que desea en este momento. Y al boceto en sí no le importa si el gráfico está dirigido o no: un borde 1 2 podría ser dos bordes 1-> 2 y 2-> 1. Pero tiene razón cuando comienza a agregar diferentes propósitos al boceto DFS, luego, en muchos casos, debe marcar la diferencia para el gráfico dirigido y no dirigido. A menudo, esta diferencia puede ser tan pequeña como (como en el ejemplo anterior) nunca usar un borde al vértice desde el cual llegamos directamente a donde estamos ahora [al final, para muchos casos esta adición es justo lo que puede llamar una respuesta preguntarse “cuál es la diferencia entre el recorrido de gráficos dirigidos y no dirigidos”], pero podría ser algo más si fuera necesario.
PD. La clasificación topológica es algo completamente diferente, y puede lograrlo usando DFS con las adiciones apropiadas, pero esa no es una “alternativa” a DFS.
