Graphs: Structure, Representation, and Traversal — Module Topics

Introduction to Graph Data Structures

• What Is a Graph? — A graph is a non-linear data structure used to model relationships between a collection of objects. Unlike arrays or linked lists, graphs do not follow a sequential or hierarchical structure.
• Vertices (Nodes) — A vertex, also called a node, is a fundamental unit of a graph that represents an entity or object. Vertices are the 'things' that a graph connects together.
• Edges (Connections) — An edge is a connection between two vertices in a graph, representing a relationship or link between those entities. Edges are what give graphs their expressive power.
• Directed vs. Undirected Graphs — One of the most fundamental distinctions in graph theory is whether the edges of a graph have a direction. This determines how relationships between vertices are interpreted.
• Key Graph Vocabulary — Graph theory comes with a specific set of terms used to describe the properties and characteristics of graphs and their components. Understanding this vocabulary is essential for studying graph algorithms.
• Real-World Applications of Graphs — Graphs are not merely theoretical constructs — they are used extensively across technology, science, and everyday applications. Understanding graphs provides the foundation for solving many practical problems.

Directed and Undirected Graphs

• What Is a Graph? — A graph is a data structure consisting of a set of nodes (vertices) connected by edges. Graphs model relationships between entities and serve as the foundation for both directed and undirected graph types.
• Undirected Graphs — In an undirected graph, edges have no defined direction, meaning the connection between two vertices is bidirectional. If vertex A is connected to vertex B, then B is equally connected to A.
• Directed Graphs (Digraphs) — In a directed graph, each edge has a specific direction, going from a source vertex to a destination vertex. The connection is one-way unless an explicit reverse edge is also defined.
• Real-World Use Cases for Undirected Graphs — Undirected graphs appear in many practical scenarios where relationships are inherently mutual. Recognizing these scenarios helps in selecting the right graph type for a problem.
• Real-World Use Cases for Directed Graphs — Directed graphs are essential when the relationship between entities has a clear and meaningful direction. Many computing and real-world systems exhibit this one-way dependency.
• Key Differences Between Directed and Undirected Graphs — Understanding the structural differences between directed and undirected graphs is critical for choosing the correct model and traversal strategy for a given problem.

Adjacency Matrix Representation

• What Is an Adjacency Matrix? — An adjacency matrix is a two-dimensional array used to represent a graph by recording which vertices are connected by edges.
• Representing Directed vs. Undirected Graphs — The structure of the adjacency matrix differs depending on whether the graph is directed or undirected.
• Space Complexity — An adjacency matrix always allocates space for every possible pair of vertices, regardless of how many edges actually exist.
• Time Complexity for Common Operations — The adjacency matrix offers constant-time edge lookups but linear-time neighbor enumeration.
• Advantages of the Adjacency Matrix — The adjacency matrix excels in scenarios where fast edge-existence queries are the primary operation.
• Trade-offs and Limitations — Despite its simplicity and fast lookups, the adjacency matrix has notable drawbacks that make it unsuitable for many real-world graphs.

Adjacency List Representation

• What Is an Adjacency List? — An adjacency list represents a graph as a collection of lists, one per vertex, where each list contains the neighbors of that vertex.
• Building an Adjacency List in JavaScript — Constructing an adjacency list involves initializing an entry for each vertex and then pushing neighbor references as edges are added.
• Space Complexity of the Adjacency List — Adjacency lists use space proportional to the number of vertices plus the number of edges, making them memory-efficient for sparse graphs.
• Adjacency List vs. Adjacency Matrix — The two primary graph representations trade off between fast edge lookup and efficient memory use, making each better suited to different scenarios.
• Directed vs. Undirected Graphs in Adjacency Lists — The adjacency list structure adapts naturally to both directed and undirected graphs by controlling how edges are recorded.
• When to Choose an Adjacency List — Adjacency lists are the default choice for most real-world graph problems because graphs encountered in practice tend to be sparse.

Breadth-First Search (BFS)

• What is Breadth-First Search? — Breadth-First Search (BFS) is a graph traversal algorithm that explores all neighbors of a node before moving to the next level of nodes.
• The Queue Data Structure in BFS — BFS relies on a queue — a First-In, First-Out (FIFO) data structure — to track which nodes to visit next.
• BFS Algorithm Logic Step by Step — The BFS algorithm follows a clear, repeatable sequence of steps to traverse all reachable nodes in a graph.
• BFS Traversal Order — The order in which BFS visits nodes is determined by their distance from the source, measured in the number of edges.
• Handling Disconnected Graphs in BFS — A single BFS call from one source node will only visit nodes reachable from that source; disconnected components require additional handling.
• Practical Applications of BFS — BFS has a wide range of real-world applications due to its ability to find shortest paths and explore nodes level by level.

Depth-First Search (DFS)

• DFS Core Concept and Strategy — Depth-First Search is a graph traversal algorithm that explores as far as possible along each branch before backtracking to try alternative paths.
• Recursive DFS Implementation — The recursive implementation of DFS leverages the program's call stack to track the current path and naturally handles backtracking when a function returns.
• Iterative DFS Implementation — An iterative DFS replaces the implicit call stack with an explicit stack data structure, making it safe for large graphs that might otherwise exceed recursion depth limits.
• DFS Traversal Order and Visited Tracking — Understanding how DFS orders its node visits is essential for correctly implementing and reasoning about the algorithm's behavior.
• Handling Disconnected Graphs — A single DFS call from one starting node will only visit nodes reachable from that node, so disconnected graphs require additional handling to ensure full traversal.
• Common Use Cases of DFS — DFS is a versatile algorithm used as the basis for solving many important graph problems beyond simple traversal.

Implementing Graph Traversal in JavaScript

• Setting Up the Graph Class in JavaScript — The foundation of graph implementation is creating a Graph class that manages vertices and edges using an adjacency list.
• Adding Edges to the Graph — Edges connect vertices and are stored by pushing neighbor references into each vertex's adjacency list array.
• Implementing Breadth-First Search (BFS) — BFS explores a graph level by level using a queue, visiting all neighbors of a node before moving deeper.
• Implementing Depth-First Search — Recursive Approach — The recursive DFS implementation uses the call stack to explore as deep as possible along each branch before backtracking.
• Implementing Depth-First Search — Iterative Approach — DFS can also be implemented iteratively using an explicit stack, which mirrors the recursive call stack manually.
• Comparing BFS and DFS Outputs in Practice — Running both BFS and DFS on the same graph highlights how traversal strategy affects the order in which vertices are visited.