COMP2521 26T2 Week 5 Lecture 2

This lecture covers fundamental graph traversal methods (DFS and BFS) and their applications to solving four key graph problems: cycle detection using DFS with visited and predecessor arrays, connected components identification through DFS traversal, Hamiltonian path/circuit finding using recursive DFS with backtracking (NP-complete), and Eulerian path/circuit determination based on vertex degree analysis (tractable). The instructor demonstrates how to implement these algorithms, analyze their complexity (O(V+E) for Eulerian problems, factorial for Hamiltonian problems), and distinguishes between tractable and intractable graph problems.