Main Content

이 번역 페이지는 최신 내용을 담고 있지 않습니다. 최신 내용을 영문으로 보려면 여기를 클릭하십시오.

minspantree

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

설명

예제

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

예제

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

예제

[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);

Figure contains an axes. The axes contains an object of type graphplot.

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

[T,pred] = minspantree(G);
highlight(p,T)

Figure contains an axes. The axes contains an object of type graphplot.

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

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');

Figure contains an axes. The axes contains an object of type graphplot.

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

[T,pred] = minspantree(G,'Type','forest','Root',findnode(G,'i'));
highlight(p,T)

Figure contains an axes. The axes contains an object of type graphplot.

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

rootedTree = digraph(pred(pred~=0),find(pred~=0),[],G.Nodes.Name);
plot(rootedTree)

Figure contains an axes. The axes contains an object of type graphplot.

입력 인수

모두 축소

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

예: G = graph(1,2)

이름-값 쌍의 인수

선택적으로 Name,Value 인수가 쉼표로 구분되어 지정됩니다. 여기서 Name은 인수 이름이고 Value는 대응값입니다. Name은 따옴표 안에 표시해야 합니다. Name1,Value1,...,NameN,ValueN과 같이 여러 개의 이름-값 쌍의 인수를 어떤 순서로든 지정할 수 있습니다.

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

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

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

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

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

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

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

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

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

옵션설명
'tree'

단일 트리만 반환됩니다. 이 트리는 루트 노드를 포함합니다.

'forest'

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

출력 인수

모두 축소

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

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

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

세부 정보

모두 축소

최소 신장 트리(Minimum Spanning Tree)

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

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

참고 항목

| |

R2015b에 개발됨