bfsearch

Поиск по графику

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

Синтаксис

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

Описание

пример

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

пример

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

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

пример

[___] = bfsearch(___,'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.

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

v = bfsearch(G,2)
v = 10×1

     2
     1
     6
     7
     8
     9
    10
     3
     4
     5
Открыть Live Script

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

s = [1 1 1 2 3 3 3 4 6];
t = [2 4 5 5 6 7 4 1 4];
G = digraph(s,t);
plot(G)

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

Выполните поиск по ширине первого графика, начиная с узла 1. Задайте 'allevents' для возврата таблицы, содержащей все события в алгоритме.

T = bfsearch(G,1,'allevents')
T=14×4 table
         Event          Node       Edge       EdgeIndex
    ________________    ____    __________    _________

    startnode             1     NaN    NaN       NaN   
    discovernode          1     NaN    NaN       NaN   
    edgetonew           NaN       1      2         1   
    discovernode          2     NaN    NaN       NaN   
    edgetonew           NaN       1      4         2   
    discovernode          4     NaN    NaN       NaN   
    edgetonew           NaN       1      5         3   
    discovernode          5     NaN    NaN       NaN   
    finishnode            1     NaN    NaN       NaN   
    edgetodiscovered    NaN       2      5         4   
    finishnode            2     NaN    NaN       NaN   
    edgetofinished      NaN       4      1         8   
    finishnode            4     NaN    NaN       NaN   
    finishnode            5     NaN    NaN       NaN

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

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

  2. Между узлом 1 и узлом 2 обнаружено ребро

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

  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

Выполните поиск графика по ширине первой, начиная с узла 2, и отметьте 'edgetonew', 'edgetofinished', и 'startnode' события. Задайте Restart как true чтобы выполнить перезапуск поиска каждый раз, когда есть оставшиеся узлы, которые не могут быть достигнуты.

events = {'edgetonew','edgetofinished','startnode'};
T = bfsearch(G,2,events,'Restart',true)
T=15×4 table
        Event         Node       Edge       EdgeIndex
    ______________    ____    __________    _________

    startnode           2     NaN    NaN       NaN   
    edgetonew         NaN       2      5         3   
    edgetonew         NaN       2      6         4   
    edgetonew         NaN       2      7         5   
    edgetofinished    NaN       7      2         8   
    startnode           1     NaN    NaN       NaN   
    edgetonew         NaN       1      3         1   
    edgetonew         NaN       1      4         2   
    edgetofinished    NaN       3      2         6   
    edgetofinished    NaN       4      6         7   
    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'

highlight(p, 'Edges', T.EdgeIndex(T.Event == 'edgetonew'), 'EdgeColor', 'g')
highlight(p, 'Edges', T.EdgeIndex(T.Event == 'edgetofinished'), 'EdgeColor', 'k') 
highlight(p,T.Node(~isnan(T.Node)),'NodeColor','r')

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

Открыть Live Script

Используйте первый поиск по ширине, чтобы определить, что график является двудольным, и вернуть соответствующие разделы. Двухпартийный график является графиком, которая имеет узлы, которые можно разделить на два множества A и B, с каждым ребром в графике, соединяющим узел в A в узел в B.

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

s = [1 1 1 1 2 2 4 5 6 7 8];
t = [2 3 6 8 5 10 6 6 10 3 10];
g = digraph(s,t);
plot(g);

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

Используйте поиск breadth-first на графике, чтобы определить, является ли он двудольным, и если это так, верните соответствующие разделы.

events = {'edgetonew', 'edgetodiscovered', 'edgetofinished'};
T = bfsearch(g, 1, events, 'Restart', true);
partitions = false(1, numnodes(g));
is_bipart = true;
is_edgetonew = T.Event == 'edgetonew';
ed = T.Edge;

for ii=1:size(T, 1)   
    if is_edgetonew(ii)
        partitions(ed(ii, 2)) = ~partitions(ed(ii, 1));
    else
        if partitions(ed(ii, 1)) == partitions(ed(ii, 2))
            is_bipart = false;
            break;
        end
    end
end

is_bipart
is_bipart = logical
   1

Начиная с g является двудольным, partitions переменная содержит информацию о том, к какому разделу принадлежит каждый узел.

Постройте график с 'layered' размещение, использование partitions переменная, чтобы задать исходные узлы, которые появляются в первом слое.

partitions
partitions = 1x10 logical array

   0   1   1   0   0   1   0   1   0   0


plot(g, 'Layout', 'layered', 'Source', find(partitions));

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"

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

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

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

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

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

Примечание

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

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

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

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

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

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

'finishnode'

Все исходящие ребра из узла были посещены.

'startnode'

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

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

'edgetonew'

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

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

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

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

Кроме того, можно задать второй выход с [T,E] = bfsearch(…) который возвращает вектор индексов ребер 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 = bfsearch(G,3) начинает поиск в третьем узле и возвращает вектор, v, содержащая узлы в порядке обнаружения. Это то же самое, что и v = bfsearch(G,3,'discovernode').

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

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

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

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

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

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

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

Пример: T = bfsearch(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] = bfsearch(G,s,'edgetonew')

Совет

  • dfsearch и bfsearch относиться к неориентированным графам так же, как и к ориентированным графам. Неориентированное ребро между узлами s и t обрабатывается как два ориентированных ребер, один от s на t и один из t на s.

Алгоритмы

Алгоритм поиска Breadth-First начинается в стартовом узле, s, и просматривает все его соседние узлы в порядке их индекса узла. Затем для каждого из этих соседей он посещает их невидимых соседей по порядку. Алгоритм продолжается до тех пор, пока не будут посещены все узлы, которые доступны из начального узла.

В псевдокоде алгоритм может быть записан как:

Event startnode(S)
Event discovernode(S)
NodeList = {S}

WHILE NodeList is not empty

  C = NodeList{1}
  Remove first element from NodeList
  
  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
      Event discovernode(N)
      Append N to the end of NodeList
    END
  END

  Event finishnode(C)
END

bfsearch может возвращать флаги для описания различных событий в алгоритме, например, когда обнаружен новый узел или когда были посещены все исходящие ребра узла. Флаги событий перечислены здесь.

Флаг событияОписание события
'discovernode'

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

'finishnode'

Все исходящие ребра из узла были посещены.

'startnode'

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

'edgetonew'

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

'edgetodiscovered'

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

'edgetofinished'

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

Для получения дополнительной информации смотрите описание входного параметра для events.

Примечание

В случаях, когда входной график содержит узлы, которые недоступны из стартового узла, 'Restart' опция предоставляет способ сделать поиск посещающим каждый узел в графике. В этом случае 'startnode' событие указывает начальный узел каждый раз, когда поиск перезапускается.

См. также

| | |

Темы

Введенный в R2015b

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

Поддержка

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