msTreePrim: Minimum cost spanning tree with Prim's algorithm
Description
msTreePrim computes a minimum cost spanning tree of
an undirected graph with Prim's algorithm.
Usage
msTreePrim(nodes, arcs, start.node = 1)
Arguments
nodes
vector containing the nodes of the graph,
identified by a number that goes from $1$ to the
order of the graph.
arcs
matrix with the list of arcs of the graph.
Each row represents one arc. The first two columns
contain the two endpoints of each arc and the third
column contains their weights.
start.node
number associated with the first node
in Prim's algorithm. By default, node $1$ is the
first node.
Value
msTreePrim returns a list with:
tree.nodes
vector containing the nodes of the minimum cost spanning tree.
tree.arcs
matrix containing the list of arcs of the minimum cost spanning tree.
stages
number of stages required.
stages.arcs
stages in which each arc was added.
Details
Prim's algorithm was developed in 1930 by the mathematician
Vojtech Jarnik, later proposed by the computer scientist
Robert C. Prim in 1957 and rediscovered by Edsger Dijkstra
in 1959. This is a greedy algorithm that can find a minimum
spanning tree in a connected, weighted and undirected graph
by adding recursively minimum cost arcs leaving visited
nodes.
References
Prim, R. C. (1957), "Shortest Connection Networks And Some
Generalizations", Bell System Technical Journal, 36 (1957),
pp. 1389-1401