Almost every graph question is solved by walking the graph: start somewhere and visit every vertex you can reach. There are exactly two ways to walk, and the rest of this course is built on them.
A tree has no cycles, so walking it can never loop. A graph can: from 0 you reach 1, from 1 you're right back at 0. So every graph walk keeps a visited set and never enters a vertex twice. Forget it and the walk runs forever.
Members only · free account
The rest of this lesson, with 4 more sections, 2 dry-run simulators and code in JavaScript, Python, Java and C++, opens with a free account.
Not ready yet? The Arrays course is free to read, no account needed.
In the rest of this lesson