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

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

свернуть все

Входной график, заданный как объект граф или диграф. Используйте граф для создания неориентированного графа или диграф для создания ориентированного графа.

Пример: G = график (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-by-2, который задает конечные узлы краев в графике:

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

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

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

'edgetodiscovered'

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

'edgetofinished'

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

cellArray

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

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

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

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

  • T. Край содержит соответствующий край для событий '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, 'edgetonew') начинается в узле под названием и возвращает массив ячеек из символьных векторов, X, указывая на каждый из краев, который соединяется с неоткрытым узлом во время поиска.

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

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

Типы данных: char | представляет в виде строки | ячейка

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

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

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

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

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

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

свернуть все

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

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

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

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

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

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

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

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

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

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

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

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

Граничные индексы, возвращенные как вектор.

Задайте этот вывод, чтобы получить вектор граничных индексов для событий 'edgetonew', 'edgetodiscovered' или 'edgetofinished'. N-by-1 вектор граничных индексов соответствует T, который является матричным или массивом ячеек размера N-by-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
Поддержка