feat: add iterative and recursive dfs examples

1 files changed, 136 insertions, 0 deletions

diff --git a/examples/algorithms/dfs.zc b/examples/algorithms/dfs.zc
new file mode 100644
index 0000000..054a9d4
--- /dev/null
+++ b/examples/algorithms/dfs.zc
@@ -0,0 +1,136 @@
+import "std.zc"
+
+struct Graph {
+    num_vertices: int;
+    adj_list: Vec<Vec<int>>;
+}
+
+impl Graph {
+    fn new(vertices: int) -> Graph {
+        var g = Graph {
+            num_vertices: vertices,
+            adj_list: Vec<Vec<int>>::new()
+        };
+
+        for i in 0..vertices {
+            g.adj_list.push(Vec<int>::new());
+        }
+
+        return g;
+    }
+
+    fn add_edge(self, src: int, dest: int) {
+        if src < 0 || dest < 0 || src >= self.num_vertices || dest >= self.num_vertices {
+            return;
+        }
+
+        self.adj_list.data[src].push(dest);
+        self.adj_list.data[dest].push(src);
+    }
+
+    fn _dfs_recursive(self, vertex: int, visited: bool*, order: Vec<int>*) {
+        visited[vertex] = true;
+        order.push(vertex);
+
+        var neighbors = self.adj_list.data[vertex];
+        var neighbor_count = (int)neighbors.len;
+        for i in 0..neighbor_count {
+            var neighbor = neighbors.data[i];
+            if !visited[neighbor] {
+                self._dfs_recursive(neighbor, visited, order);
+            }
+        }
+    }
+
+    fn dfs_recursive(self, start: int) -> Vec<int> {
+        var order = Vec<int>::new();
+        if start < 0 || start >= self.num_vertices {
+            return order;
+        }
+
+        var visited = Vec<bool>::new();
+        defer visited.free();
+        for i in 0..self.num_vertices {
+            visited.push(false);
+        }
+
+        self._dfs_recursive(start, visited.data, &order);
+        return order;
+    }
+
+    fn dfs(self, start: int) -> Vec<int> {
+        var order = Vec<int>::new();
+        if start < 0 || start >= self.num_vertices {
+            return order;
+        }
+
+        var visited = Vec<bool>::new();
+        defer visited.free();
+        for i in 0..self.num_vertices {
+            visited.push(false);
+        }
+
+        var stack = Vec<int>::new();
+        defer stack.free();
+        stack.push(start);
+
+        while !stack.is_empty() {
+            var vertex = stack.pop();
+            if visited.data[vertex] {
+                continue;
+            }
+
+            visited.data[vertex] = true;
+            order.push(vertex);
+
+            var neighbors = self.adj_list.data[vertex];
+            var i = (int)neighbors.len - 1;
+            while i >= 0 {
+                var neighbor = neighbors.data[i];
+                if !visited.data[neighbor] {
+                    stack.push(neighbor);
+                }
+                i--;
+            }
+        }
+
+        return order;
+    }
+
+    fn free(self) {
+        for i in 0..self.num_vertices {
+            self.adj_list.data[i].free();
+        }
+        self.adj_list.free();
+    }
+}
+
+fn main() {
+    var g = Graph::new(6);
+    defer g.free();
+
+    g.add_edge(0, 1);
+    g.add_edge(0, 2);
+    g.add_edge(0, 3);
+    g.add_edge(1, 4);
+    g.add_edge(3, 5);
+
+    var order_rec = g.dfs_recursive(0);
+    defer order_rec.free();
+    var order_it = g.dfs(0);
+    defer order_it.free();
+
+    "DFS recursive order: "..;
+    for i in 0..(int)order_rec.len {
+        "{order_rec.data[i]} "..;
+    }
+    "";
+
+    "DFS iterative order: "..;
+    for i in 0..(int)order_it.len {
+        "{order_it.data[i]} "..;
+    }
+    "";
+
+    "Expected: 0 1 4 2 3 5";
+}