Алгоритм Прима в R

Question

Я пытаюсь закодировать алгоритм Прима в R для университетского упражнения, я все настроил, но не могу понять, как закодировать реальный алгоритм, просто не решая его вручную каждый шаг.Вот мой код с примером графика:

C<-matrix(0,nrow=7,ncol=7)
C[1,2]<-5 #Manually inputting cost matrix for one way
C[1,3]<-6
C[1,4]<-7
C[2,3]<-2
C[2,5]<-6
C[2,6]<-3
C[4,7]<-5
C[4,6]<-9
C[3,4]<-7
C[6,7]<-7
C[5,6]<-2

for(j in 1:ncol(C)){ #This adds the cost of edges going the opposite ways
  for(i in 1:nrow(C)){
    C[i,j]<-C[j,i] #Sets the costs of the edges travelling the opposite way
  }
}


print(C) #Outputs the final matrix
A<-which(C==0,arr.ind=TRUE)
C[A]<-100 #This finds all the arcs that don't exist and gives them a value of 100 so they are never chosen for this specific example
print(C) #Outputs the new matrix C that is suitable for the algorithm

Prim<-function(C){
  tree<-matrix(0,nrow=6,ncol=2) #Creates a solution matrix with minimal cost arcs

  P<-which.min(C[1,]) #I'm starting the algorithm from 1 and looking for the minimal cost arc from 1
  tree[1,1]<-1
  tree[1,2]<-P #P is the vertex that joins to 1 with smallest length, I am adding it to the first row of the tree matrix

  vertices<-rep(0,7)
  vertices[1]<-1 #Making a list of vertices currently in the set so I can reject arcs that are already included
  vertices[2]<-P

Итак, я попробовал, если операторы отклоняют дуги, которые в данный момент находятся в дереве, но это не помогает, так как каждый раз, когда вы добавляете новую нужную вершину, вам нужнопроверить все дуги из новой вершины, чтобы увидеть, включены ли они уже.Любой совет будет оценен.

Answer 1

Я добавил к вашему коду ниже.Я использую матрицы для отслеживания соответствующих наборов (в дереве, а не в дереве), а затем также использую матрицу смежности затрат.Я рекомендую вам шаг за шагом запускать код и извлекать все, что вам нужно.Сейчас код отслеживает только каждое добавленное ребро (для связующего дерева это # ​​(точки) - 1).

# Your code from before
C = matrix(0,nrow=7,ncol=7)
C[1,2]<-5 #Manually inputting C matrix for one way
C[1,3]<-6
C[1,4]<-7
C[2,3]<-2
C[2,5]<-6
C[2,6]<-3
C[4,7]<-5
C[4,6]<-9
C[3,4]<-7
C[6,7]<-7
C[5,6]<-2

# Fill adjacency matrix up 
for(j in 1:ncol(C))
{ 
  # This adds the C of edges going the opposite ways
  for(i in 1:nrow(C))
  {
    # Sets the Cs of the edges travelling the opposite way
    C[i,j]<-C[j,i]
  }
}


# Manual first step of algorithm and then loop to generate spanning tree. 

# Num of points
num_pts = dim(C)[1]

# Makes df that will hold edges of tree (as pairs pt = from and to = next point in tree) 
points_paths = data.frame(pt = rep(0, num_pts - 1), to = rep(-1,num_pts - 1))

# Starting point 
pt0 = 1

# Set first point to starting position  
tree_pts = matrix(0, nrow = num_pts, ncol = num_pts)
non_pts = diag(num_pts)

# Push our first point into tree and take first point out of non tree set
tree_pts[pt0, pt0] = 1
non_pts[pt0, pt0] = 0 

# Nice matrix calculation to keep track of possible additions 
poss_edges = tree_pts %*% C %*% non_pts

# Find the minimum distance edge to add
edge = which(poss_edges == min(poss_edges[poss_edges > 0]), arr.ind = T)

# Add edge to tracker 
points_paths[1, ] = edge 

# Update matrices as needed 
tree_pts[edge[2], edge[2]] = 1
non_pts[edge[2], edge[2]] = 0

# Next we will repeat these calcs in a loop 
for(i in 2:(num_pts-1))
{
  # Get possible edges to add
  poss_edges = tree_pts %*% C %*% non_pts

  # Prim Algo step
  min_edges = which(poss_edges == min(poss_edges[poss_edges > 0]), arr.ind = T)

  # Only grab 1 edge of possible min edges
  edge = min_edges[1,]

  # Add to edge tracker
  points_paths[i,] = edge

  # Correct our matrices that track our "sets"
  tree_pts[edge[2], edge[2]] = 1
  non_pts[edge[2], edge[2]] = 0

}

Надеюсь, это поможет.