Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #1 (permalink)  
Старый 18.10.2017, 19:13
Новичок на форуме
Отправить личное сообщение для deniv Посмотреть профиль Найти все сообщения от deniv
 
Регистрация: 18.10.2017
Сообщений: 1

Поиск всех путей в ориентированном ацикличном графе
Всем привет!

Прошу помочь с реализацией алгоритма.

Собственно и сама задача:

Как обойти граф имея список смежных вершин, вида:
1: 2,3,4
2: 5,6
3: 7
4: 8,9
5: 10

Чтобы на выходе получить массив всех путей из вершин (1,2,3,4,5...) списка смежности вида:

[[1,2,5,10],
[1,2,6],
[1,3,7],
....
[2,5,10]
....
]

Путь считается законченным, если у вершины нет смежных вершин)

Заранее благодарю всех за подсказку или за пример реализации.

Для реализации пробовал алгоритм обхода в ширину, но что то не могу до конца правильно реализовать...
Ответить с цитированием
  #2 (permalink)  
Старый 18.10.2017, 20:17
Аватар для Alexandroppolus
Профессор
Отправить личное сообщение для Alexandroppolus Посмотреть профиль Найти все сообщения от Alexandroppolus
 
Регистрация: 25.10.2016
Сообщений: 1,002

Сообщение от deniv
Для реализации пробовал алгоритм обхода в ширину
граф ориентированный ациклический, тут всё проще - не надо запоминать что уже было. Да и обход скорее в глубину.

https://jsfiddle.net/hr6d537o/
результат в консольке - массив путей, в каждом из которых по крайней мере 2 вершины.
Ответить с цитированием
Ответ



Опции темы Искать в теме
Искать в теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Удаление всех   из текста (поиск и удаление любого слова из текста) Stenli jQuery 5 28.06.2017 20:47
Поиск всех родительских "iframe". JS/jQuery Alex241 jQuery 0 29.01.2016 01:18
Сделать класс активным для всех путей URL eXTrEMe888 jQuery 13 20.08.2014 13:58