Exponenta Banner

dfsearch

Поиск графика в глубину

свернуть все на странице

Синтаксис

v = dfsearch(G,s)
T = dfsearch(G,s,events)
[T,E] = dfsearch(G,s,events)
[___] = dfsearch(___,'Restart',tf)

Описание

пример

v = dfsearch(G,s) применяет поиск в глубину, чтобы изобразить в виде графика G запуск в узле s. Результатом является вектор из идентификаторов узла в порядке их открытия.

пример

T = dfsearch(G,s,events) настраивает выход поиска в глубину путем установки флага одного или нескольких поисковых событий. Например, T = dfsearch(G,s,'allevents') возвращает таблицу, содержащую все отмеченные события и X = dfsearch(G,s,'edgetonew') возвращает матричный или массив ячеек ребер.

[T,E] = dfsearch(G,s,events) дополнительно возвращает вектор из индексов ребра E когда events установлен в 'edgetonew', 'edgetodiscovered', или 'edgetofinished'. Индексы ребра для уникальной идентификации ребер в мультиграфе.

пример

[___] = dfsearch(___,'Restart',tf), где tf true, перезапускает поиск, если никакие новые узлы не достижимы от обнаруженных узлов. Можно использовать любую из комбинаций аргументов ввода или вывода в предыдущих синтаксисах. Эта опция гарантирует, что поиск в глубину достигает всех узлов и ребер в графике, даже если они не достижимы от стартового узла, s.

Примеры

свернуть все

Скрипт Open Live Script

Создайте и постройте график. 

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
Скрипт Open Live Script

Создайте и постройте ориентированного графа.

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

Чтобы выполнить шаги в алгоритме, считайте события в таблице сверху донизу. Например:

  1. Алгоритм начинается в узле 3

  2. Ребро обнаружено между узлом 3 и узлом 4

  3. Узел 4 обнаружен

  4. и так далее...

Скрипт Open Live Script

Выполните поиск в глубину графика с несколькими компонентами, и затем подсветите вершины графика и ребра на основе результатов поиска.

Создайте и постройте ориентированного графа. Этот график имеет два слабо связанных компонента.

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')

Скрипт Open Live Script

Сделайте ориентированного графа нециклическим путем инвертирования некоторых его ребер.

Создайте и постройте ориентированного графа.

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')

Входные параметры

свернуть все

Введите график в виде любого graph или digraph объект. Используйте graph создать неориентированного графа или digraph создать ориентированного графа.

Пример: G = graph(1,2)

Пример: G = digraph([1 2],[2 3])

Стартовый узел в виде одного из значений в этой таблице.

ЗначениеПример
Скалярный индекс узла1
Имя узла вектора символов'A'
Имя узла строкового скаляра"A"

Пример: dfsearch(G,1)

Отмеченные поисковые события в виде одной из опций в следующей таблице.

  • Чтобы отметить одно события, используйте имена флага.

  • Чтобы отметить подмножество событий, поставьте два или больше имени флага в массив ячеек или массив строк.

  • Чтобы отметить все события, используйте 'allevents'.

Примечание

В зависимости от значения events, выход dfsearch варьируется. См. последний столбец в следующей таблице для получения информации о выходном параметре, возвращенном каждой опцией.

Значение eventsОписаниеВывод
'discovernode' (значение по умолчанию)

Был обнаружен новый узел.

Возвратите вектор из идентификаторов узла:

  • Если s числовой индекс узла, затем вектор содержит числовые индексы узла.

  • Если s имя узла, затем вектор является массивом ячеек, содержащим имена узла.

'finishnode'

Посетили все исходящие ребра от узла.

'startnode'

Этот флаг указывает на стартовый узел в поиске.

Если 'Restart' true, затем 'startnode' отмечает стартовый узел каждый раз поисковые перезапуски.

'edgetonew'

Ребро соединяется с неоткрытым узлом.

Возвратите матричный или массив ячеек размера N- 2 это задает конечные узлы ребер в графике:

  • Если s числовой индекс узла, затем матрица содержит числовые индексы узла.

  • Если s имя узла, затем матрица является массивом ячеек, содержащим имена узла.

Кроме того, можно задать второй выход с [T,E] = dfsearch(…) это возвращает вектор из индексов ребра E.

'edgetodiscovered'

Ребро соединяется с ранее обнаруженным узлом.

'edgetofinished'

Ребро соединяется с законченным узлом.

cellArray

Задайте два или больше флага в массиве ячеек, чтобы только отметить те события во время поиска.

Возвратите таблицу, T, который содержит переменные T.Event, T.Node, T.Edge, и T.EdgeIndex:

  • T.Event категориальный вектор, содержащий флаги в порядке их вхождения.

  • T.Node содержит идентификатор узла соответствующего узла для событий 'discovernode', 'finishnode', и 'startnode'.

  • T.Edge содержит соответствующее ребро для событий 'edgetonew', 'edgetodiscovered', и 'edgetofinished'.

  • T.EdgeIndex содержит индекс ребра для событий 'edgetonew', 'edgetodiscovered', и 'edgetofinished'. Индекс ребра для уникальной идентификации повторных ребер в мультиграфе.

  • Неиспользованные элементы T.Node и T.Edge установлены в NaN.

  • Если s числовой индекс узла, затем T.Node и T.Edge содержите числовые индексы узла.

  • Если s имя узла, затем T.Node и T.Edge массивы ячеек, содержащие имена узла.

'allevents'

Все события отмечаются.

Пример: v = dfsearch(G,3) начинает поиск в третьем узле и возвращает вектор, v, содержа узлы в порядке открытия. Это совпадает с v = dfsearch(G,3,'discovernode').

Пример: X = dfsearch(G,'A','edgetonew') начинается в узле под названием 'A' и возвращает массив ячеек из символьных векторов, X, указание на каждое из ребер, которое соединяется с неоткрытым узлом во время поиска.

Пример: T = dfsearch(G,s,{'discovernode','finishnode'}) возвращает таблицу, T, но только флаги, когда новые узлы обнаружены или когда узел отмечен законченный.

Пример: T = dfsearch(G,s,'allevents') флаги все поисковые события и возвращают таблицу, T.

Типы данных: char | string | cell

Переключитесь, чтобы перезапустить поиск в виде false (значение по умолчанию) или true. Эта опция полезна, если график содержит узлы, которые недостижимы от стартового узла. Если 'Restart' true, затем поиск перезапускает каждый раз, когда неоткрытые узлы остаются, что недостижимы от обнаруженных узлов. Новый узел запуска является узлом с самым маленьким индексом, который является все еще неоткрытым. Повторения процесса перезапуска до dfsearch обнаруживает все узлы.

'Restart' false по умолчанию, так, чтобы поиск только посещает узлы, которые достижимы от стартового узла.

Когда 'Restart' true, 'discovernode' и 'finishnode' события имеют место однажды для каждого узла в графике. Кроме того, каждое ребро в графике отмечается однажды 'edgetonew', 'edgetodiscovered', или 'edgetofinished'. Ребра отмечаются 'edgetonew' сформируйте одно или несколько деревьев.

Пример: T = dfsearch(graph([1 3],[2 4]),1,'Restart',true) поисковые запросы оба из связанных компонентов в графике.

Типы данных: логический

Выходные аргументы

свернуть все

Идентификаторы узла, возвращенные в одном из следующих форматов:

  • Если вы используете числовой идентификатор узла, чтобы задать стартовый узел, s, затем v числовой вектор-столбец индексов узла.

  • Если s вектор символов или строка, содержащая имя узла, затем v вектор ячейки, содержащий имена узла.

Идентификаторы узла в v отразите порядок открытия поиском графика в глубину.

Результаты поиска, возвращенные в одном из следующих форматов:

  • Если events не задан или 'discovernode', 'finishnode', или 'startnode', затем T вектор из идентификаторов узла, похожих на v.

  • Если events 'edgetonew', 'edgetodiscovered', или 'edgetofinished', затем T матричный или массив ячеек размера N- 2 указание на входные и выходные узлы для каждого соответствующего ребра.

  • Если events массив ячеек поисковых событий или 'allevents', затем T таблица, содержащая отмеченные поисковые события. Таблица содержит поисковые флаги события в T.Event, соответствующие идентификаторы узла в T.Node, и соответствующие ребра в T.Edge и T.EdgeIndex.

Во всех случаях:

  • Порядок элементов или строки T указывает на их порядок вхождения во время поиска.

  • Если вы задаете s как числовой идентификатор узла, затем T также относится к узлам с помощью их числовых идентификаторов.

  • Если вы задаете s как имя узла, затем T также относится к узлам с помощью их имен.

Индексы ребра, возвращенные как вектор.

Задайте этот выход, чтобы получить вектор из индексов ребра для событий 'edgetonew', 'edgetodiscovered', или 'edgetofinished'то- 1 вектор из индексов ребра соответствует T, который является матричным или массивом ячеек размера N- 2 указание на входные и выходные узлы для каждого соответствующего ребра.

Пример: [T,E] = dfsearch(G,s,'edgetonew')

Советы

  • 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' событие указывает на стартовый узел каждый раз поисковые перезапуски.

Смотрите также

| | |

Темы

Введенный в R2015b

Документация MATLAB

Поддержка