© Sammie Bae 2019

Sammie BaeJavaScript Data Structures and Algorithmshttps://doi.org/10.1007/978-1-4842-3988-9_17

17. Graphs

Sammie Bae¹ 

(1)

Hamilton, ON, Canada

 

This chapter covers graphs. Graphs are a versatile way of representing connections between objects. In this chapter, you will learn graph basics, including fundamental terminology and graph types. The chapter will also cover working with these different graph types and methods of representing graphs in data structures that have already been explored. Finally, algorithms for traversing, searching, and sorting graphs are explored to solve problems such as finding the shortest path between two graph nodes.

Graph Basics

As mentioned in the introduction, graphs are visual representations of the connections between objects. Such representations can be of many things and have different applications; Table 17-1 shows some examples.

Table 17-1

Examples of Graph Applications

Application	Item	Connection
Web site	Web page	Links
Map	Intersection	Road
Circuit	Component	Wiring
Social media	Person	“Friendship”/connection
Telephone	Phone number	Landline

Figure 17-1 shows two examples of simple graphs.

Figure 17-1

Two examples of graphs

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

• Vertex: A vertex is the node from which graphs are formed. 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.

• Edge: An edge is the connection between nodes in a graph. 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.

Figure 17-2

Vertices and edges

• Degree of vertex: The degree of a vertex refers to the number of edges on that vertex (node).

• Sparse graph: A graph is considered sparse when only a small fraction of possible connections exist between vertices (see Figure 17-3).

Figure 17-3

Sparse graph

• Dense graph: A graph is considered dense when there are a lot of connections between different vertices (see Figure 17-4).

Figure 17-4

Dense graph

• Cyclical graph: A directed graph is considered cyclical if there is a path that travels from a vertex and back to itself. For example, in Figure 17-5, B can follow the edge to C and then D and then E and then to B again.

Figure 17-5

Graph with a cycle on B

In contrast, Figure 17-6 is an example of a graph that is not cyclical.

Figure 17-6

Graph without a cycle

• Weights: Weights are values on the edges. Weights can signify various things depending on the context. For example, weights on a directed graph can represent the distance required to get from node A to B, as shown in Figure 17-7.

Figure 17-7

Directed graph with weights

Undirected Graphs

Undirected graphs are graphs that do not have a direction between edges. The edge implies a mutual connection between the two nodes without a direction. A real-life example of an undirected graph relationship is friendship. Friendship occurs only if both parties mutually acknowledge the relationship. Values of the edges within a friendship graph may indicate how close the friendship is. Figure 17-8 is a simple undirected graph with five vertices and six nondirectional edges with weights.

Figure 17-8

Undirected graph with weights

There are various ways to represent undirected graphs as a data structure class. Two of the most common ways to do this are by using an adjacency matrix or an adjacency list. The adjacency list uses a vertex as the key for nodes with its neighbors stored into a list, whereas an adjacency matrix is a V by V matrix with each element of the matrix indicating a connection between two vertices. Figure 17-9 illustrates the difference between an adjacency list and an adjacency matrix (This book covers only adjacency lists).

Figure 17-9

Graph (left), adjacency list (middle), and adjacency matrix (right)

So far, the concepts and definitions of graphs have been discussed. Now, let’s actually start implementing these ideas into code and learn how to add and remove edges and vertices.

Adding Edges and Vertices

In this example, we create a weighted undirected graph and add vertices and edges. First, we’ll create a new class for an undirected graph. The undirected graph should have an object to store the edges. This is implemented as shown in the following code block:

 1   function UndirectedGraph() {

 2       this.edges = {};

 3   }

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

 1   UndirectedGraph.prototype.addVertex = function(vertex) {

 2       this.edges[vertex] = {};

 3   }

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

 1   UndirectedGraph.prototype.addEdge = function(vertex1,vertex2, weight) {

 2       if (weight == undefined) {

 3           weight = 0;

 4       }

 5       this.edges[vertex1][vertex2] = weight;

 6       this.edges[vertex2][vertex1] = weight;

 7  }

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

 1   var graph1 = new UndirectedGraph();

 2   graph1.addVertex(1);

 3   graph1.addVertex(2);

 4   graph1.addEdge(1,2, 1);

 5   graph1.edges;   // 1: {2: 0},  2: {1: 0}

 6   graph1.addVertex(3);

 7   graph1.addVertex(4);

 8   graph1.addVertex(5);

 9   graph1.addEdge(2,3, 8);

10   graph1.addEdge(3,4, 10);

11   graph1.addEdge(4,5, 100);

12  graph1.addEdge(1,5, 88);

Figure 17-10 shows the graphical output from this code.

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 for the graph class.

To remove an edge from a vertex, look up the edges object for that vertex in this.edges and delete it using JavaScript’s delete operator.

 1   UndirectedGraph.prototype.removeEdge = function(vertex1, vertex2) {

 2       if (this.edges[vertex1] && this.edges[vertex1][vertex2] != undefined) {

 3           delete this.edges[vertex1][vertex2];

 4       }

 5       if (this.edges[vertex2] && this.edges[vertex2][vertex1] != undefined) {

 6           delete this.edges[vertex2][vertex1];

 7       }

 8   }

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:

 1   UndirectedGraph.prototype.removeVertex = function(vertex) {

 2       for (var adjacentVertex in this.edges[vertex]) {

 3           this.removeEdge(adjacentVertex, vertex);

 4       }

 5       delete this.edges[vertex];

 6   }

With removal now implemented, let’s create another undirected graph object similar to the first example but delete some vertices and edges. Vertex 5 is removed first, and the result is shown in Figure 17-11. Vertex 1 is also removed, as shown in Figure 17-12. Finally, Figure 17-13 shows the result when the edge between 2 and 3 is removed.

 1   var graph2 = new UndirectedGraph();

 2   graph2.addVertex(1);

 3   graph2.addVertex(2);

 4   graph2.addEdge(1,2, 1);

 5   graph2.edges;   // 1: {2: 0},  2: {1: 0}

 6   graph2.addVertex(3);

 7   graph2.addVertex(4);

 8   graph2.addVertex(5);

 9   graph2.addEdge(2,3, 8);

10   graph2.addEdge(3,4, 10);

11   graph2.addEdge(4,5, 100);

12   graph2.addEdge(1,5, 88);

13   graph2.removeVertex(5);

14   graph2.removeVertex(1);

15   graph2.removeEdge(2,3);

Figure 17-11

Vertex 5 removed

Figure 17-12

Vertex 1 removed

Figure 17-13

Edge between 2 and 3 removed

Directed Graphs

Directed graphs are graphs that do have a direction between vertices. Each edge in a directed graph goes from one vertex to another, as shown in Figure 17-14.

Figure 17-14

Directed graph

In this example, the E node can “travel” to the D node, and the D node can travel only to the C node.

Now let’s implement a weighted directed graph class. The similar adjacency list approach used in the undirected graph implementation will be used. First, the DirectedGraph 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.

 1   function DirectedGraph() {

 2       this.edges = {};

 3   }

 4   DirectedGraph.prototype.addVertex = function (vertex) {

 5       this.edges[vertex] = {};

 6   }

Given an edge that starts at the origin vertex and ends at the destination vertex, to add edges into the directed graph, the weight should be set only on the origin vertex, as shown here:

 1   DirectedGraph.prototype.addEdge = function(origVertex, destVertex, weight) {

 2       if (weight === undefined) {

 3           weight = 0;

 4       }

 5       this.edges[origVertex][destVertex] = weight;

 6   }

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

 1   var digraph1 = new DirectedGraph();

 2   digraph1.addVertex("A");

 3   digraph1.addVertex("B");

 4   digraph1.addVertex("C");

 5   digraph1.addEdge("A", "B", 1);

 6   digraph1.addEdge("B", "C", 2);

 7   digraph1.addEdge("C", "A", 3);

Figure 17-15 shows the edge added between the A and B vertices (line 5). Figure 17-16 illustrates the connections between B and C (line 6), and Figure 17-17 shows the connection between C and A (line 7).

Figure 17-15

Adding A to B

Figure 17-16

Adding B to C

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 in the edges object have to be deleted, as shown here:

 1   DirectedGraph.prototype.removeEdge = function(origVertex, destVertex) {

 2       if (this.edges[origVertex] && this.edges[origVertex][destVertex] != undefined) {

 3           delete this.edges[origVertex][destVertex];

 4       }

 5   }

 6

 7   DirectedGraph.prototype.removeVertex = function(vertex) {

 8       for (var adjacentVertex in this.edges[vertex]) {

 9           this.removeEdge(adjacentVertex, vertex);

10       }

11       delete this.edges[vertex];

12   }

Graph Traversal

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 and their connected nodes in order. This idea has actually already been explored with trees in Chapter 15 with level-order traversal. Figure 17-18 shows level-order traversal for a binary search tree.

Figure 17-18

Level-order traversal for binary search tree

Notice how the order of traversal is by the height from the root node. Notice the similarity with the graph in Figure 17-19.

Figure 17-19

Breadth-first search graph

Similar to the level-order traversal for the tree data structure, 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 generalized BFS algorithm for the graph class.

 1   DirectedGraph.prototype.traverseBFS = function(vertex, fn) {

 2       var queue = [],

 3          visited = {};

 4

 5       queue.push(vertex);

 6

 7       while (queue.length) {

 8           vertex = queue.shift();

 9           if (!visited[vertex]) {

10               visited[vertex] = true;

11               fn(vertex);

12               for (var adjacentVertex in this.edges[vertex]) {

13                   queue.push(adjacentVertex);

14               }

15           }

16       }

17   }

18   digraph1.traverseBFS("B", (vertex)=>{console.log(vertex)});

Time Complexity: O(V + E)

The time complexity is O(V + E), where V is the number of vertices and E 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 in this chapter.

Figure 17-20

The earlier undirected graph example

Applying the BFS to the graph, the following is printed: 1, 2, 5, 3, 4.

In Figures 17-21 and 17-22, the lightly shaded node represents the node being currently visited, while the dark node represents that the node has already been visited.

Figure 17-21

Breadth-first search, part 1

In Figure 17-21, the breadth-first search starts at the 1 node. Because it has two neighbors, 2 and 5, those are added to the queue. Then, 2 is visited, and its neighbor 3 is added to the queue. 5 is then dequeued, and its neighbor 4 is added to the queue. Finally, 3 and 4 are visited, and the search ends, as shown in Figure 17-22.

Figure 17-22

Breadth-first search, part 2

Depth-First Search

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 Chapter 15 with in-order, post-order, and pre-order traversals in trees. For example, a post-order tree traversal visits the bottom children node before visiting the top root nodes (see Figure 17-23).

Figure 17-23

Post-order traversal

Something similar is shown in Figure 17-24 for a graph.

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 in depth before visiting E.

Similar to the pre-post, and in-order traversal for the tree data structure, recursion is used to go deep into a node until that path is exhausted.

Let’s write a generalized DFS algorithm for the graph class.

 1   DirectedGraph.prototype.traverseDFS = function(vertex, fn) {

 2      var visited = {};

 3      this._traverseDFS(vertex, visited, fn);

 4   }

 5

 6   DirectedGraph.prototype._traverseDFS = function(vertex, visited, fn) {

 7       visited[vertex] = true;

 8       fn(vertex);

 9       for (var adjacentVertex in this.edges[vertex]) {

10           if (!visited[adjacentVertex]) {

11               this._traverseDFS(adjacentVertex, visited, fn);

12           }

13       }

14   }

Time Complexity: O(V + E)

The time complexity is O(V + E) where V is the number of vertices and E 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 in the chapter (see Figure 17-25).

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, 5.

In Figures 17-26 and 17-27, the lightly shaded node represents the node being currently visited, while the dark node represents that the node has already been visited.

Figure 17-26

Depth-first search, part 1

In Figure 17-26, the depth-first search starts at the 1 node. Its first neighbor, 2, is visited. Then, 2’s first neighbor, 3, is visited. After 3 is visited, 4 will be visited next because it is 3’s first neighbor. Finally, 4 is visited followed by 5, as shown in Figure 17-27. Depth-first search always visits the first neighbor recursively.

Figure 17-27

Depth-first search, part 2

Weighted Graphs and Shortest Path

Now that we have covered the basics of graphs and how to traverse them, we can discuss weighted edges and Dijkstra’s algorithm, which employs shortest path searches.

Graphs with Weighted Edges

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 graphical length of an edge means nothing with regard to the edge’s weight. It is purely there for visual purposes. In the implementation and the code, the visual representation is not required. In Figure 17-28, the weights tell us the distances between the cities in a graph representation of five 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 50 km, and the distance from City 2 to City 3 is 10 km, which is five times larger.

Figure 17-28

Graph representation of five cities

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

Dijkstra’s Algorithm: Shortest Path

Dijkstra’s algorithm works by taking the shortest path at each level to get to a destination. At first, the distance is marked as infinity because some nodes may not be reachable (see Figure 17-29). Then at each traversal iteration, the shortest distance is chosen for each node (see Figures 17-30 and 17-31).

Figure 17-29

Dijkstra stage 1: everything marked as infinity

Figure 17-30

Dijkstra stage 2: B and C processed

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 outline to enqueue the neighboring nodes for each vertex as the graph is traversed from the origin to the destination node, the distances are updated and computed.

 1  function _isEmpty(obj) {

 2       return Object.keys(obj).length === 0;

 3  }

 4

 5   function _extractMin(Q, dist) {

 6       var minimumDistance = Infinity,

 7           nodeWithMinimumDistance = null;

 8       for (var node in Q) {

 9           if (dist[node] <= minimumDistance) {

10               minimumDistance = dist[node];

11               nodeWithMinimumDistance = node;

12           }

13       }

14       return nodeWithMinimumDistance;

15   }

16

17   DirectedGraph.prototype.Dijkstra = function(source) {

18       // create vertex set Q

19       var Q = {}, dist = {};

20       for (var vertex in this.edges) {

21           // unknown distances set to Infinity

22           dist[vertex] = Infinity;

23           // add v to Q

24           Q[vertex] = this.edges[vertex];

25       }

26       // Distance from source to source init to 0

27       dist[source] = 0;

28

29      while (!_isEmpty(Q)) {

30           var u = _extractMin(Q, dist); // get the min distance

31

32           // remove u from Q

33           delete Q[u];

34

35           // for each neighbor, v, of u:

36           // where v is still in Q.

37           for (var neighbor in this.edges[u]) {

38               // current distance

39               var alt = dist[u] + this.edges[u][neighbor];

40               // a shorter path has been found

41               if (alt < dist[neighbor]) {

42                   dist[neighbor] = alt;

43               }

44           }

45       }

46       return dist;

47   }

48

49   var digraph1 = new DirectedGraph();

50   digraph1.addVertex("A");

51   digraph1.addVertex("B");

52   digraph1.addVertex("C");

53   digraph1.addVertex("D");

54   digraph1.addEdge("A", "B", 1);

55   digraph1.addEdge("B", "C", 1);

56   digraph1.addEdge("C", "A", 1);

57   digraph1.addEdge("A", "D", 1);

58   console.log(digraph1);

59   // DirectedGraph {

60   // V: 4,

61   // E: 4,

62   // edges: { A: { B: 1, D: 1 }, B: { C: 1 }, C: { A: 1 }, D: {} }}

63   digraph1.Dijkstra("A"); // { A: 0, B: 1, C: 2, D: 1 }

Time Complexity: O(V² + E)

The algorithm here is similar to the BFS algorithm but requires the _extractMin method , which is O(n) in time complexity. Because of this, the time complexity is O(V² + 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(log₂(V )) _extractMin and hence yield an overall time complexity of O(E + V) * O(log2(V)) = O(E log₂(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

For a directed graph, it can be important to know which node should be processed first for various applications. An example of this is a task scheduler where one task depends on a previous task being done. Another example is a JavaScript library dependency manager where it has to figure out which libraries to import before others. The topological sorting algorithm implements this. It is a modified DFS that uses a stack to record the order.

Put simply, it works by performing DFS from a node until its connected nodes are recursively exhausted and by adding it to the stack until the connected nodes are all visited (see Figure 17-32).

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, unshift is used to add the current node’s value to the stack. This ensures that the order is chronological.

 1   DirectedGraph.prototype.topologicalSortUtil = function(v, visited, stack) {

 2      visited.add(v);

 3

 4      for (var item in this.edges[v]) {

 5           if (visited.has(item) == false) {

 6               this.topologicalSortUtil(item, visited, stack)

 7          }

 8       }

 9       stack.unshift(v);

10   };

11

12   DirectedGraph.prototype.topologicalSort = function() {

13       var visited = {},

14           stack = [];

15

16

17       for (var item in this.edges) {

18           if (visited.has(item) == false) {

19              this.topologicalSortUtil(item, visited, stack);

20           }

21       }

22       return stack;

23   };

24

25   var g = new DirectedGraph() ;

26   g.addVertex('A');

27   g.addVertex('B');

28   g.addVertex('C');

29   g.addVertex('D');

30   g.addVertex('E');

31   g.addVertex('F');

32

33   g.addEdge('B', 'A');

34   g.addEdge('D', 'C');

35   g.addEdge('D', 'B');

36   g.addEdge('B', 'A');

37   g.addEdge('A', 'F');

38   g.addEdge('E', 'C');

39   var topologicalOrder = g.topologicalSort();

40   console.log(g);

41   // DirectedGraph {

42   // V: 6,

43   // E: 6,

44   // edges:

45   //  { A: { F: 0 },

46   //    B: { A: 0 },

47   //    C: {},

48   //    D: { C: 0, B: 0 },

49   //    E: { C: 0 },

50   //    F: {} } }

51   console.log(topologicalOrder); // [ 'E', 'D', 'C', 'B', 'A', 'F' ]

Time Complexity: O(V + E)

Space Complexity: O(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) in space because it needs to store all the vertices in the stack. This algorithm is powerful for scheduling jobs from given dependencies.

Summary

This chapter 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 chapter, 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 (or the lack thereof) 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 shows some key properties of the graphs.

Table 17-2

Graph Properties Summary

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-3 summarizes the graph algorithms.

Table 17-3

Graph Algorithm Summary

Algorithm	Description/Use Case	Time Complexity
BFS	Traverses the graph by visiting neighbor nodes one level at a time	O(V + E )
DFS	Traverses the graph by going deep into each neighbor node one at a time	O(V + E )
Dijkstra	Finds the shortest path from one vertex to the rest of the other vertices	O(V2+ E )
Topological Sort	Sorts the directed graph; for job scheduling algorithms	O(V + E )