Breadth First Traversal + Depth First Traversal implemented in Dart (Recursive and Iterative both)

bfs-dfs-dart.dart

import 'dart:collection';

const graph = {
  "a": ["b", "c"],
  "b": ["d"],
  "c": ["e"],
  "d": ["f"],
  "e": [],
  "f": [],
};

List<String> stack = ["a"];
Queue<String> queue = Queue();
void main() {
  queue.addFirst("a");
  print("Depth Iterative " + depthFirstSearchIterative().toString());
  print("Breadth Iterative " + breadthFirstSearchIterative().toString());
  print("Depth Recursive " + depthFirstSearchRecursive([], "a").toString());
  
  //have to use queue for recurive approach
  queue.addFirst("a");
  //Don't worry if it doesn't match the iterative output, both are valid traversal
  print("Breadth Recursive " + breadthFirstSearchRecursive([]).toString());
}

/// Iterative Methods

List<String> depthFirstSearchIterative() {
  List<String> output = [];
  while (stack.isNotEmpty) {
    List? branch = graph[stack.last]?.toList();
    output.add(stack.last);
    stack.removeLast();
    while (branch!.isNotEmpty) {
      stack.add(branch.last);
      branch.removeLast();
    }
  }
  return output;
}

List<String> breadthFirstSearchIterative() {
  List<String> output = [];
  while (queue.isNotEmpty) {
    List? branch = graph[queue.first]?.toList();
    output.add(queue.first);
    queue.removeFirst();
    while (branch!.isNotEmpty) {
      queue.add(branch.last);
      branch.removeLast();
    }
  }
  return output;
}

///Recursive Methods

List<String> depthFirstSearchRecursive(List<String> output, String root) {
  output.add(root);
  List? branch = graph[root]?.toList();
  for (final item in branch!) {
    depthFirstSearchRecursive(output, item);
  }
  return output;
}

List<String> breadthFirstSearchRecursive(List<String> output) {
  if(queue.isEmpty){
    return output;
  }
  String item  = queue.first;
  queue.removeFirst();
  output.add(item);
  for (final items in graph[item]!.toList()) {
    queue.add(items);
  }
  breadthFirstSearchRecursive(output);
  return output;
}