Part 2 in the series Graph Algorithms, Implementing Breadth First Search (BFS) in Typescript. For a primer on BFS and it's applications and procedure, read Part 1: Graph Algorithms: Breadth First Search (BFS) here.

# Data Structures

For convenience and clarity of code, the following types were implmenented for use in BFS

```
// data structure that represents an edge,
// this really does nothing for the algorithm directly but provides type safety.
export type Edge = [src: number, dest: number];
export class Graph {
// array of arrays to represent adjacency list
private adjList: number[][];
constructor(edges: Edge[], N: number) {
//initialize the adjacency list with the size of the graph (number of nodes)
this.adjList = Array.from({ length: N }, () => []);
for (const [src, dest] of edges) {
this.adjList[src].push(dest);
this.adjList[dest].push(src);
}
}
public getAdjacent(index: number): number[] | null {
return this.adjList[index] ? this.adjList[index] : null;
}
}
// this is not truly necessary to do for the algorith,
// moreso a nicety becuase there is no such thing as a queue in javascript,
// only arrays.
// This class encapsulates FIFO behavior to clean up the BFS implementation
export class Queue<T> {
private stack: T[] = [];
public push(element: T): void {
this.stack.push(element);
}
public pop(): T | null {
const el = this.stack.shift();
return el ?? null;
}
public empty(): boolean {
return this.stack.length === 0;
}
}
```

# Iterative Implementation of BFS

```
export const iterativeBFS = (
graph: Graph,
v: number,
discovered: boolean[]
): void => {
//create the queue
const q = new Queue<number>();
// mark the root as having been discovered
discovered[v] = true;
// push the starting index into the queue
q.push(v);
while (q.empty() !== true) {
// while the queue isn't empty, take from it
v = q.pop()!;
//print the node to the console
console.log("node:", v);
// get the adjacent nodes to v
const adjacent = graph.getAdjacent(v);
if (adjacent) {
adjacent.forEach((u) => {
if (!discovered[u]) {
discovered[u] = true;
q.push(u);
}
});
}
}
};
```

## Output

```
const edges: Edge[] = [
[1, 2],
[1, 3],
[1, 4],
[2, 5],
[2, 6],
[5, 9],
[5, 10],
[4, 7],
[4, 8],
[7, 11],
[7, 12],
];
// vertex 0, 13, and 14 are single nodes
const N = 15;
(() => {
let graph = new Graph(edges, N);
let discovered = Array.from({ length: N }, () => false);
Array.from({ length: N }, (_, idx) => {
if (!discovered[idx]) {
iterativeBFS(graph, idx, discovered);
}
});
})();
```

```
$ npx tsc && node dist
node: 0
node: 1
node: 2
node: 3
node: 4
node: 5
node: 6
node: 7
node: 8
node: 9
node: 10
node: 11
node: 12
node: 13
node: 14
```

# Recursive Implementation of BFS

```
export const recursiveBFS = (
graph: Graph,
queue: Queue<number>,
discovered: boolean[]
) => {
// if our queue is empty, bail
if (queue.empty()) {
return;
}
// retrieve the node off of the top of the queue
const v = queue.pop()!;
// print the node to the console
console.log("node:", v);
// get the adjacent nodes to the current index
const adjacent = graph.getAdjacent(v);
// if there are adjacent nodes...
if (adjacent) {
// filter down to the nodes that have not yet been discovered
adjacent
.filter((u) => !discovered[u])
.forEach((u) => {
// for each undiscovered node, mark it "visited"/discovered
discovered[u] = true;
//push the discovered node onto the queue for it's edges to be traced
queue.push(u);
});
}
recursiveBFS(graph, queue, discovered);
};
```

## output

```
const edges: Edge[] = [
[1, 2],
[1, 3],
[1, 4],
[2, 5],
[2, 6],
[5, 9],
[5, 10],
[4, 7],
[4, 8],
[7, 11],
[7, 12],
];
// vertex 0, 13, and 14 are single nodes
const N = 15;
(() => {
// create the graph from edges
let graph = new Graph(edges, N);
// create an array to track discovered nodes
let recursiveDiscovered = Array.from({ length: N }, () => false);
//queue of nodes that need neighbor discovery
let recursiveQueue = new Queue<number>();
Array.from({ length: N }, (_, idx) => {
// for each of our nodes, we're not yet discovered, call the recursive bfs
if (!recursiveDiscovered[idx]) {
recursiveDiscovered[idx] = true;
recursiveQueue.push(idx);
recursiveBFS(graph, recursiveQueue, recursiveDiscovered);
}
});
})();
```

```
recursive approach:
node: 0
node: 1
node: 2
node: 3
node: 4
node: 5
node: 6
node: 7
node: 8
node: 9
node: 10
node: 11
node: 12
node: 13
node: 14
```