图的搜索

广度和深度

Posted by Jow on August 2, 2019

目录

  1. 广度优先搜索
  2. 深度优先搜索

尝试的学习所有的优秀的算法结构,这样你才能够理解算法的魅力

广度优先搜索

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

  • 到一个地方经理最少节点
  • 能否到达某个节点
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    
    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出来,直到栈中没有节点了。 深度优先算法的应用:

  • 算一个图的深度
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    
    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)