主要内容

minspantree

그래프의최소신장트리(最小生成树)

페이지내모두축소

구문

T = minspantree (G)
T = minspantree (G、名称、值)
(T, pred) = minspantree (___）

설명

예제

T= minspantree (G）는 그래프G에대한최소신장트리(最小生成树)T를반환합니다。

예제

T= minspantree (G，名称,值）는하나이상의이름-값쌍의수로지정된추가옵션을사용합니다。예를들어，minspantree (G,‘法’,‘稀疏’)는최소신장트리를계산하는데크루스칼알고리즘(克鲁斯卡算法)을사용합니다。

예제

［T，pred) = minspantree (___）는위에열거된구문에나와있는입력，수중하나를사용하여선행노드로구성된벡터pred도반환합니다。

예제

모두 축소

라이브스크립트열기

가중치간선이있는정육면체그래프를생성하고플로팅합니다。

S = [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 = (s t重量);p =情节(G,“EdgeLabel”, G.Edges.Weight);

图中包含一个axes对象。axes对象包含一个graphplot类型的对象。

그래프의최소신장트리를계산하고그래프위에플로팅합니다。T는G와동일한노드를갖지만간선은일부만갖습니다。

(T, pred) = minspantree (G);突出(p T)

图中包含一个axes对象。axes对象包含一个graphplot类型的对象。

라이브스크립트열기

여러성분을갖는그래프를생성하고플로팅합니다。

s = {“一个”“一个”“一个”“b”“b”“c”“e”“e”“f”“f”“f”“f”‘g’‘g’};t = {“b”“c”' d '“c”' d '' d '“f”‘g’‘g’“h”“我”“j”“我”“j”};图G = (s, t);p =情节(G,“布局”，“分层”）;

图中包含一个axes对象。axes对象包含一个graphplot类型的对象。

노드我에서시작하여그래프에대한최소신장포레스트를구합니다。플롯에서결과로생성된포레스트를강조시합니다。그래프노드이름이최소신장트리그래프로이월됩니다。

(T, pred) = minspantree (G,“类型”，“森林”，“根”findnode (G,“我”));突出(p T)

图中包含一个axes对象。axes对象包含一个graphplot类型的对象。

선행노드로구성된벡터pred를사용하여최소신장포레스트의유방향버전을생성합니다。이트리에있는모든간선은각성분의루트노드(노드.我와一个에서나가는방향입니다。

rootedTree =有向图(pred (pred ~ = 0),找到(pred ~ = 0), [], G.Nodes.Name);情节(rootedTree)

图中包含一个axes对象。axes对象包含一个graphplot类型的对象。

입력수

모두 축소

입력그래프로，图객체로지정됩니다。图를사용하면무방향图객체를생성할수있습니다。

예:图G =(1、2)

이름-값수

선택적，수쌍을Name1 = Value1,…,以=家으로지정합니다。여기서的名字은，수이름이고价值는대응값입니다。이름-값。

R2021a이전릴리스에서는쉼를사용하여각이름과값을구분하고的名字을따옴로묶으십시오。

예:(T, pred) = minspantree (G,‘法’,‘稀疏’)

최소신장트리알고리즘으로，“方法”와함께，에나와있는옵션중하나가쉼，에나와있는옵션중하나가쉼，로구분되어지정됩니다。

옵션 설명
“密集”(디폴트값) 프림알고리즘(普里姆算法)。이알고리즘은루트노드에서시작하며그래프를순회하면서트리에간선을추가합니다。
“稀疏” 크루스칼알고리즘(Kruskal的算法)。이알고리즘은가중치를기준으로모든간선을정렬한후순환을생성하지않는간선을트리에추가합니다。

루트노드로，“根”와함께노드덱스또는노드이름이쉼로구분되어지정됩니다。디폴트루트노드는1입니다。

  • “方法”가“密集”(디폴트값)이면루트노드가시작노드입니다。

  • “方法”가“稀疏”이면루트노드는선행노드로구성된벡터pred를계산하는데에만사용됩니다。

루트노드는다음형식중하나로지정할수있습니다。

값 예제
스칼라노드，덱스 1
문자형벡터노드이름 “一个”
字符串형스칼라노드이름 “一个”

최소신장트리유형으로，“类型”과함께，에나와있는옵션중하나가쉼，에나와있는옵션중하나가쉼，로구분되어지정됩니다。

옵션 설명
“树”

단일트리만반환됩니다。이트리는루트노드를포함합니다。
“森林”

최소신장트리로구성된포레스트(森林)가반환됩니다。다시말해서，“森林”를지정하면그래프의모든연결성분에대한최소신장트리를계산할수있습니다。

출력수

모두 축소

최소신장트리로，图객체로반환됩니다。

선행노드로，노드，덱스로구성된벡터로반환됩니다。pred(我)는노드我의선행노드에대한노드，덱스입니다。일반적으로，pred (rootNode) = 0입니다。类型이“树”이면루트노드와동일한성분에있지않은모든노드我에대해pred (I) = NaN입니다。

pred는루트노드에서나가는방향의모든간선을사용하여최소신장트리의유방향버전을지정합니다。

세부 정보

모두 축소

최소신장트리(最小生成树)

연결된그래프에대해,신장트리는그래프의모든노드를연결하는부분그래프이지만,순환을포함하지않습니다。지정된그래프에대해많은신장트리가있을수있습니다。각각의간선에가중치를할당하는방식으로여러신장트리에해당간선의총가중치에해당하는숫자가할당됩니다。그런다음，총가중치가가장작은간선이있는신장트리가최소신장트리가됩니다。

간선가중치가동일한그래프의경우모든신장트리가최소신장트리가되는데，이는n개노드를순회하려면n - 1개의간선이필개의간선이필。

버전 내역

R2015b에개발됨

참고 항목

||