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