图的搜索

广度优先搜索

广度优先搜索：所谓的广度优先搜索，就是从一张图中，选着一个节点，优先遍历这个节点的临近节点来找到自己想要的节点。在这里需要借助一种数据结构，那就是队列，首先将自己和临近节点入队，然后不断的让队列开头的节点出队检测，并让其临近节点入队，在这里我们要对已经检测过得节点打上标记，当队列为空或者找到节点遍历结束。广度优先算法的应用：

到一个地方经理最少节点

能否到达某个节点

persons = {
  you = { name = "you", friend = { "alice", "bob", "claire" } },
  bob = { name = "bob", friend = { "anuj", "peggy" } },
  alice = { name = "alice", friend = { "peggy" } },
  claire = { name = "claire", friend = { "thom", "jonny" } },
  anuj = { name = "anuj", friend = {} },
  peggy = { name = "peggy", friend = {} },
  thom = { name = "thom", friend = {} },
  jonny = { name = "jonny", friend = {} },
}
local result = {}
------@param persons      persons
local function graphTraverse(persons)
  local queue = {}
  table.insert(queue, persons.you.name)
  persons.you.tag = true
  while #queue > 0 do
      local person = table.remove(queue, 1)
      table.insert(result, person)
      for i, v in ipairs(persons[person].friend) do
          if not persons[v].tag then
              table.insert(queue, v)
              persons[v].tag = true
          end
      end
  end
end

深度优先搜索

深度优先搜索使用栈的方式来管理节点，遍历节点并把节点push到栈中，然后不断的访问压进来节点的临近节点，如果今个节点的没有可访问的额临近节点了，就pop出来，直到栈中没有节点了。深度优先算法的应用：

算一个图的深度

persons = {
  you = { name = "you", friend = { "alice", "bob", "claire" } },
  bob = { name = "bob", friend = { "anuj", "peggy" } },
  alice = { name = "alice", friend = { "peggy" } },
  claire = { name = "claire", friend = { "thom", "jonny" } },
  anuj = { name = "anuj", friend = {} },
  peggy = { name = "peggy", friend = {} },
  thom = { name = "thom", friend = {} },
  jonny = { name = "jonny", friend = {} },
}
local result = {}
local function getFriend(name)
  for i, v in ipairs(persons[name].friend) do
      if not persons[v].tag then
          return persons[v].name
      end
  end
  return nil
end
------@param persons      persons
local function graphTraverse(persons)
  local stack = {}
  table.insert(stack, persons.you.name)
  persons.you.tag = true
  table.insert(result, persons.you.name)
  while #stack > 0 do
      local person = stack[#stack]
      local name = getFriend(person)
      if name then
          persons[name].tag = true
          table.insert(stack, name)
          table.insert(result, name)
      else
          table.remove(stack, #stack)
      end
  end
end
graphTraverse(persons)

广度和深度

目录

广度优先搜索

深度优先搜索

CATALOG

FEATURED TAGS

FRIENDS