Поиск по графику
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);
Используйте поиск breadth-first на графике, чтобы определить, является ли он двудольным, и если это так, верните соответствующие разделы.
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' |
Ребро соединяется с ранее обнаруженным узлом |
'edgetofinished' |
Ребро соединяется с конечным узлом |
Для получения дополнительной информации смотрите описание входного параметра для events.
Примечание
В случаях, когда входной график содержит узлы, которые недоступны из стартового узла, 'Restart' опция предоставляет способ сделать поиск посещающим каждый узел в графике. В этом случае 'startnode' событие указывает начальный узел каждый раз, когда поиск перезапускается.