R 手写BFS搜索算法

背景/概述

广度优先搜索的总体思路是从图中的一点(让我们称之为a)开始，然后将所有邻居添加到未探索点的列表中(我们称之为frontier点).然后逐个判断列表，对于每个点，您将该点的不可见邻居添加到队列的末尾，依此类推，直到您找到您正在寻找的点(可以是特定的点b，或者满足您设置的特定标准的任何点)，或者您已经用完了所有地方(因为您已经探索了所有地方).

整理数据

首先，我要清理一下数据.我创建了一个数据帧，其中只有存在的人(没有空):

people_df <- df2 %>% 
    filter(person != "empty") %>%
    select(person, country)

然后，我将Country Connections数据帧df转换为数据帧neighbours_df，它为我提供每个点的邻居.根据数据帧的 struct ，它有(例如)一行:

      from         to
country_31 country_79

但没有一个是相反的，即

      from         to
country_79 country_31

因此，我交换了列，将反转的列添加到第一列的末尾，并将每个点的邻居分组到一个列表中，以使其更整洁:

reversed_df <- df %>% 
    mutate(new_from = to, to = from, from = new_from) %>% 
    select(from, to)

neighbours_df <- df %>% 
    bind_rows(reversed_df) %>% 
    filter(from != to) %>%
    group_by(from) %>%
    summarise(to = list(to))
    
#          from                            to
# 1    country_1   c("country_8", "country_92")

实施

breadth_first_search <- function(person, neighbours_df, people_df) {
  # get the country of the person
    starting_country <- people_df$country[people_df$person == person]

  # initialise the visited list 
    visited <- c()

  # initialise the frontier with the starting point
    frontier <- list()
    frontier[[starting_country]] <- 0

  # initialise distance from start variable (so we can print how far we are from the start)
    distance_from_start <- 0

  # while the frontier is not empty
    while (length(frontier) > 0) {

      # get the first element of the frontier
        current <- names(frontier)[1]

      # get the distance from current to start
        distance_from_start <- frontier[[1]]
      
      print(paste0("Current point: ", current, " (", distance_from_start, " steps from start)"))

      # remove the first element of the frontier (the one we just selected)
        frontier <- frontier[-1]

        # if the current point is in the country column of our `people_df` (i.e. someone lives there), and it's not the starting country, return the person who lives there
        if (current %in% people_df$country && current != starting_country) {
          found_person <- people_df$person[people_df$country == current]
          print(paste0("Found person: ", found_person, ", " , distance_from_start , " steps from start, in country ", current))
            return(found_person)
        }

        # add the current point to the visited list
        visited <- c(visited, current)

        # get the neighbors of the current point
        neighbs <- neighbours_df$to[neighbours_df$from == current][[1]]

        # add the neighbors to the frontier if they haven't been visited already
        neighbs <- neighbs[!neighbs %in% visited]
        frontier <- c(frontier, setNames(rep(distance_from_start + 1, length(neighbs)), neighbs))
        }
    # if we search through all the points, and didn't find anyone, return NA
    return(NA)
}

print(breadth_first_search("person_R", neighbours_df, people_df))
# [1] "person_J"

参考资料/更多信息

我被Red Blob Games(this other piece的伙伴，它很好地介绍了广度优先搜索(以及其他类似的图形搜索算法，如A*))从this article抄袭了相当多的内容.如果你想更全面地了解它们是如何工作的，BFS的缺点和优点，和/或想要玩一些互动的东西，我建议你go 看看！