# <IAMSUMAN/> # 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> {
Graph() {
}

void insertEdge(T node1, T 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>();
while (queue.isNotEmpty) {
var currentNode = queue.removeFirst();
print("Visited: \$currentNode");
try {
throw EmptyException('Empty List..');
}
for (T neighbor in _adjacencyList![currentNode]!) {
if (!visited.contains(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 {
print("Visited Node: \$startNode");
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> {
Graph() {
}

void insertEdge(T node1, T node2) {
}

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

void DFS(T startNode, Set<T> visited) {
try {
print("Visited Node: \$startNode");
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.