So berechnen Sie den minimalen Spannbaum in R.

8

Gegeben ist ein Graph von N Eckpunkten und der Abstand zwischen den Kanten der im Tupel gespeicherten Eckpunkte T1 = (d11, d12, …, d1n) to Tn = (dn1, dn2, …, dnn). Finden Sie einen minimalen Spannbaum dieses Diagramms ab dem Scheitelpunkt V1 heraus. Drucken Sie auch die Gesamtstrecke aus, die zum Reisen dieses generierten Baums erforderlich ist.

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)

Ich habe buchstäblich keine Ahnung, wie man einen Graphen von n Eckpunkten in R erstellt.

Ich habe in Google gesucht, aber ich habe nicht verstanden, wie ich mich dem obigen Problem nähern soll.

Bitte hilf mir.

r minimum-spanning-tree Magie
quelle
Haben Sie das igraphPaket oder diese Frage oder diese Funktion überprüft ?
Bretauv
Eigentlich hatte ich kein Diagramm. Muss ich ein Diagramm mit n Eckpunkten erstellen ? Ein bisschen verwirrt mit der Frage
Magie
Ich denke, wir können den minimalen Spannbaum berechnen, wenn wir ein Diagramm haben. Wie bekomme ich ein N- Eckpunkt-Diagramm, das das Szenario wie in Frage darstellt?
Magie
1
Ich denke du kannst es einfach benutzen mst(g)aber vielleicht auch mst(g, weights = E(g)$weights)?
user20650
1
sum(E(mg)$weight), wo mgist das minimale Spanning Tree-Diagramm
user20650

Antworten:

4

Ihre Frage scheint nicht mit dem Titel übereinzustimmen - Sie sind nach der Grafikerstellung nicht der MST? Sobald Sie ein Diagramm haben, wie @ user20650 sagt, ist das MST selbst einfach.

Es ist einfach, ein Diagramm der Größe n zu erstellen , aber es gibt eine Menge Komplexität darüber, welche Knoten verbunden sind und welche Gewichte (Abstände) Sie uns nicht mitteilen. Dies ist also eine wirklich grundlegende Illustration.

Wenn wir davon ausgehen, dass alle Knoten mit allen anderen Knoten verbunden sind (vollständige Grafik), können wir verwenden make_full_graph. Ist dies nicht der Fall, benötigen Sie entweder Daten, um anzugeben, welche Knoten verbunden sind, oder Sie verwenden ein Zufallsdiagramm.

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

Das nächste Problem sind die Entfernungen. Sie haben uns keine Informationen darüber gegeben, wie diese Entfernungen verteilt sind, aber wir können die Zuordnung zum Diagramm demonstrieren. Hier verwende ich nur zufällige einheitliche [0-1] Zahlen:

# 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)

Zufällige Grafik

Das nächste Bit ist nur das MST selbst, wobei Folgendes verwendet wird minimum.spanning.tree:

mst <-  minimum.spanning.tree(g)

Die Ausgabe mstsieht folgendermaßen aus:

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
David_O
quelle
Ich weiß auch nicht, wie Entfernungen berechnet werden, deshalb bin ich verwirrt. Ich habe die vollständige Frage gestellt. Sie gaben nur so viele Informationen. Und ich bin neu in diesem MST- Thema.
Magie
Wir können dabei nicht helfen. Wenn Sie über n Knoten hinaus keine Informationen zur Diagrammstruktur erhalten haben , können Sie nur mit einigen Annahmen eine allgemeine Antwort geben. Sie könnten zufällige Diagramme und eine andere Verteilung der Kantenlängen verwenden, und der Code würde immer noch die Antwort geben
David_O
Ja, ich weiß, dass es ohne Grafik- und Entfernungsinformationen schwierig ist, zu helfen. Mit diesen Informationen user20650hat mir geholfen. Das genügt.
Magie
Ihre Antwort ist übrigens nützlich für mich, weil ich gelernt habe, wie man ein Diagramm in R erstellt. Vielen Dank.
Magie