-- table 的字段 : name (结点的名称) , adj (与该结点邻接的结点集合)
function name2node( graph , name ) -- 将名称对应到结点邻
if not graph[name] then -- 结点不存在,创建新的结点
graph[name] = { name = name , adj = {} }
print(#graph)
end
return graph[name]
end
-- 构造一个图
function readgraph()
local graph = {}
for line in io.lines() do
local namefrom , nameto = string.match(line, "(%S+)%s+(%S+)" ) -- 切分行中的两个名称
-- 查找相应的结点
local from = name2node( graph , namefrom )
local to = name2node( graph , nameto )
from.adj[to] = true -- 将 to 添加到 from 的邻接集合
end
return graph
end
-- 采用深度优先遍历图
function findpath( curr , to , path , visited )
path = path or {}
visited = visited or {}25
if visited[curr] then -- 节点是否已经访问过了
return nil -- 这里没有路径
end
visited[curr] = true -- 将结点标记为已访问过了
path[ #path + 1 ] = curr -- 将其加到路径中
if curr == to then -- 最后的结点吗?
return path
end
for node in pairs( curr.adj ) do
local p = findpath(node , to , path , visited)
if p then return p end
path [#path] = nil -- 从路径中删除结点
end
end
function printpath( path ) -- 打印路径
for i = 1 , #path do
print(path[i].name)
end
end
g = readgraph()
a = name2node( g , "a" )
b = name2node( g , "b" )
p = findpath( a , b )
if p then printpath(p) end
25. Lua 图
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 1.当代种种事件不同于历史之处，在于我们不知道它们会产生什么后果。 2.经验和利益的偶然结合，往往会向人们揭示...
- 【姓名】宁静海 【派别】文魁派 【导师】袁文魁 王玉印 【分舵】闻鸡起舞 【舵主】刘丽琼 【导图说明】 ...
