Options
All
  • Public
  • Public/Protected
  • All
Menu

Class Graph<T>

Implementation of a graph with methods for different traversal methods and other useful algorithms.

Type parameters

  • T = number

Hierarchy

  • Graph

Index

Constructors

Properties

Methods

Constructors

constructor

  • new Graph<T>(): Graph<T>

Properties

Private #_graph

#_graph: Map<T, Set<T>>

Methods

BFS

  • BFS(start: T, finish: T): false | T[]

  • Searches the graph for a path from the starting vertex to the ending vertex in breadth-first order. And returns the path if it exists.(excluding the finish vertex) Returns false if no path exists.

    example

    If the graph is like this, and we search for a path from 1 to 6, 

    1 => 2 => 7
    2 => 3 => 5
    3 => 4 => 6 => 1

    Then the path will be: [1, 2, 7, 3, 5, 4]

    see

    BFT

    see

    DFS

    see

    DFT

    Parameters

    • start: T

      Starting vertex

    • finish: T

      Ending vertex

    Returns false | T[]

BFT

  • BFT(start: T): T[]

  • Traverses the graph in breadth-first order and returns the vertices in the order they were visited.

    example

    If the graph is like this,

    1 => 2 => 7
    2 => 3 => 5
    3 => 4 => 6 => 1

    Then the traversal will be: [1, 2, 7, 3, 5, 4, 6]

    see

    BFS

    see

    DFS

    see

    DFT

    Parameters

    • start: T

      Starting vertex

    Returns T[]

DFS

  • DFS(start: T, finish: T): false | T[]

  • Searches the graph for a path from the starting vertex to the ending vertex in depth-first order. And returns the path if it exists.(excluding the finish vertex) Returns false if no path exists.

    example

    If the graph is like this, and we search for a path from 1 to 6, 

    1 => 2 => 7
    2 => 3 => 5
    3 => 4 => 6 => 1

    Then the path will be: [ 1, 7, 2, 5, 3 ]

    see

    BFT

    see

    DFS

    see

    DFT

    Parameters

    • start: T

      Starting vertex

    • finish: T

      Ending vertex

    Returns false | T[]

DFT

  • DFT(start: T): T[]

  • Traverses the graph in depth-first order and returns the vertices in the order they were visited.

    example

    If the graph is like this,

    1 => 3
    2 => 5 => 8
    3 => 2
    4 => 1
    5 => 7

    Then the DFT of 1 would be [ 1, 3, 2, 8, 5, 7 ]

    see

    BFS

    see

    DFS

    see

    DFT

    Parameters

    • start: T

      Starting vertex

    Returns T[]

addDirectedEdge

  • addDirectedEdge(from: T, to: T): void

  • Adds a directed edge from one vertex to another. If the vertices do not exist in the graph, they will be added.

    example
    const graph = new Graph<number>();
    graph.addVertex(1);
    graph.addVertex(2);
    graph.addVertex(3);
    graph.addDirectedEdge(1, 2);
    graph.addDirectedEdge(2, 3);
    graph.addDirectedEdge(3, 1);
    graph.getNeighbors(1); // Set { 2 }
    graph.getNeighbors(2); // Set { 3 }
    graph.getNeighbors(3); // Set { 1 }
    see

    addUndirectedEdge

    Parameters

    • from: T

      Starting vertex

    • to: T

      Ending vertex

    Returns void

addUndirectedEdge

  • addUndirectedEdge(v1: T, v2: T): void

  • Adds an undirected edge between two vertices. If the vertices do not exist in the graph, they will be added.

    example
    const graph = new Graph<number>();
    graph.addUndirectedEdge(1, 2);
    graph.addUndirectedEdge(2, 3);
    graph.addUndirectedEdge(3, 1);
    graph.getNeighbors(1); // Set { 2, 3 }
    graph.getNeighbors(2); // Set { 1, 3 }
    graph.getNeighbors(3); // Set { 1, 2 }
    see

    addDirectedEdge

    Parameters

    • v1: T
    • v2: T

    Returns void

addVertex

  • addVertex(vertex: T): void

  • Adds a vertex to the graph if it does not already exist.

    example
    const graph = new Graph<number>();
    graph.addVertex(1);
    graph.addVertex(2);
    graph.getNeighbors(1); // Set { }
    graph.getNeighbors(2); // Set { }

    Parameters

    • vertex: T

      Vertex to add

    Returns void

getNeighbors

  • getNeighbors(vertex: T): Set<T>

  • Returns the neighbors of a vertex.

    example
    const graph = new Graph<number>();
    graph.addVertex(1);
    graph.addVertex(2);
    graph.addVertex(3);
    graph.addUndirectedEdge(1, 2);
    graph.addUndirectedEdge(2, 3);
    graph.addDirectedEdge(3, 1);
    graph.getNeighbors(1); // Set { 2 }
    graph.getNeighbors(2); // Set { 3, 1 }
    graph.getNeighbors(3); // Set { 2, 1 }

    Parameters

    • vertex: T

      Vertex to get neighbors of

    Returns Set<T>

getVertices

  • getVertices(): Set<T>

  • Returns the set of vertices in the graph.

    example
    const graph = new Graph<number>();
    graph.addVertex(1);
    graph.addVertex(2);
    graph.addVertex(3);
    graph.getVertices(); // Set { 1, 2, 3 }
    see

    getNeighbors

    see

    addVertex

    Returns Set<T>

hasVertex

  • hasVertex(vertex: T): boolean

  • Returns true if the graph contains the vertex, false otherwise.

    example
    const graph = new Graph<number>();
    graph.addVertex(1);
    graph.hasVertex(1); // true
    graph.hasVertex(2); // false

    Parameters

    • vertex: T

      Vertex to check if it exists in the graph

    Returns boolean

Generated using TypeDoc, the 1/4/2022 at 10:37:56 PM