Ruta única en un gráfico dirigido

9

Estoy diseñando un algoritmo para una clase que determinará si un gráfico dirigido es único con respecto a un vértice tal manera que para cualquier haya como máximo una ruta de a . Comencé usando BFS (búsqueda de amplitud) para encontrar la ruta más corta de v a otro vértice u, y luego ejecuté BFS nuevamente para ver si se puede encontrar una ruta alternativa de v a u. Sin embargo, creo que esto lleva demasiado tiempo. ¿Alguien tiene alguna pista sobre cómo se puede encontrar la solución con un tiempo de ejecución más corto?vtuvvtu

Juho
fuente

Respuestas:

9

Use BFS para trabajar hacia atrás desde v, marcando cada vértice como 'visitado' a medida que avanza. Si alguna vez golpeó un vértice que visitó anteriormente, su gráfico no tiene la propiedad de unicidad. De lo contrario, lo hace.


fuente
2

Es una modificación simple de cualquier recorrido del gráfico: si encuentra un borde a un nodo previamente marcado, entonces tiene múltiples rutas.


fuente