diff --git a/src/visit/traversal.rs b/src/visit/traversal.rs
index 3a40e7c..672a688 100644
--- a/src/visit/traversal.rs
+++ b/src/visit/traversal.rs
@@ -86,7 +86,6 @@
     /// the dfs from a particular node.
     pub fn move_to(&mut self, start: N)
     {
-        self.discovered.visit(start);
         self.stack.clear();
         self.stack.push(start);
     }
@@ -95,14 +94,15 @@
     pub fn next<G>(&mut self, graph: G) -> Option<N>
         where G: IntoNeighbors<NodeId=N>,
     {
-        if let Some(node) = self.stack.pop() {
-            for succ in graph.neighbors(node) {
-                if self.discovered.visit(succ) {
-                    self.stack.push(succ);
+        while let Some(node) = self.stack.pop() {
+            if self.discovered.visit(node) {
+                for succ in graph.neighbors(node) {
+                    if !self.discovered.is_visited(&succ) {
+                        self.stack.push(succ);
+                    }
                 }
+                return Some(node);
             }
-
-            return Some(node);
         }
         None
     }
diff --git a/tests/graph.rs b/tests/graph.rs
index 8cfbb49..758007d 100644
--- a/tests/graph.rs
+++ b/tests/graph.rs
@@ -118,6 +118,35 @@
     assert_eq!(Dfs::new(&gr, i).iter(&gr).count(), 3);
 }
 
+#[test]
+fn dfs_order() {
+    let mut gr = Graph::new();
+    let h = gr.add_node("H");
+    let i = gr.add_node("I");
+    let j = gr.add_node("J");
+    let k = gr.add_node("K");
+    gr.add_edge(h, i, ());
+    gr.add_edge(h, j, ());
+    gr.add_edge(h, k, ());
+    gr.add_edge(i, k, ());
+    gr.add_edge(k, i, ());
+
+    //      H
+    //    / | \
+    //   I  J  K
+    //    \___/
+    //
+    // J cannot be visited between I and K in a depth-first search from H
+
+    let mut seen_i = false;
+    let mut seen_k = false;
+    for node in Dfs::new(&gr, h).iter(&gr) {
+        seen_i |= i == node;
+        seen_k |= k == node;
+        assert!(!(j == node && (seen_i ^ seen_k)), "Invalid DFS order");
+    }
+}
+
 
 #[test]
 fn bfs() {