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:
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.
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.
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:
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.
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:
Let' see all of it in action
Consider the following problem:
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:
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;
}
