DFSをスタックだけでしたい
再帰を使いましょう。
visitedとかは書いてないですが適宜使ってください。
graphに根付き木の隣接リストが入っていると仮定しています。
行き掛け順
普通にやる。
code:preorder.rs
let mut stack = vec!start; while let Some(u) = stack.pop() {
// 行き掛け順
stack.push(v);
}
}
帰りがけ順
二種類の値をスタックに入れる。
行き
帰り
code:postorder.rs
while let Some((u, preorder)) = stack.pop() {
if preorder {
stack.push((u, false));
// 行き
stack.push((v, true));
}
} else {
// 帰り
}
}
オイラーツアー
頂点を配列に入れてみる。
code:eulertour.rs
let mut vertices = vec![]; // 頂点の配列
while let Some((u, preorder)) = stack.pop() {
if preorder {
// 行き
vertices.push(u);
stack.push((u, false));
stack.push((v, true));
}
} else {
// 帰り
vertices.push(u);
}
}
一般のグラフの場合
visitedを使うことで単純にできる。(大工猫さんより)
行きか帰りかをvisited[u]がtrueかで区別している。
code:postorder.rs
let mut stack = vec!start; while let Some(u) = stack.pop() {
stack.push(u);
// 行き
continue;
}
stack.push(v);
}
} else {
// 帰り
}
}
code:eulertour.rs
let mut vertices = vec![];
let mut stack = vec!start; while let Some(u) = stack.pop() {
vertices.push(u);
continue;
}
stack.push(u);
stack.push(v);
}
}
}