我成功地编写了一段代码,使用BFS算法遍历了所有的图节点。这是容易的部分 :)
现在我卡住了,无法得到两个节点之间的最短路径。
以下是我的代码:
function table.contains(table, element)
for _, value in pairs(table) do
if value == element then
return true
end
end
return false
end
queue = {stack={}}
function queue:en(e)
table.insert(self.stack, e)
end
function queue:de()
local e = self.stack[1]
self.stack[1] = nil
local new_stack = {}
for _, v in pairs(self.stack) do
table.insert(new_stack, v)
end
self.stack = new_stack
return e
end
function queue:count()
return #self.stack
end
function bfs()
start = 1
goal = 10
visited = {}
path = {}
graph = {}
graph[1] = {2,3,4}
graph[2] = {6,5,1}
graph[3] = {1}
graph[4] = {7,8}
graph[5] = {9,10,2}
graph[6] = {2}
graph[7] = {4,11,12}
graph[8] = {4}
graph[9] = {5}
graph[10] = {5}
graph[11] = {7}
graph[12] = {7}
queue:en(start)
table.insert(visited, start)
depth = 1
while queue:count() > 0 do
node = queue:de()
for _, exit in pairs(graph[node]) do
if not table.contains(visited, exit) then
table.insert(visited, exit)
if exit == goal then
print("GOAL : " .. exit)
do return end
end
if graph[exit] then
print("Node: " .. exit .. ", Depth: " .. depth)
queue:en(exit)
end
end
end
depth = depth + 1
end
end
bfs()
它生成的输出如下:
Node: 2, Depth: 1
Node: 3, Depth: 1
Node: 4, Depth: 1
Node: 6, Depth: 2
Node: 5, Depth: 2
Node: 7, Depth: 4
Node: 8, Depth: 4
Node: 9, Depth: 6
GOAL : 10
在当前的示例中,我需要获取从1到10的最短路径。