发帖
雷达卡
这是我用R语言实现的步骤：
（1）用R语言把随机生成的二维矩阵行之间的距离计算出来记为length,将行标号记为i和j；
（2）将i和j处理成字符，作为路径结点Nodes；（处理方法有点笨拙）
（3）用最小生成树的R程序寻找点之间的最短路径；
程序
e <- read.csv("C:/Users/SYY/Desktop/example_1.csv")
dim(e)
colnames(e) <- c('start', 'end', 'length')
e$start <- as.character(e$start)
e$end <- as.character(e$end)
#最小生成树 -------------------------------------------------------------------
Nodes <- seq(1, m0+n, by = 1)##生成字符串数组，长度为m0+n-1
Nodes <- as.character(Nodes)
ori_trees<-hash()
#创建空哈希,顶点为键——值
for (i in Nodes){
.set(ori_trees, keys = i, values = i)
}
#将顶点存入哈希中
find_nodes<-function(x){
if(ori_trees[[x]]!=x){#双亲节点和当前节点不一致，说明这条边添加了minmum spanning tree
ori_trees[[x]] <- find_nodes(ori_trees[[x]])
#找到双亲节点未变化的点
return(ori_trees[[x]])
}
else{
return(x)
}
}
minimum_spanning_tree <- data.frame(start=character(),end=character(),length=numeric(),stringsAsFactors = F)
#定义最小生成树
t<-length(Nodes)-1
#定义循环次数，n为需要添加的边数=顶点数-1
s<-0
for(i in 1:(dim(e)[1])){
if(s==t){
break
}
if(find_nodes(e[i,1]) != find_nodes(e[i, 2])){
#双亲节点不一致
ori_trees[[find_nodes(e[i, 2])]] <- find_nodes(e[i, 1])#改变该顶点的双亲节点
minimum_spanning_tree <- rbind(minimum_spanning_tree, e[i, ])#将符合条件的边
s<-s+1
}
}
s
minimum_spanning_tree
问题是实现结果中有几个点的自由度超过2（一个点与3个点同时连接），如何限制结点的自由度不超过2呢？
> minimum_spanning_tree start end length6 2 3 0.7434 1 5 1.38315 5 6 1.6729 2 6 1.81713 4 5 2.015其中结点5出现了3次，如何限制每个结点最多出现2次呢？本人不是计算机专业的，还请各位大佬指点下，如何在这个程序基础上修改。
京公网安备 11010802022788号
