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)
