bfsearch
Поиск графика в ширину
Синтаксис
Описание
v = bfsearch(G,s)G запуск в узле s. Результатом является вектор из идентификаторов узла в порядке их открытия.
[___] = bfsearch(___,'Restart',, где tf)tf true, перезапускает поиск, если никакие новые узлы не достижимы от обнаруженных узлов. Можно использовать любую из комбинаций аргументов ввода или вывода в предыдущих синтаксисах. Эта опция гарантирует, что поиск в ширину достигает всех узлов и ребер в графике, даже если они не достижимы от стартового узла, s.
Примеры
Выполнение поиска графика в ширину
Создайте и постройте график.
s = [1 1 1 1 2 2 2 2 2]; t = [3 5 4 2 6 10 7 9 8]; G = graph(s,t); plot(G)
Выполните поиск в ширину графика, запускающегося в узле 2. Результат показывает на порядок открытия узла.
v = bfsearch(G,2)
v = 10×1
2
1
6
7
8
9
10
3
4
5
Поиск графика в ширину со всеми Событиями
Создайте и постройте ориентированного графа.
s = [1 1 1 2 3 3 3 4 6]; t = [2 4 5 5 6 7 4 1 4]; G = digraph(s,t); plot(G)
Выполните поиск в ширину на графике, запускающемся в узле 1. Задайте 'allevents' возвратить таблицу, содержащую все события в алгоритме.
T = bfsearch(G,1,'allevents')T=14×4 table
Event Node Edge EdgeIndex
________________ ____ __________ _________
startnode 1 NaN NaN NaN
discovernode 1 NaN NaN NaN
edgetonew NaN 1 2 1
discovernode 2 NaN NaN NaN
edgetonew NaN 1 4 2
discovernode 4 NaN NaN NaN
edgetonew NaN 1 5 3
discovernode 5 NaN NaN NaN
finishnode 1 NaN NaN NaN
edgetodiscovered NaN 2 5 4
finishnode 2 NaN NaN NaN
edgetofinished NaN 4 1 8
finishnode 4 NaN NaN NaN
finishnode 5 NaN NaN NaN
Чтобы выполнить шаги в алгоритме, считайте события в таблице сверху донизу. Например:
Алгоритм начинается в узле 1
Ребро обнаружено между узлом 1 и узлом 2
Узел 2 обнаружен
и так далее...
Поиск графика в ширину с несколькими компонентами
Выполните поиск в ширину графика с несколькими компонентами, и затем подсветите вершины графика и ребра на основе результатов поиска.
Создайте и постройте ориентированного графа. Этот график имеет два слабо связанных компонента.
s = [1 1 2 2 2 3 4 7 8 8 8 8]; t = [3 4 7 5 6 2 6 2 9 10 11 12]; G = digraph(s,t); p = plot(G,'Layout','layered');
c = conncomp(G,'Type','weak')
c = 1×12
1 1 1 1 1 1 1 2 2 2 2 2
Выполните поиск в ширину графика, запускающегося в узле 2, и отметьте 'edgetonew', 'edgetofinished', и 'startnode' события. Задайте Restart как true сделать поисковый перезапуск каждый раз, когда там остаются узлы, которые не могут быть достигнуты.
events = {'edgetonew','edgetofinished','startnode'};
T = bfsearch(G,2,events,'Restart',true)T=15×4 table
Event Node Edge EdgeIndex
______________ ____ __________ _________
startnode 2 NaN NaN NaN
edgetonew NaN 2 5 3
edgetonew NaN 2 6 4
edgetonew NaN 2 7 5
edgetofinished NaN 7 2 8
startnode 1 NaN NaN NaN
edgetonew NaN 1 3 1
edgetonew NaN 1 4 2
edgetofinished NaN 3 2 6
edgetofinished NaN 4 6 7
startnode 8 NaN NaN NaN
edgetonew NaN 8 9 9
edgetonew NaN 8 10 10
edgetonew NaN 8 11 11
edgetonew NaN 8 12 12
Когда Restart true, 'startnode' событие возвращает информацию о том, где и когда алгоритм перезапускает поиск.
Подсветите график на основе события:
Окрасьте стартовые узлы в красный.
Зеленые ребра для
'edgetonew'Черные ребра для
'edgetofinished'
highlight(p, 'Edges', T.EdgeIndex(T.Event == 'edgetonew'), 'EdgeColor', 'g') highlight(p, 'Edges', T.EdgeIndex(T.Event == 'edgetofinished'), 'EdgeColor', 'k') highlight(p,T.Node(~isnan(T.Node)),'NodeColor','r')
Определите, является ли График Двусторонним
Используйте поиск в ширину, чтобы решить, что график является двусторонним, и возвратите соответствующие разделы. Биграф является графиком, который имеет узлы, которые можно разделить на два набора, A и B, с каждым ребром в графике, соединяющем узел в A к узлу в B.
Создайте и постройте ориентированного графа.
s = [1 1 1 1 2 2 4 5 6 7 8]; t = [2 3 6 8 5 10 6 6 10 3 10]; g = digraph(s,t); plot(g);
Используйте поиск в ширину на графике, чтобы определить, двусторонне ли это, и если так, возвратите соответствующие разделы.
events = {'edgetonew', 'edgetodiscovered', 'edgetofinished'};
T = bfsearch(g, 1, events, 'Restart', true);
partitions = false(1, numnodes(g));
is_bipart = true;
is_edgetonew = T.Event == 'edgetonew';
ed = T.Edge;
for ii=1:size(T, 1)
if is_edgetonew(ii)
partitions(ed(ii, 2)) = ~partitions(ed(ii, 1));
else
if partitions(ed(ii, 1)) == partitions(ed(ii, 2))
is_bipart = false;
break;
end
end
end
is_bipart
is_bipart = logical
1
Начиная с g является двусторонним, partitions переменная содержит информацию, о котором разделе каждый узел принадлежит.
Постройте биграф с 'layered' размещение, с помощью partitions переменная, чтобы задать исходные узлы, которые появляются в первом слое.
partitions
partitions = 1x10 logical array
0 1 1 0 0 1 0 1 0 0
plot(g, 'Layout', 'layered', 'Source', find(partitions));
Входные параметры
Выходные аргументы
Советы
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' событие указывает на стартовый узел каждый раз поисковые перезапуски.