Description Usage Arguments Details Value References See Also
msTreePrim
computes a minimum cost spanning tree of
an undirected graph with Prim's algorithm.
1 | msTreePrim(nodes, arcs, start.node = 1)
|
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. |
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.
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. |
Prim, R. C. (1957), "Shortest Connection Networks And Some Generalizations", Bell System Technical Journal, 36 (1957), pp. 1389-1401
A more general function getMinimumSpanningTree.
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.