为什么我的 Rust StackDFS 实现会产生不正确的结果？

Question

我正在阅读 Luridas 关于算法的书，现在我在第 2 章尝试实现 StackDFS 函数。这个函数的目的是“访问”图中的每一个元素。

书中的算法：

StackDFS(G, node)→visited
//Input: G = (V,E), a graph
//node, the starting vertex in G
//Output: visited, an array of size |V | such that visited[i] is true if we
//have visited node i, false otherwise
  1 S ←CreateStack()
  2 visited ←CreateArray(|V |)
  3 for i ←0 to |V | do
  4 visited[i] ← false
  5 Push(S, node)
  6 while not IsStackEmpty(S) do
  7 c ←Pop(s)
  8 visited[c] ← true
     9 foreach v in AdjacencyList(G, c) do
       10 if not visited[v] then
           11 Push(S, v)
   12 return visited

我的代码：

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 index = 2;
    let mut visited = Vec::new();
    for i in 0..new.node_count() {
        visited.push(false);
    }
    StackDFS(&mut new, &index, &mut visited);
}

fn StackDFS<T>(G: &petgraph::Graph<T, (T, T), Undirected>, node: &usize, visited: &mut Vec<bool>) {
    let mut s: Vec<usize> = Vec::with_capacity(G.node_count());
    // for i in 0..G.node_count(){
    //   visited.push(false);
    //}
    s.push(*node);
    while s.is_empty() == false {
        let c = s.pop().unwrap();
        visited[c] = true;
        for el in G.neighbors(NodeIndex::new(*node)) {
            if visited[el.index()] == false {
                s.push(el.index());
            }
        }
    }
    println!("{:?}", visited);
}

我得到的输出：

[false, true, true, false, true]

我期望的输出：

[true, true, true, true, true]

我使用了 Vec 而不是堆栈，但我不认为这是问题所在，因为 Vec 可以提供与堆栈相同的功能。

Answer 1

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

您总是在访问同一个起始节点的邻居。你应该得到当前处理节点的邻居。

改进版本：

use petgraph::{graph::NodeIndex, Undirected}; // 0.6.0

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 index = 2;
    let mut visited = vec![false; new.node_count()];
    stack_dfs(&new, index, &mut visited);
}

fn stack_dfs<T>(
    g: &petgraph::Graph<T, (T, T), Undirected>,
    start_node: usize,
    visited: &mut Vec<bool>,
) {
    let mut s = Vec::with_capacity(g.node_count());
    s.push(start_node);

    while let Some(node) = s.pop() {
        visited[node] = true;
        for el in g.neighbors(NodeIndex::new(node)) {
            let idx = el.index();
            if !visited[idx] {
                s.push(idx);
            }
        }
    }

    println!("{:?}", visited);
}

为什么我的 Rust StackDFS 实现会产生不正确的结果？

Why does my Rust StackDFS implementation produce incorrect results?

algorithm

graph

rust