DSA AnimatorDSA animations
Evaluate Division LC #399 Medium Graph · Weighted BFS
Problem

Equations a/b=k. Queries c/d. Build graph a→b(k), b→a(1/k). BFS from src, multiply weights. Return product if path exists else -1.

Example
Input: equations=[a/b=2,b/c=3], queries=[a/c,b/a]
Output: [6.0, 0.5]
Try Examples
Approach
Weighted Graph + BFS
a/b=v → edge a→b(v), b→a(1/v). Query x/y: BFS from x, multiply edge weights. Product = answer.
Graph & Results
Load an example.
Variables
Query
—
Curr
—
Acc
—
Result
—
Step Logic
Press ▶ Play or Next Step.
✓
Ready
0/0
Select example and Play.
Algorithm
1
Build graph: a→b(v), b→a(1/v)
2
BFS from src, multiply weights
3
Product = answer or -1
Time
O((V+E)·Q)
Space
O(V+E)
Why Product

a/b=2, b/c=3 → a/c = (a/b)*(b/c) = 2*3 = 6. BFS multiplies edge weights along path.

How to solve Evaluate Division

LeetCode 399 · Medium · Graph · Pattern: Weighted Graph DFS

Why the obvious approach is slow

Trying to solve the equations algebraically is complicated. Instead, picture every variable as a node in a graph.

The key idea

For a over b equal to 2, add an edge from a to b with weight 2, and from b to a with weight one half. The answer to x over y is the product of the weights along any path from x to y. This works because the middle variables cancel out: a over b times b over c is a over c. If either variable is unknown, or no path exists, the answer is −1.

Remember

Ratios become edge weights, and a path multiplies them. The reverse edge always has the reciprocal weight.

Run the animation above on your own input, or watch the 2:00 video explanation of Evaluate Division with a dry run and Java code.

More Graph problems