Breadth First Search (BFS) & Depth First Search (DFS) graph traversal using Generic Class with Null Safety | Dart

Breadth-first search (BFS) and Depth-first search (DFS) are two popular algorithms used for traversing and searching in a graph. Both algorithms can be implemented using a generic class in Dart with null safety.

Breadth First Search Graph Traversal Algorithm :

First, let's start with BFS. BFS is a traversing algorithm where you should start traversing from a selected node (source or starting node) and traverse the graph layer-wise, thus exploring the neighbor nodes (nodes that are directly connected to the source node).

Here is an implementation of BFS using a generic class in Dart:

class Graph<T> {
  Map<T, List<T>>? _adjacencyList;
  Graph() {
    _adjacencyList = Map();
  }

  void insertEdge(T node1, T node2) {
    _adjacencyList!.putIfAbsent(node1, () => []).add(node2);
  }

In this implementation, we have created a class called Graph, which is generic and can work with any data type. The class contains an adjacency list that stores the graph, and a function called addEdge() which adds an edge to the graph.

void BFS(T startNode) {
    var visited = Set<T>();
    var queue = Queue<T>();
    visited.add(startNode);
    queue.add(startNode);
    while (queue.isNotEmpty) {
      var currentNode = queue.removeFirst();
      print("Visited: $currentNode");
      try {
        if (_adjacencyList![currentNode] == null) {
          throw EmptyException('Empty List..');
        }
        for (T neighbor in _adjacencyList![currentNode]!) {
          if (!visited.contains(neighbor)) {
            visited.add(neighbor);
            queue.add(neighbor);
          }
        }
      } on EmptyException catch (e) {
        print(e);
      } catch (e) {
        print(e);
      }
    }
  }

The BFS() takes a source node as an argument and uses a queue to traverse the graph in a breadth-first manner.

Depth First Search Graph Traversal Algorithm :

Now, let's move on to DFS. DFS is a traversing algorithm where you should start traversing from a selected node (source or starting node) and traverse the graph in a depth-ward motion and uses stack as a data structure.

Here is an implementation of DFS

void DFS(T startNode, Set<T> visited) {
    try {
      visited.add(startNode);
      print("Visited Node: $startNode");
      if (_adjacencyList![startNode] == null) {
        throw EmptyException('No Elements');
      }
      for (T neighbour in _adjacencyList![startNode]!) {
        if (!visited.contains(neighbour)) {
          DFS(neighbour, visited);
        }
      }
    } on EmptyException catch (e) {
      print(e);
    } catch (e) {
      print(e);
    }
  }

The DFS() takes a source node as an argument and uses a set to keep track of the visited nodes and recursively traverses the graph in a depth-first manner.

In both of these examples, we have used the null-safety feature of Dart. The ?. and ?? operators are used to ensuring that the code is safe from null references and prevent runtime errors. The putIfAbsent() the method is used to insert a key-value pair in the map only if the key is not already present.

Here is the full code:

import 'dart:collection';

class Graph<T> {
  Map<T, List<T>>? _adjacencyList;
  Graph() {
    _adjacencyList = Map();
  }

  void insertEdge(T node1, T node2) {
    _adjacencyList!.putIfAbsent(node1, () => []).add(node2);
  }

  void BFS(T startNode) {
    var visited = Set<T>();
    var queue = Queue<T>();
    visited.add(startNode);
    queue.add(startNode);
    while (queue.isNotEmpty) {
      var currentNode = queue.removeFirst();
      print("Visited: $currentNode");
      try {
        if (_adjacencyList![currentNode] == null) {
          throw EmptyException('End..');
        }
        for (T neighbor in _adjacencyList![currentNode]!) {
          if (!visited.contains(neighbor)) {
            visited.add(neighbor);
            queue.add(neighbor);
          }
        }
      } on EmptyException catch (e) {
        print(e);
      } catch (e) {
        print(e);
      }
    }
  }

  void DFS(T startNode, Set<T> visited) {
    try {
      visited.add(startNode);
      print("Visited Node: $startNode");
      if (_adjacencyList![startNode] == null) {
        throw EmptyException('No Elements');
      }
      for (T neighbour in _adjacencyList![startNode]!) {
        if (!visited.contains(neighbour)) {
          DFS(neighbour, visited);
        }
      }
    } on EmptyException catch (e) {
      print(e);
    } catch (e) {
      print(e);
    }
  }
}

abstract class CustomException implements Exception {
  const CustomException([this.message]);
  final String? message;

  @override
  String toString() {
    String result = 'CustomException';
    if (message is String) return '$result: $message';
    return result;
  }
}

//extend custom exception class for EmptyException, you can make your own exception class like this.
class EmptyException extends CustomException {
  const EmptyException([String? message]) : super(message);
}

void main(List<String> args) {
  Graph graph = Graph<int>();
  graph.insertEdge(0, 1);
  graph.insertEdge(0, 2);
  graph.insertEdge(1, 2);
  graph.insertEdge(2, 0);
  graph.insertEdge(2, 3);
  graph.insertEdge(1, 4);
  graph.insertEdge(4, 3);
  graph.insertEdge(3, 3);
  graph.BFS(2);
  graph.DFS(2, <int>{});
}

## BFS
Visited: 2
Visited: 0
Visited: 3
Visited: 1
Visited: 4
## DFS
Visited Node: 2
Visited Node: 0
Visited Node: 1
Visited Node: 4
Visited Node: 3

Conclusion:

In conclusion, we have implemented BFS and DFS algorithms in Dart using a generic class with null safety. Using a generic class allows us to use these algorithms with any data type, and the null safety feature ensures that our code is robust and less prone to errors.