Computing · JC 2 · Abstract Data Structures and Algorithms · Semester 1

Graph Representations and Traversal Algorithms

Students will explore how information like text, images, and numbers are represented digitally using binary code.

• MOE Syllabus Outcomes
• MOE: Data and Information - Middle School

About This Topic

Graph representations and traversal algorithms form a core part of abstract data structures in the JC 2 Computing curriculum. Students compare adjacency matrices and adjacency lists, analysing space complexity and time costs for edge lookups, neighbour enumeration, and traversals. For sparse graphs, lists save space; for dense graphs, matrices speed up checks. This builds skills in algorithmic efficiency, essential for H2 Computing standards.

Traversal algorithms like BFS and DFS produce different visit orders on directed graphs. Students trace both, noting BFS suits shortest unweighted paths and level-order tasks, while DFS fits cycle detection and topological sorts. They design a DFS cycle detection algorithm using vertex colours (white, grey, black) and prove correctness for directed and undirected graphs. These connect to real-world networks like social graphs or web crawlers.

Active learning shines here because abstract concepts gain clarity through collaborative tracing and coding. When students physically simulate traversals with string and pins or code traversals in pairs, they spot patterns in orderings and complexities firsthand. This reduces errors in proofs and boosts confidence in algorithm design.

Key Questions

1. Compare adjacency matrix and adjacency list representations for sparse and dense graphs in terms of space complexity and the time cost of edge lookup, neighbour enumeration, and graph traversal.
2. Trace BFS and DFS on a directed graph, compare the orderings produced, and explain which problems each traversal is suited to solve (e.g., shortest unweighted path, cycle detection, topological sort).
3. Design a DFS-based algorithm to detect cycles in a directed graph using vertex colouring and prove its correctness for both directed and undirected cases.

Learning Objectives

• Compare the space and time complexities of adjacency matrix and adjacency list graph representations for sparse and dense graphs.
• Explain the distinct vertex visit orderings produced by Breadth-First Search (BFS) and Depth-First Search (DFS) on directed graphs.
• Design a Depth-First Search (DFS) algorithm using vertex coloring to detect cycles in a directed graph.
• Prove the correctness of a DFS-based cycle detection algorithm for both directed and undirected graphs.
• Analyze the suitability of BFS and DFS for solving specific graph problems, such as shortest unweighted path finding or topological sorting.

Before You Start

Introduction to Graphs

Why: Students need a foundational understanding of graph terminology, including vertices, edges, directed, and undirected graphs, before exploring representations and traversals.

Basic Algorithm Analysis (Big O Notation)

Why: Understanding Big O notation is essential for comparing the space and time complexities of different graph representations and traversal algorithms.

Recursion and Stacks

Why: Depth-First Search is often implemented using recursion or an explicit stack, so familiarity with these concepts is necessary.

Key Vocabulary

Adjacency Matrix	A square matrix used to represent a graph, where the value of cell (i, j) indicates if there is an edge between vertex i and vertex j.
Adjacency List	A collection of lists, where each list stores the neighbors of a particular vertex in the graph.
Breadth-First Search (BFS)	A graph traversal algorithm that explores the graph level by level, starting from a source vertex and visiting all its neighbors before moving to the next level.
Depth-First Search (DFS)	A graph traversal algorithm that explores as far as possible along each branch before backtracking, typically using a stack or recursion.
Vertex Coloring	Assigning colors (e.g., white, grey, black) to vertices during a graph traversal to track their state, such as unvisited, currently visiting, or fully visited.

Watch Out for These Misconceptions

Common Misconception

Adjacency matrices are always more efficient than lists.

What to Teach Instead

Matrices excel in dense graphs for O(1) lookups but waste space in sparse ones. Lists use O(V+E) space efficiently. Pair comparisons of real graphs reveal trade-offs, helping students choose representations contextually.

Common Misconception

BFS and DFS produce the same visit order on any graph.

What to Teach Instead

Orders differ: BFS is level-by-level, DFS is depth-first. Tracing both on the same graph in small groups highlights this, linking to applications like BFS for shortest paths. Group discussions solidify distinctions.

Common Misconception

Cycle detection works the same for directed and undirected graphs without adjustments.

What to Teach Instead

Directed graphs need back edges to ancestors; undirected need parent checks. Proving via colouring in collaborative proofs clarifies. Active simulations expose failures in naive approaches.

Active Learning Ideas

Stations Rotation: Graph Representations

Prepare stations with sample graphs: sparse, dense, directed. At matrix station, students build 2D arrays and test lookups. At list station, they construct linked lists and enumerate neighbours. Groups rotate, timing operations and comparing efficiencies.

45 min·Small Groups

Pair Tracing: BFS vs DFS

Provide printed directed graphs. Pairs trace BFS and DFS step-by-step, recording visit order and queue/stack states. They discuss suited problems, like shortest path for BFS. Pairs present one difference to class.

30 min·Pairs

Whole Class: Cycle Hunt Simulation

Draw a large graph on board. Class votes on start vertex; teacher guides DFS with colours, pausing for predictions on back edges. Students note recursion stack. Repeat with cycle-free graph for contrast.

35 min·Whole Class

Individual: Code and Test Traversals

Students implement BFS/DFS in Python on given graphs. They add print statements for orderings, run on test cases including cycles. Submit traces with complexities.

50 min·Individual

Real-World Connections

• Social network analysts use graph traversal algorithms like BFS to find the shortest path between two users, identifying 'degrees of separation' for marketing or connection recommendations.
• Logistics companies employ graph representations and traversal algorithms to plan efficient delivery routes, optimizing for time or distance by analyzing road networks as graphs.
• Cybersecurity professionals utilize DFS with vertex coloring to detect cycles in network traffic logs, identifying potential malicious loops or denial-of-service attack patterns.

Assessment Ideas

Quick Check

Provide students with a small directed graph represented by both an adjacency matrix and an adjacency list. Ask them to calculate the space complexity for each representation and the time taken to find all neighbors of a specific vertex using each method.

Exit Ticket

Present a directed graph. Ask students to trace both BFS and DFS starting from a given vertex, listing the order in which vertices are visited for each. Then, ask them to explain which traversal is better suited for finding the shortest path in this unweighted graph.

Discussion Prompt

Facilitate a class discussion on the DFS cycle detection algorithm. Ask students to explain the role of each color (white, grey, black) and to provide a scenario where this algorithm would be crucial for identifying issues in a system.

Frequently Asked Questions

How to compare adjacency matrix and list for JC2 students?

Start with space analysis: matrix is O(V^2), list O(V+E). Time lookups: matrix O(1), list O(degree). Use sparse/dense examples; students compute for graphs with V=10, E=15 vs E=80. Coding both and benchmarking builds intuition on trade-offs.

What active learning strategies teach BFS and DFS traversals?

Hands-on tracing with physical models or digital tools engages students deeply. Pairs simulate queues/stacks with cards, predicting orders before coding. Class-wide board traces reveal patterns missed alone. This active approach cuts tracing errors by 40% and links traversals to problems like shortest paths or cycles.

How to teach DFS cycle detection with vertex colouring?

Introduce colours: white (unvisited), grey (visiting), black (done). Back edge to grey signals cycle. Students trace on paper, then code recursively. Prove by contradiction: cycles force grey ancestors. Test on directed/undirected cases reinforces generality.

Why focus on graph traversals in MOE Computing?

Traversals underpin network analysis, AI search, and optimisation. JC2 mastery prepares for H2 projects like pathfinding. Comparing BFS/DFS complexities hones Big O skills. Real applications, like social network cycles, motivate abstract learning.