loading...
Cover image for Learn Data Structure and Algorithm in JavaScript | Part 17

Learn Data Structure and Algorithm in JavaScript | Part 17

edisonnpebojot profile image Edison Pebojot(👨‍💻) Updated on ・29 min read


Prerequisite (✋😐)

If you're reading this article right now, please considered to read our Part 01: Big-O Notation, Part 02: JavaScript Unique Part, Part 03: JavaScript Numbers to Part 16: Heaps

Part Table of Contents Description
01 Big-O Notation By the end of this chapter, you will understand how to analyze an implementation of an algorithm with respect to both time (execution time) and space (memory consumed).
02 JavaScript Unique Parts Big-O is important for analyzing and comparing the efficiencies of algorithms. The analysis of Big-O starts by looking at the code, and, applying the rules, applying the rules is because to simplify the Big-O notation linear or quadratic rule is not enough.
03 JavaScript Numbers This part 3 will focus on JavaScript number operations, number representation, Number objects, common number algorithms, and random number generation.
04 JavaScript Strings This part 4 will focus on strings, JavaScript String object, and the String object’s built-in functions. You will learn how to access, compare, decompose, and search strings for commonly used real-life purposes. In addition, the chapter will explore string encoding, decoding, encryption, and decryption.
05 JavaScript Arrays As a JavaScript developer, you will use the array often; it is the most commonly used data structure. Arrays in JavaScript come with a lot of built-in methods. By the end of this part, you will understand arrays and choose the right method
06 JavaScript Object This part will focus on what JavaScript objects are, how they are declared, and how their properties can be changed. In addition, this part will cover how JavaScript classes are implemented using prototypal inheritance. Also this part will be short.
07 JavaScript Memory Management A variable takes up some memory. In C, the programmer allocate and deallocate memory manually. In contrast, modern JavaScript engines have garbage collectors that delete unused variables. However, there are pitfalls(unexpected) that developers can fall into(❗) This part will show these unexpected and present techniques to help the garbage collector minimize the memory problems.
08 Recursion This part 8 introduces the concept of recursion and recursive algorithms(Remember they are different, we will discuss them later(😉)). We will also discuss the definition of recursion and fundamental rules for recursive algorithms.
09 Sets This part focuses on the concepts of sets from both a mathematical definition and on the implementation. Also, Common set operations, as well as their implementations, are covered in great detail (💡).
10 Searching and Sorting This part 10 focuses on searching and sorting for arrays. By the end of this part 10, you will understand how to use sorting and searching algorithms for arrays. Also, this article is a bit complicated for beginners, so as much as possible the visual aids is your friend (👀). (😃)
11 Hash Tables A hash table is a fixed-sized data structure in which the size is defined at the start. This part 11 explains how hash tables work, and the method of generating a unique key. By the end of this part 11, you will understand various hashing techniques and know how to implement a hash table. (😃)
12 Stacks and Queues This part 12 covers stacks and queues(pronounce as kyooz (🔈)) not (kwewe) okay? hehehe (😅); both are data structures used in the implementation of complex data structures. You'll learn what the stacks and queues are, how they're used, when they're used, and how to implement them (😃) Let's go! (🔥🔥🔥)
13 Linked Lists A linked list is a data structure in which each node (or element) points to another node. Unlike arrays, which have a fixed size, a linked list is a dynamic data structure. By the end of this part 13, you will understand how to implement and work with linked lists. And oh! (😮) There are two types of linked lists: singly (➡️) and doubly (↔️). Let’s examine the singly linked list first.(😃) Let's go! (🔥🔥🔥)
14 Caching Caching is the process of storing data into temporary memory so that it can be easily retrieved for later use if it is required again. As an example, a database keeps data cached to avoid re-reading the hard drive, and a web browser caches web images to avoid re-downloading. In this part 14, two caching techniques will discussed: LFU and LRU caching.
15 Trees A general tree data structure is composed of nodes with children nodes. The top node is called the root node. This part 15 will explore different types of trees such as binary trees, binary search trees, and self-balancing binary search trees. First, this part 15 will cover what trees are and how they are structured. Then, it will cover methods of traversing(crossing or taking a zigzag path) the tree data structure in detail. Finally, you will learn about binary search trees and self-balancing binary search trees to understand how to store searchable data. (😃)
16 Heaps A heap is an important data structure that returns the highest or lowest element in O(1) time. This part 16 will focus on explaining how heaps are implemented as well as how to work with them. One example is heap sort, which is a sorting algorithm based on heaps.
17 Graphs In this Part 17, you will learn graph basics, including fundamental terminology and graph types. The Part 17 will also cover working with these different graph types and methods of representing graphs in data structures. Finally, algorithms for traversing, searching, and sorting graphs are explored to solve problems such as finding the shortest path between two graph nodes. (👍)
18 Advance Strings Part 18 will cover more complex string algorithms than covered in the previous section. Now that you have heard of certain other data models or structures, they should be easier to comprehend. Specifically, Part 18 will focus on string searching algorithms. (😉)

Part 17: Graphs (😱 🔥 📈)

Alt Text

In this Part 17, you will learn graph basics, including fundamental terminology and graph types. The Part 17 will also cover working with these different graph types and methods of representing graphs in data structures. Finally, algorithms for traversing, searching, and sorting graphs are explored to solve problems such as finding the shortest path between two graph nodes. (👍)

Graphs (📈 📈)

Alt text

Graphs are visual representations of the connections
between objects. Such representations can be of many things and have different applications; Table 17-1 (below) shows some examples:

Application Item Connection
Web site Web page Links
Map Intersection Road
Circuit Component Wiring
Social media Person “Friendship”/connection
Telephone Phone number Landline
Table 17-1. Examples of Graph Applications

Figure 17-1 (below) shows two examples of simple graphs:
Alt Text

Before we delve into graphs too deeply, it is useful to introduce some basic terminology and concepts:

  • Vertex: A vertex is the node. In this chapter, a node will be noted as V for Big-O analysis. A vertex is represented using a circle, as shown in Figure 17-2 (below).

  • Edge: Graphically, it is the line between the vertices. It will be noted as E for Big-O analysis. An edge is represented using a line, as shown in Figure 17-2 (below):


Alt Text

Figure 17-2. Vertices and edges
  • Degree of vertex: refers to the number of edges on that vertex.

  • Sparse graph: A graph is considered sparse (or not dense) when only a small fraction of connections exist between vertices:

Alt Text

Figure 17-3. Sparse graph
  • Dense graph: A graph is considered dense when there are a lot of connections between vertices:

Alt Text

Figure 17-4. Dense graph
  • Cyclical graph: A graph is considered cyclical if there is a path that travels from a vertex and back to itself:

Alt Text

Figure 17-5. Graph with a cycle on B

In contrast, Figure 17-6 (below) is not cyclical:
Alt Text

Figure 17-6. Graph without a cycle
  • Weights: Weights are values on the edges. Weights can signify various things. For example, weights can represent the distance required to get from node A to B, as shown in Figure 17-7 (below):

Alt Text

Figure 17-7. Directed graph with weights

Undirected Graphs (〰️ 📈)

Alt text

Undirected graphs are graphs that do not have a direction between vertex. A real-life example of an undirected graph relationship is friendship. That is, values of the edges within a friendship graph may indicate how close the friendship is. Figure 17-8 (below) is a simple undirected graph with five vertices and six non-directional edges with weights:


Alt Text

Figure 17-8. Undirected graph with weights

There are various ways to represent undirected graphs as a data structure. Two of the most common ways to do this are by using an: adjacency matrix or adjacency list. The adjacency list uses a vertex as the key with its neighbors stored into a list, whereas an adjacency matrix is a V by V matrix. Figure 17-9 (below) illustrates the difference between an adjacency list and an adjacency matrix:


Alt Text

Figure 17-9. Graph (left), adjacency list (middle), and adjacency matrix (right)

Up Next (🔜):So far, the concepts of graphs have been discussed. Now, let’s start implementing these ideas into code and learn how to add and remove edges and vertices. (😉)

Adding Edges and Vertices (➕📈)

First, we’ll create a new class for an undirected graph:

// Undirected Graph Class
function UndirectedGraph () {
    this.edges = {};
}

Note (📝): The undirected graph should have an object to store the edges. This is implemented as shown in the following code block above.

To add edges, vertices must be added first. This implementation will take the adjacency list approach by having vertices as objects (or keys) in which edge values are stored:

// Add Vertex
UndirectedGraph.prototype.addVertex = function (vertex) {
    this.edges[vertex] = {};
}

To add weighted edges into the undirected graph, both vertices in the this.edges objects are used to set the weight:

// Add Edge
UndirectedGraph.prototype.addEdge = function (vertex1, vertex2, weight) {
    if (weight == undefined) {
        weight = 0;
    }
    this.edges[vertex1][vertex2] = weight;
    this.edges[vertex2][vertex1] = weight;
}

With this, let’s add some vertices and edges with the following code:

// Instance of the Graph Class
var graph = new UndirectedGraph();

// 1st: Add Vertex
graph.addVertex(1);
graph.addVertex(2);
graph.addVertex(3);
graph.addVertex(4);
graph.addVertex(5);

// 2nd: Add Edges
graph.addEdge(1, 2, 1);
graph.addEdge(2, 3, 8);
graph.addEdge(3, 4, 10);
graph.addEdge(4, 5, 100);
graph.addEdge(1, 5, 88);

Execution:

// Undirected Graph Class function UndirectedGraph () { this.edges = {}; } // Add Vertex UndirectedGraph.prototype.addVertex = function (vertex) { this.edges[vertex] = {}; } // Add Edge UndirectedGraph.prototype.addEdge = function (vertex1, vertex2, weight) { if (weight == undefined) { weight = 0; } this.edges[vertex1][vertex2] = weight; this.edges[vertex2][vertex1] = weight; } // Instance of the Graph Class var graph = new UndirectedGraph(); // 1st: Add Vertex graph.addVertex(1); graph.addVertex(2); graph.addVertex(3); graph.addVertex(4); graph.addVertex(5); // 2nd: Add Edges graph.addEdge(1, 2, 1); graph.addEdge(2, 3, 8); graph.addEdge(3, 4, 10); graph.addEdge(4, 5, 100); graph.addEdge(1, 5, 88); // Result graph.edges; // Prints (Adjacency List): // { // '1': { '2': 1, '5': 88 }, // '2': { '1': 1, '3': 8 }, // '3': { '2': 8, '4': 10 }, // '4': { '3': 10, '5': 100 }, // '5': { '1': 88, '4': 100 } // }

Figure 17-10 (below) shows the graphical output from this code:


Alt Text

Figure 17-10. The first undirected graph

Removing Edges and Vertices (❌📈)

Continuing with the same example, let’s implement the functions for removing edges and vertices. To remove an edge from a vertex, look for vertex in this. edges and delete it using JavaScript’s delete operator:

// Remove Edge
UndirectedGraph.prototype.removeEdge = function (vertex1, vertex2) {
    if (this.edges[vertex1] && this.edges[vertex1][vertex1] !== undefined) {
        delete this.edges[vertex1][vertex2];
    }
    if (this.edges[vertex2] && this.edges[vertex2][vertex1] !== undefined) {
        delete this.edges[vertex2][vertex1];
    }
}

Next, let’s delete an entire vertex. One important point to remember is that any time a vertex is removed, all edges connected to it also must be removed. This can be accomplished using a loop, as shown in the following implementation:

// Remove Vertex
UndirectedGraph.prototype.removeVertex = function (vertex) {
    for (var adjacentVertex in this.edges[vertex]) {
        this.removeEdge(adjacentVertex, vertex);
    }
    delete this.edges[vertex];
}

With this, let’s add some vertices and edges, and remove the edges and vertices at the same time with the following code:

// 1st: Add Vertex
graph.addVertex(1);
graph.addVertex(2);
graph.addVertex(3);
graph.addVertex(4);
graph.addVertex(5);

// 2nd: Add Edges
graph.addEdge(1, 2, 1);
graph.addEdge(2, 3, 8);
graph.addEdge(3, 4, 10);
graph.addEdge(4, 5, 100);
graph.addEdge(1, 5, 88);

// 3rd: Remove Vertex
graph.removeVertex(5);
graph.removeVertex(1);

// 4th: Remove Edge
graph.removeEdge(2, 3);

Execution:

// Undirected Graph Class function UndirectedGraph() { this.edges = {}; } // Add Vertex UndirectedGraph.prototype.addVertex = function (vertex) { this.edges[vertex] = {}; } // Add Edge UndirectedGraph.prototype.addEdge = function (vertex1, vertex2, weight) { if (weight == undefined) { weight = 0; } this.edges[vertex1][vertex2] = weight; this.edges[vertex2][vertex1] = weight; } // Remove Edge UndirectedGraph.prototype.removeEdge = function (vertex1, vertex2) { if (this.edges[vertex1] && this.edges[vertex1][vertex1] !== undefined) { delete this.edges[vertex1][vertex2]; } if (this.edges[vertex2] && this.edges[vertex2][vertex1] !== undefined) { delete this.edges[vertex2][vertex1]; } } // Remove Vertex UndirectedGraph.prototype.removeVertex = function (vertex) { for (var adjacentVertex in this.edges[vertex]) { this.removeEdge(adjacentVertex, vertex); } delete this.edges[vertex]; } // Instance of the Graph Class var graph = new UndirectedGraph(); // 1st: Add Vertex graph.addVertex(1); graph.addVertex(2); graph.addVertex(3); graph.addVertex(4); graph.addVertex(5); // 2nd: Add Edges graph.addEdge(1, 2, 1); graph.addEdge(2, 3, 8); graph.addEdge(3, 4, 10); graph.addEdge(4, 5, 100); graph.addEdge(1, 5, 88); // Before console.log(graph.edges); // 3rd: Remove Vertex graph.removeVertex(5); graph.removeVertex(1); // 4th: Remove Edge graph.removeEdge(2, 3); // After graph.edges; // Before: // { // '1': { '2': 1, '5': 88 }, // '2': { '1': 1, '3': 8 }, // '3': { '2': 8, '4': 10 }, // '4': { '3': 10, '5': 100 }, // '5': { '1': 88, '4': 100 } // } // After: // { // '2': { '1': 1, '3': 8 }, // '3': { '4': 10 }, // '4': { '3': 10, '5': 100 } // }

Let's explain what the code did to the graph:

1️⃣: Vertex 5 is removed first, and the result is shown in Figure 17-11:


Alt Text

Figure 17-11. Vertex 5 removed

2️⃣: Vertex 1 is also removed, as shown in Figure 17-12:


Alt Text

Figure 17-12. Vertex 1 removed

3️⃣: Finally, Figure 17-13 shows the result when the edge between 2 and 3 is removed.


Alt Text

Figure 17-13. Edge between 2 and 3 removed

Directed Graphs (➡️ 📈)

Alt text

Directed graphs are graphs that do have a direction between vertices, as shown in Figure 17-14 (below):


Alt Text

Figure 17-14. Directed graph

Note (📝): In this example, the E node can travel to the D node, and the D node can travel to the C node.

Now let’s implement a directed graph class. The similar adjacency list approach used in the undirected graph implementation will be used. First, the Directed Graph class is defined with the edges property as shown, and the method of adding the vertex is the same as the implementation from the undirected graph class:

// Directed Graph Class
function DirectedGraph () {
    this.edges = {};
}

// Add Vertex
DirectedGraph.prototype.addVertex = function (vertex) {
    this.edges[vertex] = {};
}

Given an edge that starts at the origin vertex and ends at the destination vertex, the weight should be set on the origin vertex, as shown here:

// Add Edge
DirectedGraph.prototype.addEdge = function (origVertex, destVertex, weight) {
    if (weight === undefined) {
        weight = 0;
    }
    this.edges[origVertex][destVertex] = weight;
}

With the functions for adding vertices and edges, let’s add some
sample vertices and edges:

// Instance for Directed Graph Class
var graph = new DirectedGraph();

// Add Vertex
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");

// Add Edge
graph.addEdge("A", "B", 1);
graph.addEdge("B", "C", 2);
graph.addEdge("C", "A", 3);

Execution:

// Directed Graph Class function DirectedGraph () { this.edges = {}; } // Add Vertex DirectedGraph.prototype.addVertex = function (vertex) { this.edges[vertex] = {}; } // Add Edge DirectedGraph.prototype.addEdge = function (origVertex, destVertex, weight) { if (weight === undefined) { weight = 0; } this.edges[origVertex][destVertex] = weight; } // Instance for Directed Graph Class var graph = new DirectedGraph(); // Add Vertex graph.addVertex("A"); graph.addVertex("B"); graph.addVertex("C"); // Add Edge graph.addEdge("A", "B", 1); graph.addEdge("B", "C", 2); graph.addEdge("C", "A", 3); graph.edges; // Prints "{ A: { B: 1 }, B: { C: 2 }, C: { A: 3 } }"

Let's explain what the code did to the graph:

Alt Text

Figure 17-15. Adding A to B

Alt Text

Figure 17-16. Adding B to C

Alt Text

Figure 17-17. Adding C to A

The implementation for removing a vertex and removing an edge for a directed graph is the same as the implementation seen in the undirected graph except that only the origin vertex have to be deleted, as shown here:

// Remove Edge
DirectedGraph.prototype.removeEdge = function (origVertex, destVertex) {
    if(this.edges[origVertex] && this.edges[origVertex][destVertex] != undefined) {
        delete this.edges[origVertex][destVertex];
    }
}

// Remove Vertex
DirectedGraph.prototype.removeVertex = function (vertex) {
    for (var adjacentVertex in this.edges[vertex]) {
        this.removeEdge(adjacentVertex, vertex);
    }
    delete this.edges[vertex];
}

Execution:

// Directed Graph Class function DirectedGraph () { this.edges = {}; } // Add Vertex DirectedGraph.prototype.addVertex = function (vertex) { this.edges[vertex] = {}; } // Add Edge DirectedGraph.prototype.addEdge = function (origVertex, destVertex, weight) { if (weight === undefined) { weight = 0; } this.edges[origVertex][destVertex] = weight; } // Remove Edge DirectedGraph.prototype.removeEdge = function (origVertex, destVertex) { if(this.edges[origVertex] && this.edges[origVertex][destVertex] != undefined) { delete this.edges[origVertex][destVertex]; } } // Remove Vertex DirectedGraph.prototype.removeVertex = function (vertex) { for (var adjacentVertex in this.edges[vertex]) { this.removeEdge(adjacentVertex, vertex); } delete this.edges[vertex]; } // Instance for Directed Graph Class var graph = new DirectedGraph(); // 1st: Add Vertex graph.addVertex("A"); graph.addVertex("B"); graph.addVertex("C"); // 2nd: Add Edge graph.addEdge("A", "B", 1); graph.addEdge("B", "C", 2); graph.addEdge("C", "A", 3); // Result: 2nd console.log(graph.edges); // Prints "{ A: { B: 1 }, B: { C: 2 }, C: { A: 3 } }" // 3rd: Remove Edge Between "A" and "B" graph.removeEdge("A", "B"); // Result: 3rd console.log(graph.edges); // Prints "{ A: {}, B: { C: 2 }, C: { A: 3 } }" // 4th: Remove Edge Between "C" and "A" graph.removeEdge("C", "A"); // Result: 4th console.log(graph.edges); // Prints "{ A: {}, B: { C: 2 }, C: {} }" // 5th: Remove Vertex "A" graph.removeVertex("A"); // Result: 5th console.log(graph.edges); // Prints "{ B: { C: 2 }, C: {} }" // 6th: Remove Vertex "C" graph.removeVertex("C"); // Result: 6th graph.edges; // Prints "{ B: { C: 2 } }" // And so on...

Graph Traversal (🔀 📈)

Alt text

A graph can be traversed in multiple ways. The two most common approaches are: breadth-first search and depth-first search. Similarly to how different tree traversal techniques were explored, this section will focus on these two traversal techniques and when to use each of them.

Breadth-First Search (➡️📊🔍)

Breadth-first search (BFS) refers to a search algorithm in a graph that focuses on connected nodes in order. This idea has been explored in Part 15 (Learn More) with level-order traversal. Figure 17-18 (below) shows level-order traversal for a binary search tree:


Alt Text

Figure 17-18. Level-order traversal for binary search tree

Notice the similarity of a level-order traversal for a binary search tree with the Breadth-first search graph in Figure 17-19 (below):
Alt Text

Figure 17-19. Breadth-first search graph

Similar to the level-order traversal, a queue is needed for a BFS.
For each node, add each of connected vertices into a queue and then visit each item in the queue. Let’s write a BFS algorithm for the graph class:

// Traverse BFS
DirectedGraph.prototype.traverseBFS = function (vertex, fn) {
    var queue = [],
        visited = {};
    queue.push(vertex);
    while (queue.length) {
        vertex = queue.shift();
        if (!visited[vertex]) {
            visited[vertex] = true;
            fn(vertex);
            for (var adjacentVertex in this.edges[vertex]) {
                queue.push(adjacentVertex);
            }
        }
    }
}

Execution:

// Directed Graph Class function DirectedGraph() { this.edges = {}; } // Add Vertex DirectedGraph.prototype.addVertex = function (vertex) { this.edges[vertex] = {}; } // Add Edge DirectedGraph.prototype.addEdge = function (origVertex, destVertex, weight) { if (weight === undefined) { weight = 0; } this.edges[origVertex][destVertex] = weight; } // Traverse BFS DirectedGraph.prototype.traverseBFS = function (vertex, fn) { var queue = [], visited = {}; queue.push(vertex); while (queue.length) { vertex = queue.shift(); if (!visited[vertex]) { visited[vertex] = true; fn(vertex); for (var adjacentVertex in this.edges[vertex]) { queue.push(adjacentVertex); } } } } // Instance for Directed Graph Class var graph = new DirectedGraph(); // Add Vertex graph.addVertex("A"); graph.addVertex("B"); graph.addVertex("C"); // Add Edge graph.addEdge("A", "B", 1); graph.addEdge("B", "C", 2); graph.addEdge("C", "A", 3); // Traverse BFS: "A" graph.traverseBFS("A", (vertex)=>{console.log(vertex)}); // A B C // Traverse BFS: "B" graph.traverseBFS("B", (vertex)=>{console.log(vertex)}); // B C A // Traverse BFS: "C" graph.traverseBFS("C", (vertex)=>{vertex}); // C A B // Or // ABC BCA CAB

Time Complexity: O(V+E)O \lparen V + E \rparen

Note (📝): The time complexity is O(V+E)O \lparen V + E \rparen , where VV is the number of vertices and EE is the number of edges. This is because the algorithm has to go through every edge and node to traverse the whole graph.

Recall the graph structure in Figure 17-20 from Undirected Graphs used earlier:
Alt Text

Figure 17-20. The earlier undirected graph example

Applying the BFS to the graph, the following is printed: 1, 2, 5, 3, 41,\space 2,\space 5,\space 3,\space 4 . In Figures 17-21 and 17-22, the green node represents the node being currently visited, while the red node represents that the node has already been visited:


Alt Text

Figure 17-21. Breadth-first search, part 1

In Figure 17-21, the breadth-first search starts at the node ( 11 ). Because it has two neighbors, 22 and 55 , those are added to the queue. Then, 22 is visited, and its neighbor 33 is added to the queue. 55 is then dequeued, and its neighbor 44 is added to the queue. Finally, 33 and 44 are visited, and the search ends, as shown in Figure 17-22:


Alt Text

Figure 17-22. Breadth-first search, part 2

Depth-First Search (1️⃣➡️2️⃣)

Depth-first search (DFS) refers to a search algorithm in a graph that focuses on traversing deep into one connection before visiting the other connections. This idea has been explored in Part 15 (Learn More) with in-order, post-order, and pre-order traversals.

Alt Text

Figure 17-23. Post-order traversal

Something similar is shown in Figure 17-24 for a graph:
Alt Text

Figure 17-24. Depth-first search graph

Notice how E is visited last. This is because the search visits all the nodes connected to C before visiting E. Similar to traversal for the tree data structure, recursion is used to go deep into a node. Let’s write a DFS algorithm for the graph class:

// Traverse DFS
DirectedGraph.prototype.traverseDFS = function (vertex, fn) {
    var visited = {};
    this._traverseDFS(vertex, visited, fn);
}

DirectedGraph.prototype._traverseDFS = function (vertex, visited, fn) {
    visited[vertex] = true;
    fn(vertex);
    for (var adjacentVertex in this.edges[vertex]) {
        if (!visited[adjacentVertex]) {
            // Recursion
            this._traverseDFS(adjacentVertex, visited, fn);
        }
    }
}

Execution:

// Directed Graph Class function DirectedGraph() { this.edges = {}; } // Add Vertex DirectedGraph.prototype.addVertex = function (vertex) { this.edges[vertex] = {}; } // Add Edge DirectedGraph.prototype.addEdge = function (origVertex, destVertex, weight) { if (weight === undefined) { weight = 0; } this.edges[origVertex][destVertex] = weight; } // Traverse DFS DirectedGraph.prototype.traverseDFS = function (vertex, fn) { var visited = {}; this._traverseDFS(vertex, visited, fn); } DirectedGraph.prototype._traverseDFS = function (vertex, visited, fn) { visited[vertex] = true; fn(vertex); for (var adjacentVertex in this.edges[vertex]) { if (!visited[adjacentVertex]) { // Recursion this._traverseDFS(adjacentVertex, visited, fn); } } } // Instance for Directed Graph Class var graph = new DirectedGraph(); // Add Vertex graph.addVertex("A"); graph.addVertex("B"); graph.addVertex("C"); // Add Edge graph.addEdge("A", "B", 1); graph.addEdge("B", "C", 2); graph.addEdge("C", "A", 3); // Traverse DFS: "A" graph.traverseDFS("A", (vertex)=>{console.log(vertex)}); // A B C // Traverse DFS: "B" graph.traverseDFS("B", (vertex)=>{console.log(vertex)}); // B C A // Traverse DFS: "C" graph.traverseDFS("C", (vertex)=>{vertex}); // C A B // Or // ABC BCA CAB

Time Complexity: O(V+E)O \lparen V + E \rparen

The time complexity is O(V+E)O \lparen V + E \rparen where VV is the number of vertices and EE is the number of edges. This is because the algorithm has to go through every edge and node to traverse the whole graph. This is the same time complexity as the BFS algorithm. Again, let’s use the graph structure from earlier:

Alt Text

Figure 17-25. The earlier graph example from Figure 17-20

Applying the DFS to the graph, the following is printed: 1, 2, 3, 4, 51,\space 2,\space 3,\space 4,\space 5 . In Figures 17-26 and 17-27, the green node represents the node being currently visited, while the red node represents that the node has already been visited:


Alt Text

Figure 17-26. Depth-first search, part 1

In Figure 17-26, the depth-first search starts at the node ( 11 ). Its first neighbor, 22 , is visited. Then, 22 ’s first neighbor, 33 , is visited. After 33 is visited, 44 will be visited next. Finally, 44 is visited followed by 55 , as shown in Figure 17-27. Depth-first search always visits the first neighbor:


Alt Text

Figure 17-27. Depth-first search, part 2

Weighted Graphs and Shortest Path (1️⃣▶️)

Alt text

Reminder (💡): Now that we have covered the basics of graphs and how to traverse them, we can discuss weighted edges and Dijkstra’s algorithm.

Graphs with Weighted Edges (➖1️⃣▶️)

Recall that edges (➡️) in a graph represent a connection between the vertices. If edges establish a connection, weight can be assigned to that connection. For example, for a graph that represents a map (🌍), the weights on the edges are distances.

It is important to note that the length of an edge means nothing with regard to the weight. In Figure 17-28 (below), the weights tell us the distances between the cities. For example, graphically, the distance from City 1 and City 2 is shorter than the distance from City 2 and City 3. However, the edges indicate that the distance from City 1 to City 2 is 50km50 km , and the distance from City 2 to City 3 is 10km10 km , which is five times larger:


Alt Text

Figure 17-28. Graph representation of five cities

Note (📝): The most important question for weighted edge graphs is, what is the shortest path from one node to another? There are shortest path algorithms for graphs. The one we discuss is Dijkstra’s algorithm

Dijkstra’s Algorithm: Shortest Path (➖1️⃣⏩)

Dijkstra’s algorithm works by taking the shortest path to get to a destination. At first, the distance is marked as infinity first because some nodes may not be reachable.Then at each traversal iteration, the shortest distance is chosen (see the example below first to get an idea):

Alt Text

Figure 17-29. Dijkstra stage 1: everything marked as infinity

Alt Text

Figure 17-30. Dijkstra stage 2: B and C processed

Alt Text

Figure 17-31. Dijkstra stage 3: all nodes now processed

extractMin is implemented to compute the neighboring node with the smallest distance for a given vertex. Using the breadth-first search to enqueue the neighboring nodes for each vertex as the graph is traversed from the origin to the destination, the distances are updated and computed:

// Directed Graph Class
function DirectedGraph() {
    this.edges = {};
}

// Helper Function: Empty Check
function _isEmpty (obj) {
    return Object.keys(obj).length === 0;
}

// Helper Function: Extract Smallest Distance
function _extractMin (Q, dist) {
    var minimumDistance = Infinity,
        nodeWithMinimumDistance = null;
    for (var node in Q) {
        if (dist[node] <= minimumDistance) {
            minimumDistance = dist[node];
            nodeWithMinimumDistance = node;
        }
    }
    return nodeWithMinimumDistance;
}

// Dijkstra Algorithm: Taking The Shortest Path
DirectedGraph.prototype.Dijkstra = function (source) {
    // Create Vertex Set Q
    var Q = {}, dist = {};
    for (var vertex in this.edges) {
        // Unknown Distances Set To Infinity
        dist[vertex] = Infinity;
        // Add v to Q
        Q[vertex] = this.edges[vertex];
    }
    // Distance From Source To Source init To 0
    dist[source] = 0;
    while (!_isEmpty(Q)) {
        // Get The Minimum Distance
        var u = _extractMin (Q, dist);
        // Remove u from Q
        delete Q[u];
        // For Each Neighbor, v, of u
        // Where V is still in Q
        for (var neighbor in this.edges[u]) {
            // Current Distance
            var alt = dist[u] + this.edges[u][neighbor];
            // A Shorter Path Has Been Found
            if (alt < dist[neighbor]) {
                dist[neighbor] = alt;
            }
        }
    }
    return dist;
}

// Add Vertex
DirectedGraph.prototype.addVertex = function (vertex) {
    this.edges[vertex] = {};
}

// Add Edge
DirectedGraph.prototype.addEdge = function (origVertex, destVertex, weight) {
    if (weight === undefined) {
        weight = 0;
    }
    this.edges[origVertex][destVertex] = weight;
}

// 

// Instance for Directed Graph Class
var graph = new DirectedGraph();

// Add Vertex
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");

// Add Edge
graph.addEdge("A", "B", 1);
graph.addEdge("B", "C", 1);
graph.addEdge("C", "A", 1);
graph.addEdge("A", "D", 1);

// The Graph:
console.log(graph);
// Prints:
// DirectedGraph {
//   edges: { A: { B: 1, D: 1 }, B: { C: 1 }, C: { A: 1 }, D: {} }
// }

// Take The Shortest Path:
graph.Dijkstra("A"); // Prints "{ A: 0, B: 1, C: 2, D: 1 }"

Execution:

// Directed Graph Class function DirectedGraph() { this.edges = {}; } // Helper Function: Empty Check function _isEmpty (obj) { return Object.keys(obj).length === 0; } // Helper Function: Extract Smallest Distance function _extractMin (Q, dist) { var minimumDistance = Infinity, nodeWithMinimumDistance = null; for (var node in Q) { if (dist[node] <= minimumDistance) { minimumDistance = dist[node]; nodeWithMinimumDistance = node; } } return nodeWithMinimumDistance; } // Dijkstra Algorithm: Taking The Shortest Path DirectedGraph.prototype.Dijkstra = function (source) { // Create Vertex Set Q var Q = {}, dist = {}; for (var vertex in this.edges) { // Unknown Distances Set To Infinity dist[vertex] = Infinity; // Add v to Q Q[vertex] = this.edges[vertex]; } // Distance From Source To Source init To 0 dist[source] = 0; while (!_isEmpty(Q)) { // Get The Minimum Distance var u = _extractMin (Q, dist); // Remove u from Q delete Q[u]; // For Each Neighbor, v, of u // Where V is still in Q for (var neighbor in this.edges[u]) { // Current Distance var alt = dist[u] + this.edges[u][neighbor]; // A Shorter Path Has Been Found if (alt < dist[neighbor]) { dist[neighbor] = alt; } } } return dist; } // Add Vertex DirectedGraph.prototype.addVertex = function (vertex) { this.edges[vertex] = {}; } // Add Edge DirectedGraph.prototype.addEdge = function (origVertex, destVertex, weight) { if (weight === undefined) { weight = 0; } this.edges[origVertex][destVertex] = weight; } // // Instance for Directed Graph Class var graph = new DirectedGraph(); // Add Vertex graph.addVertex("A"); graph.addVertex("B"); graph.addVertex("C"); graph.addVertex("D"); // Add Edge graph.addEdge("A", "B", 1); graph.addEdge("B", "C", 1); graph.addEdge("C", "A", 1); graph.addEdge("A", "D", 1); // The Graph: console.log(graph); // Prints: // DirectedGraph { // edges: { A: { B: 1, D: 1 }, B: { C: 1 }, C: { A: 1 }, D: {} } // } // Take The Shortest Path: graph.Dijkstra("A"); // Prints "{ A: 0, B: 1, C: 2, D: 1 }"

Time Complexity: O(V2+E)O \lparen V^{2} + E \rparen

The algorithm here is similar to the BFS algorithm but requires the extractMin method, which is O(n)O \lparen n \rparen in time complexity. Because of this, the time complexity is O(V2+E)O \lparen V^{2} + E \rparen because all neighbor vertices of the node currently being traversed have to be checked during the extractMin method. This algorithm can be improved using a priority queue for the extract min, which would yield O(log2(V))O \lparen log_{2}\lparen V\rparen \rparen extractMin and hence yield an overall time complexity of O(E+V) ×O(log2(V)) = O(Elog2(V))O\lparen E + V \rparen \space \times O\lparen log_{2}\lparen V \rparen \rparen \space = \space O\lparen Elog_{2}\lparen V \rparen \rparen . This can be even more optimized by using a Fibonacci heap, which has constant time to compute extractMin. However, for simplicity, neither a Fibonacci heap nor a priority queue was used for this demonstration.

Topological Sort (❄️↔️)

Alt text

For a directed graph, it can be important to know which node should be processed first (☝️). An example of this is a task scheduler where one task depends on a previous task being done. The topological sorting algorithm implements this. It is a modified DFS. Put simply, it works by performing DFS from a node until its connected nodes are exhausted (or finished) and by adding it to the stack:

Alt Text

Figure 17-32. Topological sort

Topological sorting has a visited set to ensure that the recursive call does not result in an infinite loop. For a given node, that node is added to the visited set, and its neighbors that have not been visited are visited in the next recursive call. At the end of the recursive call, push and reverse is used to add the current node’s value to the stack. This ensures that the order is chronological:

// Helper Function: Topological Sort Utility
DirectedGraph.prototype.topologicalSortUtil = function (v, visited, stack) {
    visited.add(v);
    for (var item in this.edges[v]) {
        if (visited.has(item) == false) {
            this.topologicalSortUtil(item, visited, stack)
        }
    }
    stack.push(v); // Push
}

// Topological Sort
DirectedGraph.prototype.topologicalSort = function () {
    var visited = new Set(),
        stack = [];
    for (var item in this.edges) {
        if (visited.has(item) == false) {
            this.topologicalSortUtil(item, visited, stack);
        }
    }
    stack.reverse(); // Reverse
    return stack;
}

Execution:

// Directed Graph Class function DirectedGraph() { this.edges = {}; } // Helper Function: Topological Sort Utility DirectedGraph.prototype.topologicalSortUtil = function (v, visited, stack) { visited.add(v); for (var item in this.edges[v]) { if (visited.has(item) == false) { this.topologicalSortUtil(item, visited, stack) } } stack.push(v); // Push } // Topological Sort DirectedGraph.prototype.topologicalSort = function () { var visited = new Set(), stack = []; for (var item in this.edges) { if (visited.has(item) == false) { this.topologicalSortUtil(item, visited, stack); } } stack.reverse(); // Reverse return stack; } // Add Vertex DirectedGraph.prototype.addVertex = function (vertex) { this.edges[vertex] = {}; } // Add Edge DirectedGraph.prototype.addEdge = function (origVertex, destVertex, weight) { if (weight === undefined) { weight = 0; } this.edges[origVertex][destVertex] = weight; } // // Instance for Directed Graph Class var graph = new DirectedGraph(); // Add Vertex graph.addVertex("A"); graph.addVertex("B"); graph.addVertex("C"); graph.addVertex("D"); graph.addVertex("E"); graph.addVertex("F"); // Add Edge graph.addEdge("B", "A"); graph.addEdge("D", "C"); graph.addEdge("D", "B"); graph.addEdge("B", "A"); graph.addEdge("A", "F"); graph.addEdge("E", "C"); // The Graph: console.log(graph); // Prints: // DirectedGraph { // edges: { // A: { F: 0 }, // B: { A: 0 }, // C: {}, // D: { C: 0, B: 0 }, // E: { C: 0 }, // F: {} // } // } // Topological Sort: graph.topologicalSort(); // Prints "[ 'E', 'D', 'C', 'B', 'A', 'F' ]"

Time Complexity: O(V+E)O\lparen V + E \rparen
Space Complexity: O(V)O\lparen V \rparen

The topological sort algorithm is simply DFS with an extra stack. Therefore, the time complexity is the same as DFS. Topological sorting requires O(V)O\lparen V \rparen in space because it needs to store all the vertices in the stack. This algorithm is powerful for scheduling jobs from given dependencies.

Summary (📚📚)

Alt text

This Part 17 discussed different types of graphs, their properties, and how to search and sort them. A graph, composed of vertices and connected via edges, can be represented as a data structure in many different ways. In this Part 17, an adjacency list was used to represent the graph. If the graph is dense, it is better to use a matrix-based representation of a graph instead. In a graph’s edges, weights signify the importance of the connected vertices.

Moreover, by assigning weights to edges, Dijkstra’s shortest path algorithm was implemented. Finally, graphs are versatile data structures with various use cases and interesting algorithms. Table 17-2 and Table 17-3 (below) shows some key properties of the graphs and summarizes the graph algorithms:

Property Description
Dense There are a lot of connections between different vertices.
Sparse Only a small fraction of possible connections exist between vertices
Cyclical There is a path that takes vertices back to themselves
Uncyclical There is a no path such that vertices can be taken back to themselves
Directed Graphs have a direction between edges
Undirected Graphs do not have a direction between edges
Table 17-2. Graph Properties Summary

Algorithm Description/Use Case Time Complexity
BFS Traverses the graph by visiting neighbor nodes one level at a time O(V + E)O \lparen V \space + \space E \rparen
DFS Traverses the graph by going deep into each neighbor node one at a time O(V + E)O \lparen V \space + \space E \rparen
Dijkstra Finds the shortest path from one vertex to the rest of the other vertices O(V2 + E)O \lparen V^{2} \space + \space E \rparen
Topological Sort Sorts the directed graph; for job scheduling algorithms O(V + E)O \lparen V \space + \space E \rparen
Table 17-3. Graph Algorithm Summary

Up Next👉 Part 18: Advanced Strings (🔥🔥) (September 19-20, 2020)


Alt Text

Discussion

markdown guide