rust - 创建对父节点的引用时，借入的值的生命周期不足

Question

我正在尝试学习Rust，为此，我决定实现深度优先搜索算法。
到目前为止，我具有以下Node结构:

#[derive(Debug)]
pub struct Node<'a> {
    parent: Option<&'a Node<'a>>,
    position: crate::entities::Position,
}

如您所见，每次创建节点时，都会引用其父节点。
现在，我有了dfs算法:

pub fn dfs<'a>(maze: &crate::entities::Maze) -> Node<'static> {
    let mut traversed = Vec::new();
    let mut frontier = Vec::new();
    let mut seen: HashSet<crate::entities::Position> = HashSet::new();

    let parent = Node {
        parent: None,
        position: maze.start // position is just a holder for row and column
    };
    frontier.push(parent);

    loop {
        if frontier.is_empty() {
            panic!("No solution found!")
        }
        let current: Node<'static> = frontier.pop().expect("There must be a node here");
        let position = current.position;
        if current.position == maze.exit {
            break current;
        } else {
            if !seen.contains(&current.position) {
                let neighbours = maze.get_neighbours(current.position).iter().map(|pos| Node {
                    parent: Some(&current), // this line is not compiling
                    position: *pos
                }).collect::<Vec<Node>>();
                frontier.append(&mut neighbours); 
                traversed.push(current);
            }
        }
        seen.insert(position);
    }
}

但是我收到一个编译错误:

27 |                     parent: Some(&current),
   |                                   ^^^^^^^ borrowed value does not live long enough

我该如何解决？

Answer 1

您的基本问题是节点的管理。注意，首先由矩阵创建一个节点，然后将其放入frontier中，最后将其移至traversed中。这意味着您不能使用对节点的引用，因为它们可能会移动，从而使引用无效。
解决方案是拥有节点的中央存储，然后在引用它们时使用索引。当然，这与Node的实现不太兼容，但是您可以将其更改为使用索引而不是对父级的引用。