DFS на эволюционирующих графах

Я думаю, что вполне уверен, что алгоритм DFS для проблемы не должен отличаться от обычного DFS, но просто хотел получить обратную связь от других. Вот моя проблема:

Я хотел бы выполнить поиск в глубину на графах, для которых я не знаю всех узлов. Когда я начинаю поиск, все, что я знаю, это только начальный узел. Основываясь на свойствах начального узла, я могу определить его набор дочерних узлов. Дочерние узлы, которые только что были обнаружены, могут быть дополнительно обнаружены, как описано выше.

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

Это разумный подход? Я что-то пропустил?


graph algorithm depth-first-search
person user1595789    schedule 21.03.2014    source источник
comment
Он будет работать, но имейте в виду, что он будет исследовать все узлы, доступные из одного из дочерних узлов, прежде чем продолжить работу со следующим дочерним узлом. Для бесконечных графов это может быть не то, что вам нужно. В этом случае вы можете использовать BFS или итеративное углубление DFS вместо этого   -  person Niklas B.    schedule 21.03.2014
comment
Это будет работать нормально. Ничто в алгоритме DFS не предполагает каких-либо знаний о графе, кроме текущего узла и его непосредственных соседей.   -  person chepner    schedule 24.03.2014
comment
Что вы хотите сделать, обходя граф с помощью DFS? Если вам нужен список вершин в графе, то применение обычного dfs будет работать, как описано в ответах. В то время как если вы хотите обнаружить все ребра, алгоритмы поиска в глубину, описанные ниже, не будут работать. Это связано с тем, что после того, как вы завершили поиск в глубину из 2 вершин и между ними было добавлено новое ребро, вы не обнаружите это новое ребро.   -  person Nikunj Banka    schedule 24.03.2014

Ответы (2)


arrow_upward
0
arrow_downward

Это кажется вполне разумным подходом.

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

Если это большой (возможно, бесконечный) граф (или он содержит циклы и слишком много узлов, чтобы отслеживать их все, как вы делаете DFS, чтобы не застрять в цикле) и вы ищете какой-то узел, не слишком глубоко в графике, либо BFS, либо DFS с итеративным углублением может быть лучшей идеей.

person Bernhard Barker    schedule 21.03.2014
comment
Упрощенная версия проблемы, которую я пытаюсь решить, похожа на создание программных графов вызовов. Например, я хотел бы знать граф вызовов, который имеет глубину 10 для конкретного API. Я могу начать с этого API, и когда я обнаружу вызывающих этот API, я добавлю их в список дочерних элементов этого узла и действую, как описано выше. - person user1595789; 22.03.2014

arrow_upward
0
arrow_downward

DFS означает поиск в глубину. а под «Поиском» подразумевается, что он не знает, что его ждет впереди. Так что DFS на известном графе ничем не отличается от DFS на графе, где вы узнаете дочерний элемент как раз в то время, когда вы достигаете родителя.

person firemana    schedule 24.03.2014