Поиск графика в ширину
v = bfsearch(G,s)
T = bfsearch(G,s,events)
[T,E] = bfsearch(G,s,events)
[___] = bfsearch(___,'Restart',tf)
применяет поиск в ширину, чтобы изобразить в виде графика v
= bfsearch(G
,s
)G
, запускающийся в узле s
. Результатом является вектор идентификаторов узла в порядке их открытия.
[___] = bfsearch(___,'Restart',
, то, где tf
)tf
является true
, перезапускает поиск, если никакие новые узлы не достижимы от обнаруженных узлов. Можно использовать любую из комбинаций аргументов ввода или вывода в предыдущих синтаксисах. Эта опция гарантирует, что поиск в ширину достигает всех узлов и ребер в графике, даже если они не достижимы от стартового узла, s
.
dfsearch
и bfsearch
обрабатывают неориентированных графов то же самое как ориентированные графы. Неориентированное ребро между узлами s
и t
обработано как два ориентированных ребра, один от s
до t
и один от t
до s
.
Алгоритм Поиска в ширину начинается в стартовом узле, s
, и осматривает все свои соседние узлы в порядке их индекса узла. Затем для каждого из тех соседей, это посещает их непосещаемых соседей по порядку. Алгоритм продолжается, пока все узлы, которые достижимы от стартового узла, не посетили.
В псевдокоде алгоритм может быть написан как:
Event startnode(S) Event discovernode(S) NodeList = {S} WHILE NodeList is not empty C = NodeList{1} Remove first element from NodeList 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 Event discovernode(N) Append N to the end of NodeList END END Event finishnode(C) END
bfsearch
может возвратить флаги, чтобы описать различные события в алгоритме, такой как тогда, когда новый узел обнаружен или когда все исходящие ребра узла посетили. Флаги события перечислены здесь.
Флаг события | Описание события |
---|---|
'discovernode' |
Был обнаружен новый узел. |
'finishnode' |
Посетили все исходящие ребра от узла. |
'startnode' |
Этот флаг указывает на стартовый узел в поиске. |
'edgetonew' |
Ребро соединяется с неоткрытым узлом |
'edgetodiscovered' |
Ребро соединяется с ранее обнаруженным узлом |
'edgetofinished' |
Ребро соединяется с законченным узлом |
Для получения дополнительной информации см. описание входного параметра для events
.
В случаях, где входной график содержит узлы, которые недостижимы от стартового узла, опция 'Restart'
обеспечивает способ нанести поисковый визит каждый узел в графике. В этом случае событие 'startnode'
указывает на стартовый узел каждый раз поисковые перезапуски.