`minspantree`

Minimum spanning tree of a weighted graph.

Category: Mathematics > Graph and Network Algorithms

Syntax

T = minspantree(G)

Returns the spanning tree (or forest) of least total weight.

Description

A spanning tree connects all nodes using the fewest edges, and the minimum one does so with the smallest possible sum of weights. It is the cheapest way to wire a set of sites together. For a disconnected graph the result is a forest with one tree per component.

When several trees tie, any one of them may be returned.

Input arguments

G: An undirected graph. Edge weights, if present, are minimized; otherwise all edges weigh the same.

Output arguments

T: A graph with the nodes of G and a subset of its edges: numnodes(G) - c edges for c connected components, and no cycles.

Example

Cheapest network

G = graph([1 1 2 2 3 4], [2 3 3 4 4 5], [2 1 3 5 1 4]);
T = minspantree(G);
disp(T.Edges)
sum(T.Edges.Weight)

Output

    EndNodes    Weight
    ________    ______

     1    2       2   
     1    3       1   
     3    4       1   
     4    5       4   
ans = 8

minspantree