Поиск графика в глубину
v = dfsearch(G,s)
T = dfsearch(G,s,events)
[T,E] = dfsearch(G,s,events)
[___] = dfsearch(___,'Restart',tf)
применяет поиск в глубину, чтобы изобразить в виде графика v
= dfsearch(G
,s
)G
, запускающийся в узле s
. Результатом является вектор идентификаторов узла в порядке их открытия.
[___] = dfsearch(___,'Restart',
, то, где tf
)tf
является true
, перезапускает поиск, если никакие новые узлы не достижимы от обнаруженных узлов. Можно использовать любую из комбинаций аргументов ввода или вывода в предыдущих синтаксисах. Эта опция гарантирует, что поиск в глубину достигает всех узлов и ребер в графике, даже если они не достижимы от стартового узла, s
.
dfsearch
и bfsearch
обрабатывают неориентированных графов то же самое как ориентированные графы. Неориентированное ребро между узлами s
и t
обработано как два ориентированных ребра, один от s
до t
и один от t
до s
.
Алгоритм Поиска в глубину начинается в стартовом узле, s
, и осматривает соседа s
, который имеет самый маленький индекс узла. Затем для того соседа, это осматривает следующего неоткрытого соседа с самым низким индексом. Это продолжается, пока поиск не сталкивается с узлом, соседей которого все посетили. В той точке поиск отслеживает в обратном порядке вдоль пути к самому близкому ранее обнаруженному узлу, который имеет неоткрытого соседа. Этот процесс продолжается, пока все узлы, которые достижимы от стартового узла, не посетили.
В псевдокоде (рекурсивный) алгоритм может быть написан как:
Event startnode(S) Call DFS(S) function DFS(C) Event discovernode(C) FOR edge E from outgoing edges of node C, connecting to node N Event edgetonew(C,E), edgetodiscovered(C,E) or edgetofinished(C,E) (depending on the state of node N) IF event was edgetonew Call DFS(N) END END Event finishnode(C) END
dfsearch
может возвратить флаги, чтобы описать различные события в алгоритме, такой как тогда, когда новый узел обнаружен или когда все исходящие ребра узла посетили. Флаги события перечислены здесь.
Флаг события | Описание события |
---|---|
'discovernode' |
Был обнаружен новый узел. |
'finishnode' |
Посетили все исходящие ребра от узла. |
'startnode' |
Этот флаг указывает на стартовый узел в поиске. |
'edgetonew' |
Ребро соединяется с неоткрытым узлом |
'edgetodiscovered' |
Ребро соединяется с ранее обнаруженным узлом |
'edgetofinished' |
Ребро соединяется с законченным узлом |
Для получения дополнительной информации см. описание входного параметра для events
.
В случаях, где входной график содержит узлы, которые недостижимы от стартового узла, опция 'Restart'
обеспечивает способ нанести поисковый визит каждый узел в графике. В этом случае событие 'startnode'
указывает на стартовый узел каждый раз поисковые перезапуски.