A collection of graph search algorithms implemented in TypeScript for studying

GraphAlgorithm.ts

//=========================- - Search Algorithms - -=========================//

//- Binary Search

//Binary Search assumes that the input array is already sorted in ascending order.
function binarySearch(arr: number[], target: number, start = 0, end = arr.length - 1) {
  if (start > end) return -1

  const mid = Math.floor((start + end) / 2)

  if (arr[mid] === target) return mid

  if (arr[mid] < target) {
    start = mid + 1

    return binarySearch(arr, target, start, end)
  }

  if (arr[mid] > target) end = mid - 1

  return binarySearch(arr, target, start, end)
}

const arr = [0,10,20,30,40,50,60,70,80,90,100]
const target = 90
const index = binarySearch(arr, target)

console.log(index)

/*
- Depth-First Search (DFS)
 is a graph traversal algorithm that visits all vertices of a graph or a tree by exploring as far as possible along
 each branch before backtracking. The DFS algorithm starts at a root node and visits all of the connected nodes in the
 graph or tree until all nodes have been visited.

Aplications
 - Finding connected components: DFS can be used to find connected components in a graph. A connected component is a
 subgraph where all vertices are connected to each other.

 - Topological sorting: DFS can be used to perform a topological sorting of a graph. Topological sorting is the process
 of arranging the vertices of a directed acyclic graph (DAG) in a linear order such that for every directed edge (u, v),
 vertex u comes before vertex v in the ordering.

 - Finding cycles: DFS can be used to find cycles in a graph. A cycle is a path in a graph that starts and ends at the same vertex.

 - Pathfinding: DFS can be used to find a path between two vertices in a graph. The algorithm can be modified to stop
 when the target vertex is found, and then backtrack to find the path.

 - Maze solving: DFS can be used to solve mazes. The algorithm can be used to explore all possible paths until the end of the maze is reached.

 - Tree traversal: DFS can be used to traverse trees, such as binary trees or n-ary trees. The algorithm can be used to
 visit all nodes in the tree in a particular order, such as pre-order, in-order, or post-order.
 */

class Graph {
  nodes: Map<string, GraphNode>

  constructor() {
    this.nodes = new Map()
  }

  addNode(name: string) {
    const node = new GraphNode(name)

    this.nodes.set(name, node)
  }

  addEdge(start: string, end: string, bothWays?: boolean) {
    const startNode = this.nodes.get(start)
    const endNode = this.nodes.get(end)

    if(!startNode || !endNode) return

    startNode.adjacentNodes.push(endNode)

    if(bothWays) endNode.adjacentNodes.push(startNode)
  }

  dfs(startName: string) {
    const startNode = this.nodes.get(startName)
    const visited = new Set<GraphNode>()

    this.dfsHelper(startNode, visited)
  }

  dfsHelper(node: GraphNode | undefined, visited: Set<GraphNode>) {
    if(!node) {
      return
    }

    visited.add(node)

    for (const adjacentNode of node.adjacentNodes) {
      if (!visited.has(adjacentNode)) {
        this.dfsHelper(adjacentNode, visited)
      }
    }
  }

  getReachableNodes(startName: string) {
    const startNode = this.nodes.get(startName)
    const visited = new Set<GraphNode>()

    this.dfsHelper(startNode, visited)

    return [ ...visited ]
  }

  topologicalSort() {
    const visited = new Set<GraphNode>()
    const path: GraphNode[] = []

    for (const node of this.nodes.values()) {
      if (!visited.has(node)) {
        this.dfsTopologicalSortHelper(node, visited, path)
      }
    }

    return path.reverse()
  }

  dfsTopologicalSortHelper(node: GraphNode, visited: Set<GraphNode>, stack: GraphNode[]) {
    visited.add(node)

    for (const adjacentNode of node.adjacentNodes) {
      if (!visited.has(adjacentNode)) {
        this.dfsTopologicalSortHelper(adjacentNode, visited, stack)
      }
    }

    stack.push(node)
  }

  findCycles() {
    const visited = new Set<GraphNode>()
    const cycleNodes = new Set<GraphNode>()
    const path = new Set<GraphNode>()

    for (const node of this.nodes.values()) {
      if (!visited.has(node)) {
        this.dfsCycleHelper(node, visited, cycleNodes, path)
      }
    }

    return Array.from(cycleNodes)
  }

  dfsCycleHelper(node: GraphNode, visited: Set<GraphNode>, cycleNodes: Set<GraphNode>, path: Set<GraphNode>) {
    visited.add(node)
    path.add(node)

    for (const adjacentNode of node.adjacentNodes) {
      if (path.has(adjacentNode)) {
        // Found a cycle!
        cycleNodes.add(adjacentNode)
      } else if (!visited.has(adjacentNode)) {
        this.dfsCycleHelper(adjacentNode, visited, cycleNodes, path)
      }
    }

    path.delete(node)
  }

  findLongestPath(startName: string, endName: string) {
    const startNode = this.nodes.get(startName)
    const endNode = this.nodes.get(endName)

    if(!startNode || !endNode) return

    const visited = new Set<GraphNode>()

    return this.dfsFindLongestPathHelper(startNode, endNode, visited)
  }

  dfsFindLongestPathHelper(node: GraphNode, endNode: GraphNode, visited: Set<GraphNode>) {
    visited.add(node)

    if (node === endNode) return [node]

    let longestPath: GraphNode[] = []

    for (const adjacentNode of node.adjacentNodes) {
      if (!visited.has(adjacentNode)) {
        const path = this.dfsFindLongestPathHelper(adjacentNode, endNode, visited)

        if (path.length > longestPath.length) {
          longestPath = [node, ...path]
        }
      }
    }

    return longestPath
  }

  /*
  Breadth-First Search (BFS) is a tree traversal algorithm that visits all the nodes in a tree in a breadth-first manner.
  This means that it visits all the nodes at the same level before moving on to the nodes at the next level.

  The algorithm works by starting at a given node (often called the root node) and visiting all its adjacent nodes.
  It then visits all the adjacent nodes of these nodes, and so on, until all nodes have been visited.

  BFS uses a queue data structure to keep track of the nodes to visit. The algorithm adds the starting node to the queue
  and then enters a loop that continues until the queue is empty. In each iteration of the loop, the algorithm dequeues
  the next node from the queue, visits it, and adds its unvisited adjacent nodes to the queue.

  One of the main advantages of BFS is that it can be used to find the shortest path between two nodes in an unweighted
  graph or tree. Since BFS visits nodes in a breadth-first manner, it is guaranteed to find the shortest path between two nodes if it exists.

  Overall, BFS is a useful algorithm for traversing trees and graphs and is commonly used in a wide range of applications,
  such as network routing, web crawlers, and AI search algorithms.
*/

  //breadth-first search algorithm
  bfsfindShortestPath(startName: string, endName: string) {
    const startNode = this.nodes.get(startName)
    const endNode = this.nodes.get(endName)

    if (!startNode || !endNode) return

    const visited = new Set<GraphNode>()
    const queue: [GraphNode, GraphNode[]][] = [[startNode, []]]

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

      if (visited.has(currentNode)) {
        continue
      }

      visited.add(currentNode)

      const newPath = [...currentPath, currentNode]

      if (currentNode === endNode) {
        return newPath
      }

      for (const adjacentNode of currentNode.adjacentNodes) {
        if (!visited.has(adjacentNode)) {
          queue.push([adjacentNode, newPath])
        }
      }
    }

    return null
  }
}

class GraphNode {
  name: string
  adjacentNodes: GraphNode[]

  constructor(name: string) {
    this.name = name
    this.adjacentNodes = []
  }

  getName = () => this.name
}

// Example usage:
const graph = new Graph()
graph.addNode("A")
graph.addNode("B")
graph.addNode("C")
graph.addNode("D")
graph.addNode("E")

graph.addEdge("A", "B")
graph.addEdge("B", "D")
graph.addEdge("A", "C")
graph.addEdge("C", "D")
graph.addEdge("D", "E")
graph.addEdge("D", "A")
graph.addEdge("E", "C")

graph.dfs("A")
console.log(graph.getReachableNodes("A").map(x => x.getName()))
console.log(graph.topologicalSort().map(x => x.getName()))
console.log(graph.findCycles().map(x => x.getName()))
console.log(graph.findLongestPath("A", "C")?.map(x => x.getName()))
console.log(graph.bfsfindShortestPath("A", "C")?.map(x => x.getName()))