Поиск по графику глубина-первая
v = dfsearch(G,s)G запуск в узле s. Результатом является вектор идентификаторов узла в порядке их обнаружения.
[___] = dfsearch(___,'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)
Выполните глубинный первый поиск графика, начиная с узла 7. Результат указывает порядок обнаружения узлов.
v = dfsearch(G,7)
v = 10×1
7
2
1
3
4
5
6
8
9
10
Создайте и постройте ориентированного графа.
A = [0 1 0 1 1 0 0;
0 0 0 0 0 0 0;
0 0 0 1 0 1 1;
0 0 0 0 0 1 0;
0 0 0 0 0 0 0;
0 0 0 0 0 0 0;
0 0 0 0 0 0 0];
G = digraph(A);
plot(G)
Выполните поиск по глубине первого графика, начиная с узла 3. Задайте 'allevents' для возврата таблицы, содержащей все события в алгоритме.
T = dfsearch(G,3,'allevents')T=13×4 table
Event Node Edge EdgeIndex
______________ ____ __________ _________
startnode 3 NaN NaN NaN
discovernode 3 NaN NaN NaN
edgetonew NaN 3 4 4
discovernode 4 NaN NaN NaN
edgetonew NaN 4 6 7
discovernode 6 NaN NaN NaN
finishnode 6 NaN NaN NaN
finishnode 4 NaN NaN NaN
edgetofinished NaN 3 6 5
edgetonew NaN 3 7 6
discovernode 7 NaN NaN NaN
finishnode 7 NaN NaN NaN
finishnode 3 NaN NaN NaN
Чтобы следовать шагам в алгоритме, прочитайте события в таблице сверху вниз. Для примера:
Алгоритм начинается с узла 3
Между узлом 3 и узлом 4 обнаружено ребро
Узел 4 обнаружен
и так далее...
Выполните поиск графика по глубине с несколькими компонентами, а затем выделите узлы и ребра графика на основе результатов поиска.
Создайте и постройте ориентированного графа. Этот график имеет два слабо связанных компоненты.
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
Выполните глубинный первый поиск графика, начиная с узла 4, и отметьте 'edgetonew', 'edgetodiscovered', 'edgetofinished', и 'startnode' события. Задайте Restart как true чтобы выполнить перезапуск поиска каждый раз, когда есть оставшиеся узлы, которые не могут быть достигнуты.
events = {'edgetonew','edgetodiscovered','edgetofinished','startnode'};
T = dfsearch(G,4,events,'Restart',true)T=15×4 table
Event Node Edge EdgeIndex
________________ ____ __________ _________
startnode 4 NaN NaN NaN
edgetonew NaN 4 6 7
startnode 1 NaN NaN NaN
edgetonew NaN 1 3 1
edgetonew NaN 3 2 6
edgetonew NaN 2 5 3
edgetofinished NaN 2 6 4
edgetonew NaN 2 7 5
edgetodiscovered NaN 7 2 8
edgetofinished NaN 1 4 2
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'
Пурпурные ребра предназначены для 'edgetodiscovered'
highlight(p, 'Edges', T.EdgeIndex(T.Event == 'edgetonew'), 'EdgeColor', 'g') highlight(p, 'Edges', T.EdgeIndex(T.Event == 'edgetofinished'), 'EdgeColor', 'k') highlight(p, 'Edges', T.EdgeIndex(T.Event == 'edgetodiscovered'), 'EdgeColor', 'm') highlight(p,T.Node(~isnan(T.Node)),'NodeColor','r')
Сделайте ориентированный граф ациклическим путем обращения вспять некоторых его ребер.
Создайте и постройте ориентированного графа.
s = [1 2 3 3 3 3 4 5 6 7 8 9 9 9 10]; t = [7 6 1 5 6 8 2 4 4 3 7 1 6 8 2]; g = digraph(s,t); plot(g, 'Layout', 'force')
Выполните поиск по глубине на графике, пометив 'edgetodiscovered' событие. Это событие соответствует ребрам, которые завершают цикл.
[e,edge_indices] = dfsearch(g, 1, 'edgetodiscovered', 'Restart', true)
e = 3×2
3 1
6 4
8 7
edge_indices = 3×1
3
9
11
Использование flipedge изменить направление отмеченных ребер, чтобы они больше не завершали цикл. Это удаляет все циклы из графика. Использование isdag чтобы подтвердить, что график является ациклическим.
gnew = flipedge(g, edge_indices); isdag(gnew)
ans = logical
1
Постройте график и подсветите ребра, которые были развернуты.
p = plot(gnew, 'Layout', 'force'); highlight(p,'Edges',findedge(gnew,e(:,2),e(:,1)),'EdgeColor','r')
dfsearch и bfsearch относиться к неориентированным графам так же, как и к ориентированным графам. Неориентированное ребро между узлами s и t обрабатывается как два ориентированных ребер, один от s на t и один из t на s.
Алгоритм поиска Depth-First начинается в стартовом узле, 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' событие указывает начальный узел каждый раз, когда поиск перезапускается.