Introduction to Graph Pattern

You are given cities connected by roads. Decide whether a route exists between two cities.

0 --- 1 --- 2        4 --- 5

route from 0 to 2: yes
route from 0 to 5: no

A graph contains nodes and edges. In this example, cities are nodes and roads are edges.

Unlike a tree, a graph may contain cycles. A route can return to a node that was already visited.

A tree traversal without extra protection can loop forever:

visit 0 -> visit 1 -> visit 0 -> visit 1 -> ...

The solution is to remember visited nodes. Process each node at most once.