S_N>Задача состоит в поиске всевозможных путей в циклическом графе от A до B. S_N>Заранее благодарю за помощь
Если всё-таки речь идет об ациклическом орграфе, то можно начать с вершины A и поиском в ширину/глубину пометить все вершины, достижимые из A. Потом, начиная из B, идем из текущей вершины по обратным ребрам во все вершины, достижимые из A. Так перебираем все пути (только в обратном порядке обхода), причем, очевидно, различные, и только их.
Здравствуйте, S_Nawa, Вы писали:
S_N>Задача состоит в поиске всевозможных путей в циклическом графе от A до B. S_N>Заранее благодарю за помощь
С трудом себе представляю это в _циклическом_ графе. А в ациклическом — поиск в ширину до победы ( пока на очередном шаге некуда прийти, или все пути пришли в B )
Здравствуйте, xtile, Вы писали:
X>Здравствуйте, S_Nawa, Вы писали:
S_N>>Задача состоит в поиске всевозможных путей в циклическом графе от A до B. S_N>>Заранее благодарю за помощь
X>С трудом себе представляю это в _циклическом_ графе. А в ациклическом — поиск в ширину до победы ( пока на очередном шаге некуда прийти, или все пути пришли в B )
Просто заводим массив с номерами вершин, которые мы уже достигли. И если следующая вершина уже была достигнута когда-либо — сравниваем два пути (подымаясь вверх по дереву) и оставляем лишь более оптимальный.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Если программист в рабочее время играет, значит —
либо у него мало работы и большая зарплата,
либо у него много работы и маленькая зарплата.
Здравствуйте, twisted_mind, Вы писали:
S_N>>Задача состоит в поиске всевозможных путей в циклическом графе от A до B. S_N>>Заранее благодарю за помощь
_>Если всё-таки речь идет об ациклическом орграфе, то можно начать с вершины A и поиском в ширину/глубину пометить все вершины, достижимые из A. Потом, начиная из B, идем из текущей вершины по обратным ребрам во все вершины, достижимые из A. Так перебираем все пути (только в обратном порядке обхода), причем, очевидно, различные, и только их.
В ациклическом (дереве) путь, очевидно, единственный, если существует.
Здравствуйте, S_Nawa, Вы писали:
S_N>Задача состоит в поиске всевозможных путей в циклическом графе от A до B. S_N>Заранее благодарю за помощь
Возможно только при наложении ограничений на количество проходов по одной дуге/одной вержине.
Просто идешь рекурсивно из старта, каждый раз перебирая все возможные выходы из вершины.
+ заводишь массивы счетчиков прохождений для дуг/вершин.
