Function BuildParentsFromAdjacencyList

src/colmap/math/spanning_tree.cc:49–75

Build parent pointers from adjacency list using BFS from root.

// Build parent pointers from adjacency list using BFS from root.
void BuildParentsFromAdjacencyList(
    const std::vector<std::vector<int>>& adjacency_list,
    int root,
    std::vector<int>& parents) {
  const int num_nodes = static_cast<int>(adjacency_list.size());
  parents.assign(num_nodes, -1);
  parents[root] = root;

  std::vector<char> visited(num_nodes, false);
  visited[root] = true;

  std::queue<int> queue;
  queue.push(root);

  while (!queue.empty()) {
    const int current = queue.front();
    queue.pop();

    for (const int neighbor : adjacency_list[current]) {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        parents[neighbor] = current;
        queue.push(neighbor);
      }
    }
  }
}

SpanningTree ComputeSpanningTreeInternal(
    int num_nodes,