minspantree
그래프의 최소 신장 트리(Minimum Spanning Tree)
설명
는 그래프 T
= minspantree(G
)G
에 대한 최소 신장 트리(Minimum Spanning Tree) T
를 반환합니다.
는 하나 이상의 이름-값 쌍의 인수로 지정된 추가 옵션을 사용합니다. 예를 들어, T
= minspantree(G
,Name,Value
)minspantree(G,'Method','sparse')
는 최소 신장 트리를 계산하는 데 크루스칼 알고리즘(Kruskal’s Algorithm)을 사용합니다.
예제
정육면체 그래프의 최소 신장 트리(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)가 반환됩니다. 다시 말해서, |
출력 인수
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
개의 간선이 필요하기 때문입니다.
버전 내역
R2015b에 개발됨
참고 항목
MATLAB 명령
다음 MATLAB 명령에 해당하는 링크를 클릭했습니다.
명령을 실행하려면 MATLAB 명령 창에 입력하십시오. 웹 브라우저는 MATLAB 명령을 지원하지 않습니다.
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)