Как рассчитать минимальное остовное дерево в R - PullRequest
Новая
       64

Как рассчитать минимальное остовное дерево в R

8 голосов
/ 07 января 2020

Приведен график из N вершин и расстояние между ребрами вершин, сохраненное в кортеже T1 = (d11, d12, …, d1n) to Tn = (dn1, dn2, …, dnn). Найдите минимальное остовное дерево этого графа, начиная с вершины V1. Кроме того, выведите общее расстояние, необходимое для перемещения этого сгенерированного дерева. 

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)

Буквально, я понятия не имею, как создать граф из n вершин в R.

I искал в гугле но я не понял как подойти к вышеуказанной проблеме.

Пожалуйста, помогите мне.

1 Ответ

4 голосов
/ 27 марта 2020

Ваш вопрос не соответствует названию - вы после создания графика не MST? Если у вас есть график, как говорит @ user20650, само MST становится простым.

Создать график размером n очень просто, но существует множество сложностей, связанных с тем, какие узлы связаны, и их весами (расстояниями), о которых вы нам не говорите. , так что это действительно базовая c иллюстрация.

Если предположить, что все узлы связаны со всеми другими узлами (полный график), мы можем использовать make_full_graph. Если это не так, вам нужны данные, чтобы сказать, какие узлы подключены, или использовать случайный график. 

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

Следующая проблема - расстояния. Вы не предоставили нам никакой информации о том, как распределяются эти расстояния, но мы можем продемонстрировать, как они распределяются по графику. Здесь я просто использую случайные равномерные [0-1] числа: 

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

Random graph

Следующий бит - это просто само MST, используя minimum.spanning.tree: 

mst <-  minimum.spanning.tree(g)

Выход mst выглядит следующим образом: 

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
...