Graphs: Structure, Representation, and Traversal — Topics & Learning Outcomes

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.

Student Learning Outcomes

By the end of this module, students will be able to:

Course Outcomes (reference)