Алгоритмы теории диаграмм

Question

Я работаю над тем, чтобы получить все возможные пути, начиная с узла «А» и заканчивая на том же узле. График - ориентированный граф (каждый узел соединен, по меньшей мере, с одним узлом).

Ограничения: я могу посетить узел ровно один раз, за ​​исключением, (конечно, стартового узла).

Проблема: Я попытался реализовать это, используя функцию графаграфа в MATLAB, но это дает мне только один такой способ. Любой алгоритм или логика, которые могут быть реализованы в C, java, будут работать.

Я был бы рад, если кто-то может дать мне какие-либо указания на него.

Примечание: я не хочу кратчайший путь, я хочу набор возможных путей.

Answer 1

Не знаю свой уровень, но boost библиотека очень хорошо, если вы можете получить его правильно настроены

Answer 2

Почему бы не написать свою собственную рекурсивную функцию?

findPath(Node start, Node end, List<Node> alreadyVisited) 
    for (Node neighbor: other ends of outgoing edges from start) { 
     if (neighbor == end) 
      display("Found a path: " + alreadyVisited + end) 
     else if (neighbor not in alreadyVisited) 
      findPath(neighbor, end, alreadyVisited + neighbor) 
    } 

... или что-то подобное. Поскольку вы ищете циклы, начальный вызов должен иметь то же значение, которое передается start и end. Конечно, если вывод в приглашение недостаточен, вам нужно собрать правильные пути в глобальном массиве или найти более элегантный способ их возврата.

Кроме того, выполнение двунаправленного поиска (одновременное слежение за входящими краями и проверка пересечения узлов, достигнутых последовательными исходящими краями и последовательными входящими ребрами, а не только достижение желаемой конечной точки) должны быть более быстрыми для больших графиков.