Graph Traversal

Graph traversal means visiting every vertex a start vertex can reach, and the topic teaches the two ways to do it. Breadth-first search opens it: a queue visits vertices in order of distance, and a gotcha shows why the visited mark goes on as a vertex joins the queue. Depth-first search follows, with a stack and three colours, and a code card writes both in Python, Java and TypeScript. The rest is what the searches find. Breadth-first parents give shortest paths when every edge costs the same, and a maze grid shows a graph that is never written down. Grey vertices detect a cycle in a directed graph, and an outer loop counts components and tests for two colours. An exercise splits market stalls between two days.