# Graph data structure in Typescript

The graph data structure is a fundamental concept in computer science, and it is used in various domains such as social networks, transportation systems, and computer networks.

A graph is a **collection of nodes connected by edges**, where each node represents an entity, and each edge represents a relationship between two entities. In this article, we will discuss how to implement a graph data structure in TypeScript and perform BFS and DFS on it.

### Implementing Graph Data Structure in TypeScript

In TypeScript, we can implement a graph data structure using classes. We will define two classes, namely Node and Graph, to represent a node and a graph, respectively.

The Node class will have two properties: value and neighbors:

* `value` property will hold the value of the node.
    
* `neighbors` property will hold an array of neighboring nodes.
    

```typescript
class Node {
  value: any;
  neighbors: Node[];

  constructor(value: any) {
    this.value = value;
    this.neighbors = [];
  }

  addNeighbor(node: Node) {
    this.neighbors.push(node);
  }
}
```

The Graph class will have one property, `nodes`, which will hold an array of all the nodes in the graph. It will also have two methods, `addNode` and `addEdge`, to add a node and an edge to the graph, respectively.

```typescript
class Graph {
  nodes: Node[];

  constructor() {
    this.nodes = [];
  }

  addNode(value: any) {
    const node = new Node(value);
    this.nodes.push(node);
  }

  addEdge(source: Node, destination: Node) {
    source.addNeighbor(destination);
    destination.addNeighbor(source);
  }
}
```

### Graph traversal: Breadth-First Search (BFS)

Breadth-First Search (BFS) is a graph traversal algorithm that visits all the nodes of a graph in breadth-first order, i.e., it visits all the nodes at the same level before moving to the next level. To perform BFS, we need to maintain a queue of nodes to be visited.

```typescript
function bfs(startNode: Node) {
  const visited: Set<Node> = new Set();
  const queue: Node[] = [];

  visited.add(startNode);
  queue.push(startNode);

  while (queue.length > 0) {
    const currentNode = queue.shift()!;
    console.log(currentNode.value);

    for (const neighbor of currentNode.neighbors) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}
```

In the above code, we first initialize a set called visited to keep track of the nodes that have been visited. We also initialize a queue to hold the nodes to be visited. We add the `startNode` to both visited and queue. Then, while the queue is not empty, we dequeue the currentNode, print its value, and add its unvisited `neighbors` to the queue and visited set.

Here's a visual cue for the code above:

![Breadth First Search (BFS) in Graphs](https://www.codesdope.com/staticroot/images/algorithm/bfs8.png align="left")

### Graph-traversal: Depth-First Search (DFS)

Depth-First Search (DFS) is a graph traversal algorithm that visits all the nodes of a graph in depth-first order, i.e., it visits all the nodes in a branch before moving to the next branch. To perform DFS, we need to maintain a stack of nodes to be visited.

```typescript
function dfs(startNode: Node) {
  const visited: Set<Node> = new Set();
  const stack: Node[] = [];

  stack.push(startNode);

  while (stack.length > 0) {
    const currentNode = stack.pop()!;
    if (!visited.has(currentNode)) {
      console.log(currentNode.value);
      visited.add(currentNode);

      for (const neighbor of currentNode.neighbors) {
        stack.push(neighbor);
      }
    }
  }
}
```

We first initialize a set called visited to keep track of the nodes that have been visited. We also initialize a stack to hold the nodes to be visited. We push the `startNode` to the stack. Then, while the stack is not empty, we pop the currentNode from the stack, print its value, add it to the visited set, and push its unvisited `neighbors` to the stack.

Here's a visual cue:

![animation of dfs](https://www.codesdope.com/staticroot/images/algorithm/dfs.gif align="left")

### Let' see all of it in action

Consider the following problem:

```markdown
Given a graph, find the shortest path between two nodes using BFS.                    
```

To solve this problem, we can use the BFS algorithm provided in this article. We start by adding the start node to the visited set and queue. Then, while the queue is not empty, we dequeue the `currentNode`, check if it is the target node, and return the path if it is. Otherwise, we add its unvisited `neighbors` to the queue and visited set, and update the path.

Here's the typescript code to solve the problem above:

```typescript
function shortestPath(graph: Graph, start: Node, target: Node) {
  const visited: Set<Node> = new Set();
  const queue: [Node, Node[]][] = [];

  queue.push([start, [start]]);

  while (queue.length > 0) {
    const [currentNode, currentPath] = queue.shift()!;

    if (currentNode === target) {
      return currentPath;
    }

    visited.add(currentNode);

    for (const neighbor of currentNode.neighbors) {
      if (!visited.has(neighbor)) {
        queue.push([neighbor, [...currentPath, neighbor]]);
      }
    }
  }
  return null;
}
```