JS Data Structs

Graph

Undirected

// Create a new undirected graph
var g = Graph()
g.addEdge(0, 1);
g.addEdge(0, 2); // add edges

// Another way to create a graph is from an ajacency matrix

var matrix = [
    [0, 1, 0, 0, 1],
    [1, 0, 1, 1, 1],
    [0, 1, 0, 1, 0],
    [0, 1, 1, 0, 1],
    [1, 1, 0, 1, 0],
]

g.fromAdjMatrix(matrix)

Directed

// Create a new directed graph
var g = Graph(true) // pass true
g.addEdge(0, 1);
g.addEdge(0, 2); // add edges

// OR
var matrix = [
    [0, 1, 0, 0, 1],
    [1, 1, 1, 1, 1],
    [0, 1, 0, 1, 0],
    [1, 1, 1, 0, 1],
    [1, 1, 1, 1, 0],
]

g.fromAdjMatrix(matrix, true)

// create a new graph
var g = Graph(true)

g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);

console.log(g.DFS(2)); 
// pass the starting node as a parameter
// returns an array containing the order of traversal

// create a new graph
var g = Graph(true)

g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);

console.log(g.BFS(2)); // pass the starting node as a parameter
// returns an array containing the order of traversal

Topological Sort

// Create a new graph
var g = Graph(true)
g.addEdge("A", "C");
g.addEdge("A", "B");
g.addEdge("A", "D");
g.addEdge("C", "D");
g.addEdge("D", "E");
g.addEdge("E", "F");
g.addEdge("B", "G"); 


console.log(g.topologicalSort());
// Returns the sorted array
// This returns only one of the many possible sorted orders

Note

Topological sort can only be done on Directed Acyclic Graphs(DAG).

Dijktra's Algorithm

This algorithm returns the shortest path from the start node to all other nodes in the graph


// Create a new graph

// The second parameter is the weighted property, which has to be true.
var g = Graph(false, true);

// Create a graph by adding edges
g.addEdge(0, 1, 4)
g.addEdge(0, 7, 8)
g.addEdge(1, 2, 8)
g.addEdge(1, 7, 11)
g.addEdge(2, 3, 7)
g.addEdge(2, 8, 2)
g.addEdge(2, 5, 4)
g.addEdge(3, 4, 9)
g.addEdge(3, 5, 14)
g.addEdge(4, 5, 10)
g.addEdge(5, 6, 2)
g.addEdge(6, 7, 1)
g.addEdge(6, 8, 6)
g.addEdge(7, 8, 7)

// OR
// Create a graph from an adjacency matrix
var matrix = [
    [0, 4, 0, 0, 0, 0, 0, 8, 0],
    [4, 0, 8, 0, 0, 0, 0, 11, 0],
    [0, 8, 0, 7, 0, 4, 0, 0, 2],
    [0, 0, 7, 0, 9, 14, 0, 0, 0],
    [0, 0, 0, 9, 0, 10, 0, 0, 0],
    [0, 0, 4, 14, 10, 0, 2, 0, 0],
    [0, 0, 0, 0, 0, 2, 0, 1, 6],
    [8, 11, 0, 0, 0, 0, 1, 0, 7],
    [0, 0, 2, 0, 0, 0, 6, 7, 0]
]

g.fromAdjMatrix(matrix)

// Pass the start node
console.log(g.dijkstra(0));
// Returns a hashmap of the distance of all nodes from the start node

← Trie →