Your Web News in One Place

Help Webnuz

Referal links:

Sign up for GreenGeeks web hosting
September 13, 2020 04:22 am GMT

Learn Data Structure and Algorithm in JavaScript | Part 17



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 objects 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 (). Lets 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. ()

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, lets start implementing these ideas into code and learn how to add and remove edges and vertices. ()

Adding Edges and Vertices ()

First, well create a new class for an undirected graph:

// Undirected Graph Classfunction 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 VertexUndirectedGraph.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 EdgeUndirectedGraph.prototype.addEdge = function (vertex1, vertex2, weight) {    if (weight == undefined) {        weight = 0;    }    this.edges[vertex1][vertex2] = weight;    this.edges[vertex2][vertex1] = weight;}

With this, lets add some vertices and edges with the following code:

// Instance of the Graph Classvar graph = new UndirectedGraph();// 1st: Add Vertexgraph.addVertex(1);graph.addVertex(2);graph.addVertex(3);graph.addVertex(4);graph.addVertex(5);// 2nd: Add Edgesgraph.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 Classfunction UndirectedGraph () { this.edges = {};}// Add VertexUndirectedGraph.prototype.addVertex = function (vertex) { this.edges[vertex] = {};}// Add EdgeUndirectedGraph.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 Classvar graph = new UndirectedGraph();// 1st: Add Vertexgraph.addVertex(1);graph.addVertex(2);graph.addVertex(3);graph.addVertex(4);graph.addVertex(5);// 2nd: Add Edgesgraph.addEdge(1, 2, 1);graph.addEdge(2, 3, 8);graph.addEdge(3, 4, 10);graph.addEdge(4, 5, 100);graph.addEdge(1, 5, 88);// Resultgraph.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, lets 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 JavaScripts delete operator:

// Remove EdgeUndirectedGraph.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, lets 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 VertexUndirectedGraph.prototype.removeVertex = function (vertex) {    for (var adjacentVertex in this.edges[vertex]) {        this.removeEdge(adjacentVertex, vertex);    }    delete this.edges[vertex];}

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

// 1st: Add Vertexgraph.addVertex(1);graph.addVertex(2);graph.addVertex(3);graph.addVertex(4);graph.addVertex(5);// 2nd: Add Edgesgraph.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 Vertexgraph.removeVertex(5);graph.removeVertex(1);// 4th: Remove Edgegraph.removeEdge(2, 3);

Execution:

// Undirected Graph Classfunction UndirectedGraph() { this.edges = {};}// Add VertexUndirectedGraph.prototype.addVertex = function (vertex) { this.edges[vertex] = {};}// Add EdgeUndirectedGraph.prototype.addEdge = function (vertex1, vertex2, weight) { if (weight == undefined) { weight = 0; } this.edges[vertex1][vertex2] = weight; this.edges[vertex2][vertex1] = weight;}// Remove EdgeUndirectedGraph.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 VertexUndirectedGraph.prototype.removeVertex = function (vertex) { for (var adjacentVertex in this.edges[vertex]) { this.removeEdge(adjacentVertex, vertex); } delete this.edges[vertex];}// Instance of the Graph Classvar graph = new UndirectedGraph();// 1st: Add Vertexgraph.addVertex(1);graph.addVertex(2);graph.addVertex(3);graph.addVertex(4);graph.addVertex(5);// 2nd: Add Edgesgraph.addEdge(1, 2, 1);graph.addEdge(2, 3, 8);graph.addEdge(3, 4, 10);graph.addEdge(4, 5, 100);graph.addEdge(1, 5, 88);// Beforeconsole.log(graph.edges);// 3rd: Remove Vertexgraph.removeVertex(5);graph.removeVertex(1);// 4th: Remove Edgegraph.removeEdge(2, 3);// Aftergraph.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 lets 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 Classfunction DirectedGraph () {    this.edges = {};}// Add VertexDirectedGraph.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 EdgeDirectedGraph.prototype.addEdge = function (origVertex, destVertex, weight) {    if (weight === undefined) {        weight = 0;    }    this.edges[origVertex][destVertex] = weight;}

With the functions for adding vertices and edges, lets add some
sample vertices and edges:

// Instance for Directed Graph Classvar graph = new DirectedGraph();// Add Vertexgraph.addVertex("A");graph.addVertex("B");graph.addVertex("C");// Add Edgegraph.addEdge("A", "B", 1);graph.addEdge("B", "C", 2);graph.addEdge("C", "A", 3);

Execution:

// Directed Graph Classfunction DirectedGraph () { this.edges = {};}// Add VertexDirectedGraph.prototype.addVertex = function (vertex) { this.edges[vertex] = {};}// Add EdgeDirectedGraph.prototype.addEdge = function (origVertex, destVertex, weight) { if (weight === undefined) { weight = 0; } this.edges[origVertex][destVertex] = weight;}// Instance for Directed Graph Classvar graph = new DirectedGraph();// Add Vertexgraph.addVertex("A");graph.addVertex("B");graph.addVertex("C");// Add Edgegraph.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 EdgeDirectedGraph.prototype.removeEdge = function (origVertex, destVertex) {    if(this.edges[origVertex] && this.edges[origVertex][destVertex] != undefined) {        delete this.edges[origVertex][destVertex];    }}// Remove VertexDirectedGraph.prototype.removeVertex = function (vertex) {    for (var adjacentVertex in this.edges[vertex]) {        this.removeEdge(adjacentVertex, vertex);    }    delete this.edges[vertex];}

Execution:

// Directed Graph Classfunction DirectedGraph () { this.edges = {};}// Add VertexDirectedGraph.prototype.addVertex = function (vertex) { this.edges[vertex] = {};}// Add EdgeDirectedGraph.prototype.addEdge = function (origVertex, destVertex, weight) { if (weight === undefined) { weight = 0; } this.edges[origVertex][destVertex] = weight;}// Remove EdgeDirectedGraph.prototype.removeEdge = function (origVertex, destVertex) { if(this.edges[origVertex] && this.edges[origVertex][destVertex] != undefined) { delete this.edges[origVertex][destVertex]; }}// Remove VertexDirectedGraph.prototype.removeVertex = function (vertex) { for (var adjacentVertex in this.edges[vertex]) { this.removeEdge(adjacentVertex, vertex); } delete this.edges[vertex];}// Instance for Directed Graph Classvar graph = new DirectedGraph();// 1st: Add Vertexgraph.addVertex("A");graph.addVertex("B");graph.addVertex("C");// 2nd: Add Edgegraph.addEdge("A", "B", 1);graph.addEdge("B", "C", 2);graph.addEdge("C", "A", 3);// Result: 2ndconsole.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: 3rdconsole.log(graph.edges); // Prints "{ A: {}, B: { C: 2 }, C: { A: 3 } }"// 4th: Remove Edge Between "C" and "A"graph.removeEdge("C", "A");// Result: 4thconsole.log(graph.edges); // Prints "{ A: {}, B: { C: 2 }, C: {} }"// 5th: Remove Vertex "A"graph.removeVertex("A");// Result: 5thconsole.log(graph.edges); // Prints "{ B: { C: 2 }, C: {} }"// 6th: Remove Vertex "C"graph.removeVertex("C");// Result: 6thgraph.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. Lets write a BFS algorithm for the graph class:

// Traverse BFSDirectedGraph.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 Classfunction DirectedGraph() { this.edges = {};}// Add VertexDirectedGraph.prototype.addVertex = function (vertex) { this.edges[vertex] = {};}// Add EdgeDirectedGraph.prototype.addEdge = function (origVertex, destVertex, weight) { if (weight === undefined) { weight = 0; } this.edges[origVertex][destVertex] = weight;}// Traverse BFSDirectedGraph.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 Classvar graph = new DirectedGraph();// Add Vertexgraph.addVertex("A");graph.addVertex("B");graph.addVertex("C");// Add Edgegraph.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 O(V+E)

Note (): The time complexity is O(V+E)O \lparen V + E \rparen O(V+E), where VVV is the number of vertices and EEE 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 41,2,5,3,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 ( 111). Because it has two neighbors, 222 and 555, those are added to the queue. Then, 222 is visited, and its neighbor 333 is added to the queue. 555 is then dequeued, and its neighbor 444 is added to the queue. Finally, 333 and 444 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 (12)

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. Lets write a DFS algorithm for the graph class:

// Traverse DFSDirectedGraph.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 Classfunction DirectedGraph() { this.edges = {};}// Add VertexDirectedGraph.prototype.addVertex = function (vertex) { this.edges[vertex] = {};}// Add EdgeDirectedGraph.prototype.addEdge = function (origVertex, destVertex, weight) { if (weight === undefined) { weight = 0; } this.edges[origVertex][destVertex] = weight;}// Traverse DFSDirectedGraph.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 Classvar graph = new DirectedGraph();// Add Vertexgraph.addVertex("A");graph.addVertex("B");graph.addVertex("C");// Add Edgegraph.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 \rparenO(V+E)

The time complexity is O(V+E)O \lparen V + E \rparenO(V+E) where VVV is the number of vertices and EEE 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, lets 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 51,2,3,4,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 ( 111). Its first neighbor, 222, is visited. Then, 222s first neighbor, 333, is visited. After 333 is visited, 444 will be visited next. Finally, 444 is visited followed by 555, 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 Dijkstras 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 km50km, and the distance from City 2 to City 3 is 10km10 km10km, 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 Dijkstras algorithm

Dijkstras Algorithm: Shortest Path (1)

Dijkstras 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 Classfunction DirectedGraph() {    this.edges = {};}// Helper Function: Empty Checkfunction _isEmpty (obj) {    return Object.keys(obj).length === 0;}// Helper Function: Extract Smallest Distancefunction _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 PathDirectedGraph.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 VertexDirectedGraph.prototype.addVertex = function (vertex) {    this.edges[vertex] = {};}// Add EdgeDirectedGraph.prototype.addEdge = function (origVertex, destVertex, weight) {    if (weight === undefined) {        weight = 0;    }    this.edges[origVertex][destVertex] = weight;}// // Instance for Directed Graph Classvar graph = new DirectedGraph();// Add Vertexgraph.addVertex("A");graph.addVertex("B");graph.addVertex("C");graph.addVertex("D");// Add Edgegraph.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 Classfunction DirectedGraph() { this.edges = {};}// Helper Function: Empty Checkfunction _isEmpty (obj) { return Object.keys(obj).length === 0;}// Helper Function: Extract Smallest Distancefunction _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 PathDirectedGraph.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 VertexDirectedGraph.prototype.addVertex = function (vertex) { this.edges[vertex] = {};}// Add EdgeDirectedGraph.prototype.addEdge = function (origVertex, destVertex, weight) { if (weight === undefined) { weight = 0; } this.edges[origVertex][destVertex] = weight;}// // Instance for Directed Graph Classvar graph = new DirectedGraph();// Add Vertexgraph.addVertex("A");graph.addVertex("B");graph.addVertex("C");graph.addVertex("D");// Add Edgegraph.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 \rparenO(V2+E)

The algorithm here is similar to the BFS algorithm but requires the extractMin method, which is O(n)O \lparen n \rparenO(n) in time complexity. Because of this, the time complexity is O(V2+E)O \lparen V^{2} + E \rparenO(V2+E) 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 \rparenO(log2(V)) 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 \rparenO(E+V)O(log2(V))=O(Elog2(V)). 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 nodes value to the stack. This ensures that the order is chronological:

// Helper Function: Topological Sort UtilityDirectedGraph.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 SortDirectedGraph.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 Classfunction DirectedGraph() { this.edges = {};}// Helper Function: Topological Sort UtilityDirectedGraph.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 SortDirectedGraph.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 VertexDirectedGraph.prototype.addVertex = function (vertex) { this.edges[vertex] = {};}// Add EdgeDirectedGraph.prototype.addEdge = function (origVertex, destVertex, weight) { if (weight === undefined) { weight = 0; } this.edges[origVertex][destVertex] = weight;}// // Instance for Directed Graph Classvar graph = new DirectedGraph();// Add Vertexgraph.addVertex("A");graph.addVertex("B");graph.addVertex("C");graph.addVertex("D");graph.addVertex("E");graph.addVertex("F");// Add Edgegraph.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 \rparenO(V+E)
Space Complexity: O(V)O\lparen V \rparenO(V)

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 \rparenO(V) 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 graphs edges, weights signify the importance of the connected vertices.

Moreover, by assigning weights to edges, Dijkstras 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 levelat a time O(V+E)O \lparen V \space + \space E \rparen O(V+E)
DFS Traverses the graph by going deep into each neighbornode one at a time O(V+E)O \lparen V \space + \space E \rparen O(V+E)
Dijkstra Finds the shortest path from one vertex to the rest of theother vertices O(V2+E)O \lparen V^{2} \space + \space E \rparen O(V2+E)
Topological Sort Sorts the directed graph; for job scheduling algorithms O(V+E)O \lparen V \space + \space E \rparen O(V+E)
Table 17-3. Graph Algorithm Summary

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

Alt Text


Original Link: https://dev.to/edisonpebojots/learn-data-structure-and-algorithm-in-javascript-part-17-2ej0

Share this article:    Share on Facebook
View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To