minspantree

Минимальное дерево охвата графика

Синтаксис

T = minspantree(G)
T = minspantree(G,Name,Value)
[T,pred] = minspantree(___)

Описание

пример

T = minspantree(G) возвращает минимальное дерево охвата, T, для графика G.

пример

T = minspantree(G,Name,Value) дополнительные опции использования заданы одним или несколькими Аргументами пары "имя-значение". Например, minspantree(G,'Method','sparse') использует алгоритм Краскэла для вычисления минимального дерева охвата.

пример

[T,pred] = minspantree(___) также возвращает вектор узлов-предшественников, pred, с помощью любого из входных параметров в предыдущих синтаксисах.

Примеры

свернуть все

Создайте и постройте график куба со взвешенными ребрами.

s = [1 1 1 2 5 3 6 4 7 8 8 8];
t = [2 3 4 5 3 6 4 7 2 6 7 5];
weights = [100 10 10 10 10 20 10 30 50 10 70 10];
G = graph(s,t,weights);
p = plot(G,'EdgeLabel',G.Edges.Weight);

Вычислите и постройте минимальное дерево охвата графика сверху графика. T содержит те же узлы как G, но подмножество ребер.

[T,pred] = minspantree(G);
highlight(p,T)

Создайте и постройте график, который имеет несколько компонентов.

s = {'a' 'a' 'a' 'b' 'b' 'c' 'e' 'e' 'f' 'f' 'f' 'f' 'g' 'g'};
t = {'b' 'c' 'd' 'c' 'd' 'd' 'f' 'g' 'g' 'h' 'i' 'j' 'i' 'j'};
G = graph(s,t);
p = plot(G,'Layout','layered');

Найдите минимальный лес охвата для графика, запускающегося в узле i. Подсветите получившийся лес в графике. Имена узла графика перенесены в минимальный древовидный граф охвата.

[T,pred] = minspantree(G,'Type','forest','Root',findnode(G,'i'));
highlight(p,T)

Используйте вектор узлов-предшественников, pred, чтобы создать направленную версию минимального леса охвата. Все ребра в этом дереве направлены далеко от корневых узлов в каждом компоненте (узлы i и a).

rootedTree = digraph(pred(pred~=0),find(pred~=0),[],G.Nodes.Name);
plot(rootedTree)

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

свернуть все

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

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

Аргументы в виде пар имя-значение

Укажите необязательные аргументы в виде пар ""имя, значение"", разделенных запятыми. Имя (Name) — это имя аргумента, а значение (Value) — соответствующее значение. Name должен появиться в кавычках. Вы можете задать несколько аргументов в виде пар имен и значений в любом порядке, например: Name1, Value1, ..., NameN, ValueN.

Пример: [T,pred] = minspantree(G,'Method','sparse')

Минимальный алгоритм связующего дерева, заданный как пара, разделенная запятой, состоящая из 'Method' и одна из опций в таблице.

ОпцияОписание
'dense' (значение по умолчанию)Алгоритм Прима. Этот алгоритм запускается в корневом узле и добавляет ребра в дерево при пересечении графика.
'sparse'Алгоритм Краскэла. Эти виды алгоритма все ребра в развес, и затем добавляют их в дерево, если они не создают цикл.

Корневой узел, заданный как пара, разделенная запятой, состоящая из 'Root' и индекса узла или имени узла. Корневым узлом по умолчанию является 1.

  • Если 'Method' является 'dense' (значение по умолчанию), то корневой узел является стартовым узлом.

  • Если 'Method' является 'sparse', то корневой узел используется только, чтобы вычислить pred, вектор узлов-предшественников.

Можно задать корневой узел в любом из этих форматов:

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

Тип минимального дерева охвата, заданного как пара, разделенная запятой, состоящая из 'Type' и одна из опций в таблице.

ОпцияОписание
'tree'

Только одно дерево возвращено. Дерево содержит корневой узел.

'forest'

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

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

свернуть все

Минимальное дерево охвата, возвращенное как объект graph.

Узлы-предшественники, возвращенные как вектор индексов узла. pred(I) является индексом узла предшественника узла I. Условно, pred(rootNode) = 0. Если Type является 'tree', то pred(I) = NaN для всех узлов I, которые не находятся в том же компоненте как корневой узел.

pred задает направленную версию минимального дерева охвата со всеми ребрами, направленными далеко от корневого узла.

Больше о

свернуть все

Минимальное дерево охвата

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

Для графиков с равным весом ребра все деревья охвата являются минимальными деревьями охвата, начиная с пересечения узлов n требует ребер n-1.

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

| |

Введенный в R2015b

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