minspantree

グラフの最小全域木

構文

T = minspantree(G)

T = minspantree(G,Name,Value)

[T,pred] = minspantree(___)

説明

T = minspantree(G) は、グラフ G の最小全域木 T を返します。

T = minspantree(G,Name,Value) は、1 つ以上の名前と値のペアの引数で指定された追加のオプションを使用します。たとえば、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)

入力引数

G — 入力グラフ

graph オブジェクト

入力グラフ。graph オブジェクトとして指定します。無向グラフ オブジェクトを作成するには、graph を使用します。

例: G = graph(1,2)

名前と値の引数

オプションの引数のペアを Name1=Value1,...,NameN=ValueN として指定します。ここで、Name は引数名で、Value は対応する値です。名前と値の引数は他の引数の後に指定しなければなりませんが、ペアの順序は重要ではありません。

R2021a より前では、コンマを使用して名前と値をそれぞれ区切り、Name を引用符で囲みます。

例: [T,pred] = minspantree(G,'Method','sparse')

Method — 最小全域木アルゴリズム

'dense' (既定値) | 'sparse'

最小全域木アルゴリズム。'Method' と、次の表のいずれかのオプションで構成されるコンマ区切りのペアとして指定します。

オプション	説明
'dense' (既定)	プリムのアルゴリズム。このアルゴリズムはルート ノードから開始し、グラフを通過しながら木にエッジを追加します。
'sparse'	クラスカルのアルゴリズム。このアルゴリズムは重みを基準にしてすべてのエッジを並べ替え、エッジが循環を作成しない場合にそのエッジを木に追加します。

Root — ルート ノード

1 (既定値) | ノード インデックス | ノード名

ルート ノード。'Root'、およびノード インデックスまたはノード名で構成されるコンマ区切りのペアとして指定します。既定のルート ノードは 1 です。

• 'Method' が 'dense' (既定) の場合、ルート ノードは開始ノードです。

• 'Method' が 'sparse' の場合、ルート ノードは先行ノードのベクトル pred の計算にのみ使用されます。

ルート ノードは次のいずれかの形式で指定できます。

値	例
スカラー ノード インデックス	1
文字ベクトルのノード名	'A'
string スカラーのノード名	"A"

Type — 最小全域木のタイプ

'tree' (既定値) | 'forest'

最小全域木のタイプ。'Type' と、次の表のいずれかのオプションで構成されるコンマ区切りのペアとして指定します。

オプション	説明
'tree'	単一の木のみが返されます。木はルート ノードを含みます。
'forest'	最小全域木の森が返されます。つまり、'forest' を指定すると、グラフ内のすべての連結要素の最小全域木が計算されます。

出力引数

T — 最小全域木

graph オブジェクト

最小全域木。graph オブジェクトとして返されます。

pred — 先行ノード

ベクトル

先行ノード。ノード インデックスのベクトルとして返されます。pred(I) は先行ノード I のノード インデックスです。慣例により、pred(rootNode) = 0 です。Type が 'tree' の場合、ルート ノードと同じ要素内にないすべてのノード I について pred(I) = NaN です。

pred は、最小全域木の指向バージョンを指定します。すべてのエッジがルート ノードから遠ざかる方向を向きます。

詳細

最小全域木

連結グラフの場合、全域木はグラフの各ノードを連結し、循環を含まない部分グラフです。任意のグラフについて、多くの全域木が存在します。各エッジに重みを割り当てることにより、異なる全域木にエッジの合計重みを示す値が割り当てられます。そして、最小全域木は、エッジの合計重みが最小の全域木です。

重みが等しいエッジからなるグラフでは、すべての全域木が最小全域木になります。これは、n 個のノードを通過するには n-1 本のエッジが必要だからです。

拡張機能

スレッドベースの環境
MATLAB® の backgroundPool を使用してバックグラウンドでコードを実行するか、Parallel Computing Toolbox™ の ThreadPool を使用してコードを高速化します。

バージョン履歴

R2015b で導入

参考

graph | shortestpath | conncomp