How to calculate minimum spanning tree in R

Question

Given a graph of N vertices and the distance between the edges of the vertices stored in tuple T1 = (d11, d12, …, d1n) to Tn = (dn1, dn2, …, dnn). Find out a minimum spanning tree of this graph starting from the vertex V1. Also, print the total distance travel needed to travel this generated tree.

Example:
For N =5 
T1 = (0, 4, 5, 7, 5)
T2 = (4, 0, 6, 2, 5)
T3 = (5, 6, 0, 2, 1)
T4 = (7, 2, 2, 0, 5)
T5 = (5, 5, 1, 5, 0)

Selection of edges according to minimum distance are:
V1 -> V2 = 4
V2 -> V4 = 2
V4 -> V3 = 2
V3 -> V5 = 1

Thus, MST is V1 -> V2 -> V4 -> V3 -> V5 and the distance travelled is 9 (4+2+2+1)

Literally,I don't have idea about how to create a graph of n vertices in R.

I searched in google but i didn't understand how to approach above problem.

Please,help me.

Answer 1

Your question doesn't seem to match the title - you're after the graph creation not the MST? Once you've got a graph, as @user20650 says, the MST itself is easy.

It is easy to create a graph of size n, but there is a whole lot of complexity about which nodes are connected and their weights (distances) that you don't tell us about, so this is a really basic illustration.

If we assume that all nodes are connected to all other nodes (full graph), we can use make_full_graph. If that isn't the case, you either need data to say which nodes are connected or use a random graph.

# create graph
n <- 5
g <- make_full_graph(n)

The next issue is the distances. You haven't given us any information on how those distances are distributed, but we can demonstrate assigning them to the graph. Here, I'll just use random uniform [0-1] numbers:

# number of edges in an (undirected) full graph is (n2 - n) /2 but
# it is easier to just ask the graph how many edges it has - this
# is more portable if you change from make_full_graph
n_edge <- gsize(g)
g <- set_edge_attr(g, 'weight', value=runif(n_edge))
plot(g)

The next bit is just the MST itself, using minimum.spanning.tree:

mst <-  minimum.spanning.tree(g)

The output mst looks like this:

IGRAPH dc21276 U-W- 5 4 -- Full graph
+ attr: name (g/c), loops (g/l), weight (e/n)
+ edges from dc21276:
[1] 1--4 1--5 2--3 2--5