我的Rust StackDFS实现为何输出错误结果？

我看了你的代码和问题，马上发现了导致遍历不完整的关键问题——你在遍历邻居的时候一直用的是起始节点的邻居，而不是当前弹出的栈顶节点的邻居！这就是为什么部分节点没被访问到的原因。

1. 核心错误：错误的邻居遍历对象 #

看你StackDFS函数里的这段代码：

for el in G.neighbors(NodeIndex::new(*node)) {

这里的*node是传入的起始节点（比如你例子里的2），不管栈里弹出的是哪个节点c，你都在遍历起始节点2的邻居，而不是c的邻居。这就导致只有起始节点和它的直接邻居被标记，其他节点永远不会被加入栈中，自然无法被访问。

正确的做法应该是用当前弹出的节点c来获取邻居：

for el in G.neighbors(NodeIndex::new(c)) {

2. 其他可以优化的小细节 #

• 参数node不用传引用，直接传usize更简洁（它是Copy类型，不会有性能问题）
• 栈的初始化可以直接用Vec::new()，with_capacity只是预分配空间，不是必须的
• 可以去掉main里手动初始化visited的循环，改用vec![false; new.node_count()]更简洁

修正后的完整代码 #

use petgraph::graph::NodeIndex;
use petgraph::Undirected;

fn main() {
    let mut new = petgraph::Graph::<i32, (i32, i32), Undirected>::new_undirected();
    new.extend_with_edges(&[(0, 1), (0, 3), (1, 2), (2, 4)]);
    let start_node = 2;
    // 用vec!宏初始化visited，更简洁
    let mut visited = vec![false; new.node_count()];
    StackDFS(&new, start_node, &mut visited);
}

fn StackDFS<T>(G: &petgraph::Graph<T, (T, T), Undirected>, node: usize, visited: &mut Vec<bool>) {
    let mut s: Vec<usize> = Vec::new();
    s.push(node);
    
    while !s.is_empty() {
        let c = s.pop().unwrap();
        visited[c] = true;
        // 改为用当前弹出的节点c获取邻居
        for el in G.neighbors(NodeIndex::new(c)) {
            let el_idx = el.index();
            if !visited[el_idx] {
                s.push(el_idx);
            }
        }
    }
    
    println!("{:?}", visited);
}

运行结果 #

现在运行这段代码，输出会是[true, true, true, true, true]，和你的预期完全一致。另外要说明的是：你用Vec模拟栈是完全没问题的，pop()从尾部取元素正好符合栈的LIFO特性，这部分你的思路是正确的。

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