Spans

This option finds a minimum cost set of links that connect all the nodes together

Input

format

The first line specifies the calculation required. It must contain

format spans

Links

Column	Description
1	l for link
2	src node name
3	dst node name
4	cost

Start

Specify name of node used as the root of the spanning tree. If unspecified, an arbitrary root node will be selected.

Column	Description
1	s
2	root node name

Example Run

input
format spans
l 1 2 1
l 2 3 1
l 2 4 10
l 4 3 1

graph links
(2,1,1) (2,3,1) (2,4,10) (3,4,1)

span links
(2,1,1) (2,3,1) (3,4,1)

Algorithm

Prim's Algorithm

Performance

Vertex Count	Run time, seconds
1,000	0.1
10,000	4
100,000	410