手动实现BFS搜索算法：寻找网络图中最近人员

1. 构建匹配场景的示例图 #

library(igraph)
library(visNetwork)

# 创建100个国家节点
countries <- paste0("country_", 1:100)
# 生成20个人员并分配唯一国家
people <- paste0("person_", LETTERS[1:20])
assigned_countries <- sample(countries, 20)
# 建立人员-国家映射表
person_country_map <- setNames(assigned_countries, people)

# 创建随机无向图（边密度适中，模拟真实连接）
g <- sample_gnm(n = 100, m = 250, directed = FALSE)
V(g)$name <- countries
# 给节点添加人员属性：有人员的节点赋值，其余为NA
V(g)$person <- ifelse(V(g)$name %in% assigned_countries, 
                      names(person_country_map)[match(V(g)$name, person_country_map)], 
                      NA)

2. 手动实现BFS核心逻辑 #

manual_bfs <- function(start_person, person_country_map, graph) {
  # 获取起点人员所在国家
  start_country <- person_country_map[start_person]
  cat("=== BFS搜索启动 ===\n")
  cat("起点人员：", start_person, " | 所在国家：", start_country, "\n\n")
  
  # 初始化搜索队列、已访问集合、搜索状态标记
  queue <- list(list(country = start_country, degree = 0))
  visited <- c(start_country)
  target_found <- FALSE
  
  while (length(queue) > 0 && !target_found) {
    # 取出队列头部节点（FIFO，保证按度数顺序搜索）
    current <- queue[[1]]
    queue <- queue[-1]
    current_country <- current$country
    current_degree <- current$degree
    
    cat("当前搜索半径（度数）：", current_degree, " | 正在检查国家：", current_country, "\n")
    
    # 检查当前国家是否存在其他人员（排除起点自身）
    current_person <- V(graph)[name == current_country]$person
    if (!is.na(current_person) && current_person != start_person) {
      cat("✅ 找到最近关联人员：", current_person, " | 所在国家：", current_country, "\n")
      cat("关联度数：", current_degree, "\n")
      target_found <- TRUE
      break
    }
    
    # 获取当前国家的所有邻居节点
    neighbors <- neighbors(graph, current_country, mode = "all")$name
    # 过滤已访问过的邻居，避免重复搜索
    unvisited_neighbors <- setdiff(neighbors, visited)
    
    if (length(unvisited_neighbors) > 0) {
      cat("  发现未访问邻居：", paste(unvisited_neighbors, collapse = ", "), "\n")
      # 将未访问邻居加入队列，度数+1
      for (neigh in unvisited_neighbors) {
        queue <- c(queue, list(list(country = neigh, degree = current_degree + 1)))
        visited <- c(visited, neigh)
      }
    } else {
      cat("  无未访问邻居\n")
    }
    cat("\n")
  }
  
  if (!target_found) {
    cat("❌ 未找到任何其他关联人员\n")
  }
}

# 执行搜索（以person_A为起点）
manual_bfs("person_A", person_country_map, g)

3. 可视化验证（可选） #

# 准备可视化节点与边数据
nodes <- data.frame(id = V(g)$name, 
                    label = ifelse(is.na(V(g)$person), V(g)$name, paste(V(g)$name, "\n(", V(g)$person, ")")),
                    color = ifelse(is.na(V(g)$person), "#97C2FC", "#FF7F7F")) # 有人员的节点标红
edges <- as.data.frame(get.edgelist(g))
colnames(edges) <- c("from", "to")

# 生成交互式可视化图
visNetwork(nodes, edges, height = "800px") %>%
  visOptions(highlightNearest = TRUE)

关键逻辑说明 #

• 队列管理：用列表模拟FIFO队列，确保严格按照1度、2度...的顺序逐层搜索
• 已访问集合：记录已搜索过的国家，避免重复遍历和循环
• 实时输出：每步打印当前搜索度数、检查的国家及发现的邻居，清晰展示搜索过程
• 终止条件：一旦找到第一个非起点的人员立即停止，保证结果是最近的关联者

内容的提问来源于stack exchange，提问作者stats_noob