Уникальный путь в ориентированном графе

9

Я разрабатываю алгоритм для класса, который будет определять, является ли ориентированный граф уникальным по отношению к вершине , так что для любого существует не более одного пути от до . Я начал с использования BFS (поиск в ширину), чтобы найти кратчайший путь от v до другой вершины u, а затем снова запустил BFS, чтобы проверить, можно ли найти альтернативный путь от v до u. Я думаю, что это слишком много времени, однако. Есть ли у кого-нибудь подсказки относительно того, как можно найти решение за более короткое время выполнения?vuvvu

Юхо
источник

Ответы:

9

Используйте BFS, чтобы работать в обратном направлении от v, помечая каждую вершину как «посещенную» на ходу. Если вы когда-нибудь попадете в вершину, которую посещали ранее, у вашего графа нет свойства уникальности. В противном случае это так.


источник
2

Это простая модификация любого обхода графа: если вы найдете ребро ранее помеченного узла, у вас будет несколько путей.


источник