minspantree

그래프의 최소 신장 트리(Minimum Spanning Tree)

구문

T = minspantree(G)

T = minspantree(G,Name,Value)

[T,pred] = minspantree(___)

설명

T = minspantree(G)는 그래프 G에 대한 최소 신장 트리(Minimum Spanning Tree) T를 반환합니다.

T = minspantree(G,Name,Value)는 하나 이상의 이름-값 쌍의 인수로 지정된 추가 옵션을 사용합니다. 예를 들어, minspantree(G,'Method','sparse')는 최소 신장 트리를 계산하는 데 크루스칼 알고리즘(Kruskal’s Algorithm)을 사용합니다.

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

예제

정육면체 그래프의 최소 신장 트리(Minimum Spanning Tree)

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

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)

지정된 루트 노드 기준 최소 신장 포레스트(Spanning Forest)

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

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를 사용하면 무방향 graph 객체를 생성할 수 있습니다.

예: G = graph(1,2)

이름-값 인수

선택적 인수 쌍을 Name1=Value1,...,NameN=ValueN으로 지정합니다. 여기서 Name은 인수 이름이고 Value는 대응값입니다. 이름-값 인수는 다른 인수 뒤에 와야 하지만, 인수 쌍의 순서는 상관없습니다.

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

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

Method — 최소 신장 트리(Minimum Spanning Tree) 알고리즘

'dense' (디폴트 값) | 'sparse'

최소 신장 트리 알고리즘으로, 'Method'와 함께 표에 나와 있는 옵션 중 하나가 쉼표로 구분되어 지정됩니다.

옵션	설명
'dense'(디폴트 값)	프림 알고리즘(Prim’s Algorithm). 이 알고리즘은 루트 노드에서 시작하며 그래프를 순회하면서 트리에 간선을 추가합니다.
'sparse'	크루스칼 알고리즘(Kruskal’s Algorithm). 이 알고리즘은 가중치를 기준으로 모든 간선을 정렬한 후 순환을 생성하지 않는 간선을 트리에 추가합니다.

Root — 루트 노드

1 (디폴트 값) | 노드 인덱스 | 노드 이름

루트 노드로, 'Root'와 함께 노드 인덱스 또는 노드 이름이 쉼표로 구분되어 지정됩니다. 디폴트 루트 노드는 1입니다.

• 'Method'가 'dense'(디폴트 값)이면 루트 노드가 시작 노드입니다.

• 'Method'가 'sparse'이면 루트 노드는 선행 노드로 구성된 벡터인 pred를 계산하는 데에만 사용됩니다.

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

값	예제
스칼라 노드 인덱스	1
문자형 벡터 노드 이름	'A'
string형 스칼라 노드 이름	"A"

Type — 최소 신장 트리(Minimum Spanning Tree) 유형

'tree' (디폴트 값) | 'forest'

최소 신장 트리 유형으로, 'Type'과 함께 표에 나와 있는 옵션 중 하나가 쉼표로 구분되어 지정됩니다.

옵션	설명
'tree'	단일 트리만 반환됩니다. 이 트리는 루트 노드를 포함합니다.
'forest'	최소 신장 트리로 구성된 포레스트(Forest)가 반환됩니다. 다시 말해서, 'forest'를 지정하면 그래프의 모든 연결성분에 대한 최소 신장 트리를 계산할 수 있습니다.

출력 인수

T — 최소 신장 트리(Minimum Spanning Tree)

graph 객체

최소 신장 트리로, graph 객체로 반환됩니다.

pred — 선행 노드

벡터

선행 노드로, 노드 인덱스로 구성된 벡터로 반환됩니다. pred(I)는 노드 I의 선행 노드에 대한 노드 인덱스입니다. 일반적으로, pred(rootNode) = 0입니다. Type이 'tree'이면 루트 노드와 동일한 성분에 있지 않은 모든 노드 I에 대해 pred(I) = NaN입니다.

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

세부 정보

최소 신장 트리(Minimum Spanning Tree)

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

간선 가중치가 동일한 그래프의 경우 모든 신장 트리가 최소 신장 트리가 되는데, 이는 n개 노드를 순회하려면 n-1개의 간선이 필요하기 때문입니다.

확장 기능

스레드 기반 환경
MATLAB®의 backgroundPool을 사용해 백그라운드에서 코드를 실행하거나 Parallel Computing Toolbox™의 ThreadPool을 사용해 코드 실행 속도를 높일 수 있습니다.

버전 내역

R2015b에 개발됨

참고 항목

graph | shortestpath | conncomp