|
|
List = {}
--创建链表
function List.new(val)
return {pnext = nil, index=val}
end
--添加一个节点
function List.addNode(nodeParent, nodeChild)
nodeChild.pnext = nodeParent.pnext
nodeParent.pnext = nodeChild
return nodeChild
end
function searchPre()
road.rooms={}
--print(road.id)
--if road.id =='sld/xiaolu' or road.id =='sld/haitan' then map.rooms["sld/haitan"].ways["#toSld"]=nil end
if string.find(road.id,'sld') then map.rooms["sld/lgxroom"].ways["#outSld"]=nil end
local p_room = map.rooms[road.id].name
local p_dest = getLookCity(road.id)
local l_distance = 6
if job.name and (job.name=="clb" or job.name=='tdh' or job.name=='tmonk') and flag.times==1 then
l_distance = 2
end
if job.name and job.name=='xueshan' and flag.times==1 then
l_distance = 3
end
if p_dest==nil then
p_dest=job.area
end
local rooms = getAroundRooms(p_room,p_dest,l_distance,'all')
roomsnum=countTab(rooms)
--构造邻接表，用于递归搜索
--插入起始road.id
starttime=os.clock() --测试计算时间
newrooms = {}
for id in pairs(rooms) do
table.insert(newrooms,id)
end
myrt={}
for _,roomid in pairs(newrooms) do --插入房间链表
roomV = List.new(roomid)
local node = roomV
for k,v in pairs(newrooms) do --所有的房间id
for route,link_way in pairs(map.rooms[roomid].ways) do --当前id的出口
local routeLength = map.rooms[roomid]:length(route) --获取路径方向是否可达，返回false标示此路不通，那么这个方向的路就不插入出口链表
if routeLength then
if v==link_way then
node = List.addNode(node,List.new(k)) --插入节点生成第一个房间的出口链表
end
end
end
end
table.insert(myrt,roomV)
end
visited={}
for i=1 ,countTab(newrooms) do
visited[i]=false --初始化所有节点未曾访问
end
if not visited[1] then
FastDFS(myrt,1) --计算起点的连通图
end
for i=1 ,countTab(newrooms) do
if visited[i]==false then--未曾访问的节点测试一下跟第一个起点的连通性，如果能联通，则递归这个节点
local path, len = map:getPath(myrt[1].index,myrt[i].index)
if path then
FastDFS(myrt,i) --继续遍历指定的myrt[i]这个节点
messageShow("发现通路，遍历下一个节点！","red")
end
end
end
--messageShow("【"..job.name.."】深度优先计算结束，遍历【"..roomsnum.."】个房间，用时【"..os.clock()-starttime.."】秒","SandyBrown")
end
function FastDFS(myrt,i)
visited[i] = true --设置下标为I的顶点为已访问
--Note(myrt[i].index) --输出顶点信息
table.insert(road.rooms,myrt[i].index)
local p = myrt[i].pnext --下一个边表结点
if p==nil then return end
while p~=nil do
if(not visited[p.index]) then--如果是未访问的则递归
visited[p.index]=true
FastDFS(myrt,p.index)
end
p = p.pnext
end
end |
|
闽公网安备 35050202000162号 )
发表于 2017-4-26 13:16:53
