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.

Примеры

свернуть все

Открыть 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)

Figure contains an axes. The axes contains an object of type graphplot.

Выполните глубинный первый поиск графика, начиная с узла 7. Результат указывает порядок обнаружения узлов.

v = dfsearch(G,7)
v = 10×1

     7
     2
     1
     3
     4
     5
     6
     8
     9
    10
Открыть 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)

Figure contains an axes. The axes contains an object of type graphplot.

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

Открыть 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');

Figure contains an axes. The axes contains an object of type graphplot.

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

Figure contains an axes. The axes contains an object of type graphplot.

Открыть 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')

Figure contains an axes. The axes contains an object of type graphplot.

Выполните поиск по глубине на графике, пометив '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')

Figure contains an axes. The axes contains an object of type graphplot.

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

свернуть все

Входной график, заданный как 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-by- 2 который задает конечные узлы ребер в графике:

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

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

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

'edgetodiscovered'

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

'edgetofinished'

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

массив ячеек

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

Верните таблицу, 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) выполняет поиск по обоим связанным компонентам в графике.

Типы данных: logical

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

свернуть все

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

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

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

The идентификаторов узла in 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'. The N-by- 1 вектор индексов ребра соответствует T, который является матрицей или массивом ячеек размера N-by- 2 указывает исходный и целевой узлы для каждого соответствующего ребра.

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

Совет

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

См. также

| | |

Темы

Введенный в R2015b

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

Поддержка

Для просмотра документации необходимо авторизоваться на сайте