🚀 BFS Solution for 'Evaluate Division' | Graph Traversal Approach | #Graph #BFS #Python #LeetCode

In this post/video, we solve the "Evaluate Division" problem from LeetCode using the BFS (Breadth-First Search) Approach. 🚀 This problem is an application of Graph Theory, where we are given division equations and need to answer queries based on these equations.

🔹 Given: Equations like a / b = 2.0, b / c = 3.0
🔹 Queries: Compute a / c = ?, b / a = ?, etc.
🔹 Undefined Variables: If a variable is not in the equations, return -1.0.

💡 Approach 2: Graph Representation + BFS Traversal
This approach treats the problem as a graph traversal problem, where each variable represents a node, and each division equation (A / B = value) represents a directed weighted edge.

🛠 Steps to Solve Using BFS

1️⃣ Graph Representation

Create an adjacency list where each node (variable) stores its neighbors and the corresponding weight (division value).
If a / b = 2.0, we add two edges:
a → b (weight 2.0)
b → a (weight 1/2.0)

2️⃣ Processing Queries Using BFS

For each query (Cj / Dj), perform BFS traversal starting from Cj.
Maintain a visited set to avoid cycles.
If we reach Dj, return the accumulated product of weights along the path.
If Dj is unreachable, return -1.0.

3️⃣ Edge Cases

If Cj or Dj does not exist in the graph, return -1.0.
If Cj == Dj, return 1.0 (division of a number by itself).

📌 Complexity Analysis

Graph Construction: O(N)
BFS Traversal for each query: O(N + Q)
Overall Complexity: O(N + Q), making it efficient for small to medium inputs. 🚀

📝 Python Solution (Approach 2 - BFS)

from collections import defaultdict, deque

class Solution:
def calcEquation(self, equations, values, queries):
# Step 1: Build the graph as an adjacency list
graph = defaultdict(list)
for (A, B), value in zip(equations, values):
graph[A].append((B, value)) # A → B (value)
graph[B].append((A, 1 / value)) # B → A (1/value)

# Step 2: Process each query using BFS
def bfs(source, target):
if source not in graph or target not in graph:
return -1.0 # Return -1 if either variable is missing

queue = deque([(source, 1.0)]) # Start BFS with the source node and initial weight 1.0
visited = set() # To avoid cycles

while queue:
if node == target:
return curr_value # Found target, return accumulated value

for neighbor, weight in graph[node]:
if neighbor not in visited:

return -1.0 # Target not reachable

return [bfs(C, D) for C, D in queries]

🛠 Example Walkthrough

🔹 Input:

equations = [["a", "b"], ["b", "c"]]
values = [2.0, 3.0]
queries = [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]

🔹 Graph Representation:

a → b (2.0), b → a (0.5)
b → c (3.0), c → b (1/3.0)

🔹 Processing Queries Using BFS:

1️⃣ a / c = 2.0 * 3.0 = 6.0
2️⃣ b / a = 1 / 2.0 = 0.5
3️⃣ a / e = -1.0 (e not in graph)
4️⃣ a / a = 1.0
5️⃣ x / x = -1.0 (x not in graph)

🔹 Output:

[6.0, 0.5, -1.0, 1.0, -1.0]

🔖 Why BFS Works Well?

✅ BFS guarantees the shortest path traversal
✅ No need to preprocess all paths, only traverse when needed
✅ More intuitive and flexible for graph traversal problems

🔥 This is a powerful and simple approach for solving the problem efficiently! 🚀