Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Introduction to Graph Pattern

You are given a network of cities joined by roads, and two city names. Decide whether you can drive from the first to the second.

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

is there a route from 0 to 2?  yes
is there a route from 0 to 5?  no

A tree would make this easy, because a tree has exactly one route between any two nodes and it never doubles back. A graph offers neither guarantee. Two cities can be joined by several roads, and a road can lead you back where you started.

Run a plain tree traversal on that and it never stops. From 0 you visit 1. From 1 you visit 0

.....

.....

.....

Like the course? Get enrolled and start learning!