minspantree
Минимальное покрывающее дерево графика
Описание
T = minspantree(G)T, для графика G.
T = minspantree(G,Name,Value)minspantree(G,'Method','sparse') использует алгоритм Крускаля для вычисления минимального покрывающего дерева.
Примеры
Минимальное покрывающее дерево графика куба
Создайте и постройте график куба с взвешенными ребрами.
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)
