给出数组
[[“ 5”,“ A”,“ B”,“ C”,“ D”,“ F”,“ A-B”,“ A-C”,“ B-C”,“ C-D”,“ D-F”];
在这里我要对数组进行剪切的位置是5,在这种情况下,它会得到-
[[“ A-B”,“ A-C”,“ B-C”,“ C-D”,“ D-F”]
我需要找到A和F之间的最短路径
[[“ A-B”,“ A-C”,“ B-C”,“ C-D”,“ D-F”]
正确的输出为:A-C-D-F
任何解决此算法的JavaScript函数?
const findShort = (arrayStrings) => {
let index = arrayStrings.shift();
arrayStrings.splice(0, index)
let allChars = arrayStrings.join('-').split('-')
let lastItem = ''
let shortPath = []
allChars.map(item => {
if (item > lastItem) {
shortPath.push(item)
}
lastItem = item;
})
shortPath = [...new Set(shortPath)].join('-')
return shortPath; // returns "A-B-C-D-F" and should return A-C-D-F
}
let test = ["5", "A", "B", "C", "D", "F", "A-B", "A-C", "B-C", "C-D", "D-F"];
findShort(test)
[不确定通过数组中的cut
表示什么。我假设它是在数组中的索引5
之后,您具有一些可以在其中搜索最短路径的信息,它们是如您所示的边:
["A-B", "A-C", "B-C", "C-D", "D-F"]
,当可视化时将看起来像:
在那种情况下,您可以构建可以由Adjacency List表示的图形,并且可以使用该列表实现Breadth First Search以获取从起始顶点到目标顶点的最短路径。