Поиск графика в глубину
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.
Алгоритм Поиска в глубину начинается в стартовом узле, 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' событие указывает на стартовый узел каждый раз поисковые перезапуски.