graphtraverse

Пересеките график следующими смежными узлами

Синтаксис

[disc, pred, closed] = graphtraverse(GS)
[...] = graphtraverse(GS, ...'Depth', DepthValue, ...)
[...] = graphtraverse(GS, ...'Directed', DirectedValue, ...)
[...] = graphtraverse(GS, ...'Method', MethodValue, ...)

Аргументы

G N на n разреженная матрица, которая представляет ориентированного графа. Ненулевые записи в матричном G укажите на присутствие ребра.
SЦелое число, которое указывает на исходный узел в графике G.
DepthValueЦелое число, которое указывает на узел в графике G это задает глубину поиска. Значением по умолчанию является Inf Бесконечность.
DirectedValueСвойство, которое указывает ли график G направлен или неориентированный. Введите false для неориентированного графа. Это приводит к верхнему треугольнику проигнорированной разреженной матрицы. Значением по умолчанию является true.
MethodValueВектор символов или строка, которая задает алгоритм, раньше пересекали график. Выбор:
  • 'BFS' — Поиск в ширину. Временной сложностью является O(N+E), где N и E количество узлов и ребер соответственно.

  • 'DFS' — Алгоритм по умолчанию. Поиск в глубину. Временной сложностью является O(N+E), где N и E количество узлов и ребер соответственно.

Описание

Совет

Дополнительные сведения о функциях теории графов см. в Функциях Теории графов.

[disc, pred, closed] = graphtraverse(GS) график пересечений G запуск с узла обозначается целочисленным SG N на n разреженная матрица, которая представляет ориентированного графа. Ненулевые записи в матричном G укажите на присутствие ребра. disc вектор из индексов узла в порядке, в котором они обнаружены. pred вектор из индексов узла-предшественников (перечисленный в порядке индексов узла) получившегося дерева охвата. closed вектор из индексов узла в порядке, в котором они закрываются.

[...] = graphtraverse (G S PropertyName ', PropertyValue, ...) вызовы graphtraverse с дополнительными свойствами, которые используют имя свойства / пары значения свойства. Можно задать одно или несколько свойств в любом порядке. Каждый PropertyName должен быть заключен в одинарные кавычки и нечувствительный к регистру. Это имя свойства / пары значения свойства следующие:

[...] = graphtraverse(GS, ...'Depth', DepthValue, ...) задает глубину поиска. DepthValue целое число, указывающее на узел в графике G. Значением по умолчанию является Inf Бесконечность.

[...] = graphtraverse(GS, ...'Directed', DirectedValue, ...) указывает, направлен ли график или неориентированный. Установите DirectedValue к false для неориентированного графа. Это приводит к верхнему треугольнику проигнорированной разреженной матрицы. Значением по умолчанию является true.

[...] = graphtraverse(GS, ...'Method', MethodValue, ...) позволяет вам указать, что алгоритм раньше пересекал график. Выбор:

  • 'BFS' — Поиск в ширину. Временной сложностью является O(N+E), где N и E количество узлов и ребер соответственно.

  • 'DFS' — Алгоритм по умолчанию. Поиск в глубину. Временной сложностью является O(N+E), где N и E количество узлов и ребер соответственно.

Примеры

  1. Создайте ориентированного графа с 10 узлами и 12 ребрами.

    DG = sparse([1 2 3 4 5 5 5 6 7 8 8 9],...
                  [2 4 1 5 3 6 7 9 8 1 10 2],true,10,10)
    
    DG =
    
       (3,1)        1
       (8,1)        1
       (1,2)        1
       (9,2)        1
       (5,3)        1
       (2,4)        1
       (4,5)        1
       (5,6)        1
       (5,7)        1
       (7,8)        1
       (6,9)        1
       (8,10)       1
    
    h = view(biograph(DG))
    Biograph object with 10 nodes and 12 edges.

  2. Пересеките график, чтобы найти порядок открытия поиска в глубину (DFS), запускающийся в узле 4.

    order = graphtraverse(DG,4)
    
    order =
    
         4     5     3     1     2     6     9     7     8    10
    
  3. Пометьте узлы порядком открытия DFS.

    for i = 1:10
        h.Nodes(order(i)).Label =...
    			sprintf('%s:%d',h.Nodes(order(i)).ID,i);
    end
    h.ShowTextInNodes = 'label'
    dolayout(h)

  4. Пересеките график, чтобы найти порядок открытия поиска в ширину (BFS), запускающийся в узле 4.

    order = graphtraverse(DG,4,'Method','BFS')
    
    order =
    
         4     5     3     6     7     1     9     8     2    10
    
  5. Пометьте узлы порядком открытия BFS.

    for i = 1:10
        h.Nodes(order(i)).Label =...
    			sprintf('%s:%d',h.Nodes(order(i)).ID,i);
    end
    h.ShowTextInNodes = 'label'
    dolayout(h)

  6. Найдите и окрасьте узлы, которые являются близко к (в двух ребрах) узел 4.

    node_idxs = graphtraverse(DG,4,'depth',2)
    
    node_idxs =
    
         4     5     3     6     7
    
    set(h.nodes(node_idxs),'Color',[1 0 0])

Ссылки

[1] Sedgewick, R., (2002). Алгоритмы на C++, алгоритмы графика части 5 (Аддисон-Уэсли).

[2] Siek, J.G., Ли, L-Q и Lumsdaine, A. (2002). Руководство пользователя библиотеки графика повышения и справочник, (верхний Сэддл-Ривер, образование НДЖ:ПИРСОНА).

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