Neal Callaghan@nealcallaghanNever ever underestimate the power of a good nights sleep when coding. Where once I was blind now I can see #React #javascript10:41 AM  12 Sep 2020
I just taught a good developer with 5 years of javascript experience that you can use `debugger;`
he is losing his shit right now. he's been debugging with console.log for his entire career.
#javascript21:07 PM  10 Sep 2020
Prerequisite (✋😐)
If you're reading this article right now, please considered to read our Part 01: BigO Notation, Part 02: JavaScript Unique Part, Part 03: JavaScript Numbers to Part 16: Heaps

Part Table of Contents Description 01 BigO 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 BigO is important for analyzing and comparing the efficiencies of algorithms. The analysis of BigO starts by looking at the code, and, applying the rules, applying the rules is because to simplify the BigO 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 builtin functions. You will learn how to access, compare, decompose, and search strings for commonly used reallife 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 builtin 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 fixedsized 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 rereading the hard drive, and a web browser caches web images to avoid redownloading. 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 selfbalancing 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 selfbalancing 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 (😱 🔥 📈)
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 (📈 📈)
Graphs are visual representations of the connections
between objects. Such representations can be of many things and have different applications; Table 171 (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 171. Examples of Graph Applications
Figure 171 (below) shows two examples of simple graphs:
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 BigO analysis. A vertex is represented using a circle, as shown in Figure 172 (below).
Edge: Graphically, it is the line between the vertices. It will be noted as E for BigO analysis. An edge is represented using a line, as shown in Figure 172 (below):

Figure 172. 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:

Figure 173. Sparse graph
 Dense graph: A graph is considered dense when there are a lot of connections between vertices:

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

Figure 175. Graph with a cycle on B
In contrast, Figure 176 (below) is not cyclical:

Figure 176. 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 177 (below):

Figure 177. Directed graph with weights
Undirected Graphs (〰️ 📈)
Undirected graphs are graphs that do not have a direction between vertex. A reallife 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 178 (below) is a simple undirected graph with five vertices and six nondirectional edges with weights:

Figure 178. 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 179 (below) illustrates the difference between an adjacency list and an adjacency matrix:

Figure 179. 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:
Figure 1710 (below) shows the graphical output from this code:

Figure 1710. 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:
Let's explain what the code did to the graph:
1️⃣: Vertex 5 is removed first, and the result is shown in Figure 1711:

Figure 1711. Vertex 5 removed
2️⃣: Vertex 1 is also removed, as shown in Figure 1712:

Figure 1712. Vertex 1 removed
3️⃣: Finally, Figure 1713 shows the result when the edge between 2 and 3 is removed.

Figure 1713. Edge between 2 and 3 removed
Directed Graphs (➡️ 📈)
Directed graphs are graphs that do have a direction between vertices, as shown in Figure 1714 (below):

Figure 1714. 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:
Let's explain what the code did to the graph:

Figure 1715. Adding A to B

Figure 1716. Adding B to C

Figure 1717. 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:
Graph Traversal (🔀 📈)
A graph can be traversed in multiple ways. The two most common approaches are: breadthfirst search and depthfirst 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.
BreadthFirst Search (➡️📊🔍)
Breadthfirst 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 levelorder traversal. Figure 1718 (below) shows levelorder traversal for a binary search tree:

Figure 1718. Levelorder traversal for binary search tree
Notice the similarity of a levelorder traversal for a binary search tree with the Breadthfirst search graph in Figure 1719 (below):

Figure 1719. Breadthfirst search graph
Similar to the levelorder 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:
Time Complexity: $O \lparen V + E \rparen$
Note (📝): The time complexity is $O \lparen V + E \rparen$ , 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 1720 from Undirected Graphs used earlier:

Figure 1720. The earlier undirected graph example
Applying the BFS to the graph, the following is printed: $1,\space 2,\space 5,\space 3,\space 4$ . In Figures 1721 and 1722, the green node represents the node being currently visited, while the red node represents that the node has already been visited:

Figure 1721. Breadthfirst search, part 1
In Figure 1721, the breadthfirst search starts at the node ( $1$ ). 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 1722:

Figure 1722. Breadthfirst search, part 2
DepthFirst Search (1️⃣➡️2️⃣)
Depthfirst 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 inorder, postorder, and preorder traversals.

Figure 1723. Postorder traversal
Something similar is shown in Figure 1724 for a graph:

Figure 1724. Depthfirst 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:
Time Complexity: $O \lparen V + E \rparen$
The time complexity is $O \lparen V + E \rparen$ 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:

Figure 1725. The earlier graph example from Figure 1720
Applying the DFS to the graph, the following is printed: $1,\space 2,\space 3,\space 4,\space 5$ . In Figures 1726 and 1727, the green node represents the node being currently visited, while the red node represents that the node has already been visited:

Figure 1726. Depthfirst search, part 1
In Figure 1726, the depthfirst search starts at the node ( $1$ ). Its first neighbor, $2$ , is visited. Then, $2$ ’s first neighbor, $3$ , is visited. After $3$ is visited, $4$ will be visited next. Finally, $4$ is visited followed by $5$ , as shown in Figure 1727. Depthfirst search always visits the first neighbor:

Figure 1727. Depthfirst search, part 2
Weighted Graphs and Shortest Path (1️⃣▶️)
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 1728 (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 $50 km$ , and the distance from City 2 to City 3 is $10 km$ , which is five times larger:

Figure 1728. 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):

Figure 1729. Dijkstra stage 1: everything marked as infinity

Figure 1730. Dijkstra stage 2: B and C processed

Figure 1731. 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 breadthfirst 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:
Time Complexity: $O \lparen V^{2} + E \rparen$
The algorithm here is similar to the BFS algorithm but requires the extractMin method, which is $O \lparen n \rparen$ in time complexity. Because of this, the time complexity is $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 \lparen log_{2}\lparen V\rparen \rparen$ extractMin and hence yield an overall time complexity of $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 (❄️↔️)
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:

Figure 1732. 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:
Time Complexity:
$O\lparen V + E \rparen$
Space Complexity:
$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\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 (📚📚)
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 matrixbased 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 172 and Table 173 (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 172. Graph Properties Summary

Algorithm Description/Use Case Time Complexity BFS Traverses the graph by visiting neighbor nodes one level at a time $O \lparen V \space + \space E \rparen$ DFS Traverses the graph by going deep into each neighbor node one at a time $O \lparen V \space + \space E \rparen$ Dijkstra Finds the shortest path from one vertex to the rest of the other vertices $O \lparen V^{2} \space + \space E \rparen$ Topological Sort Sorts the directed graph; for job scheduling algorithms $O \lparen V \space + \space E \rparen$ Table 173. Graph Algorithm Summary
Up Next👉 Part 18: Advanced Strings (🔥🔥) (September 1920, 2020)
Posted on by:
Discussion