Поиск графов по ширине
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.
Алгоритм поиска Breadth-First начинается с начального узла, 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' |
Edge подключается к ранее обнаруженному узлу |
'edgetofinished' |
Кромка подключается к готовому узлу |
Дополнительные сведения см. в описании входного аргумента для events.
Примечание
В случаях, когда входной граф содержит узлы, которые недоступны из начального узла, 'Restart' предоставляет способ сделать поиск посещаемым каждым узлом в графике. В этом случае 'startnode' событие указывает начальный узел при каждом перезапуске поиска.