В настоящее время я сталкиваюсь с проблемой, пытаясь сделать так, чтобы при первом поиске по глубине не было найдено всех ребер в данном графике, удовлетворяющих следующим ограничениям:
- Ориентированный граф G = (V, E)
- Начальная вершина s ∈ V
- Множество ребер дерева ET ⊆ E такое, что для каждой вершины v ∈ V
единственный путь в графе (V, ET) от s до v является кратчайшим путем в G
- Множество ребер ET не может быть получено с помощью поиска в глубину
на G, независимо от того, как упорядочены вершины в каждом списке смежности.
Проблема, с которой я сталкиваюсь при решении этой головоломки, заключается в том, что мне кажется, что если s (наша начальная вершина) должна быть соединена с любой другой вершиной (для того чтобы s - v был кратчайшим путем), то DFS всегда будет найти каждый край.
Кто-нибудь может увидеть, чего мне не хватает? Любые примеры будут оценены!