Graph Traversal, Trees & Applications: DFS, BFS, Trees, Spanning Trees

TAKEAWAYS:

• Graph traversal (DFS and BFS) explores nodes systematically, with DFS using recursion/depth-first and BFS using queues/level-order.
• Trees are acyclic connected graphs with hierarchical relationships, used to model nested structures like file systems or organizational charts.
• Spanning trees connect all vertices with minimal edges, critical for network design (e.g., minimizing cable costs in NTC’s fiber-optic backbone).
• Applications include pathfinding (Pathao’s ride routing), dependency resolution (Khalti’s transaction validation), and hierarchical data storage (Daraz’s product categories).
• Time complexity differs: BFS is $O(V+E)$ for level-order, while DFS is $O(V+E)$ but may use more memory for recursion stacks.
• Real-world tie: NEPSE’s stock price updates use tree structures to organize nested market data efficiently.

---

Graph Traversal: DFS and BFS

Graph traversal visits every node in a graph systematically. Two primary methods:

1. Depth-First Search (DFS): Explores as far as possible along a branch before backtracking.
2. Breadth-First Search (BFS): Explores all neighbors at the present depth before moving deeper.

How DFS Works

DFS uses a stack (implicitly via recursion or explicitly via a stack data structure). It marks nodes as visited to avoid cycles. Steps:

1. Start at a root node, mark it visited.
2. Push its unvisited neighbors onto the stack.
3. Pop a node, process it, and repeat for its neighbors.

Worked Example: Pathao’s Ride Routing Pathao’s algorithm uses DFS to explore possible routes from a rider’s location to destinations, prioritizing shortest paths by depth. Suppose a rider is at Thapathali and wants to reach Koteshwor. The graph represents streets as edges:

Thapathali --(5 min)--> Kalanki
Thapathali --(3 min)--> Bhatbhateni
Kalanki --(7 min)--> Koteshwor
Bhatbhateni --(4 min)--> Koteshwor

DFS Trace:

1. Start at Thapathali → visit Kalanki (5 min) → visit Koteshwor (12 min total).
2. Backtrack to Thapathali → visit Bhatbhateni (3 min) → visit Koteshwor (7 min total). Optimal path: Thapathali → Bhatbhateni → Koteshwor (7 min).

How BFS Works

BFS uses a queue to explore nodes level by level. It guarantees the shortest path in unweighted graphs. Steps:

1. Start at the root, enqueue it.
2. Dequeue a node, process it, and enqueue its unvisited neighbors.
3. Repeat until the queue is empty.

Worked Example: NTC’s Network Packet Routing NTC’s fiber-optic network uses BFS to route data packets efficiently. Suppose nodes are routers, and edges are fiber links with equal latency. To send a packet from Router A to Router E:

A -- B -- C -- E
A -- D -- E

BFS Trace:

1. Enqueue A → dequeue A, enqueue B and D.
2. Dequeue B, enqueue C.
3. Dequeue D, enqueue E (target found). Shortest path: A → D → E (2 hops).

Comparison Table: DFS vs. BFS

---

Trees in Graph Theory

A tree is a connected acyclic graph. Key properties:

• N-1 edges for N nodes.
• No cycles.
• Unique path between any two nodes.

Types of Trees

1. Binary Tree: Each node has at most 2 children.

2. Spanning Tree: Subgraph of a connected graph that includes all vertices with minimal edges.
   • Minimum Spanning Tree (MST): Spanning tree with the smallest total edge weight (used in Kruskal’s/Prim’s algorithms).

Worked Example: NEPSE’s Stock Market Hierarchy NEPSE organizes stocks into hierarchical categories (e.g., Banking, Hydro, Insurance). This forms a tree:

Root: NEPSE
├── Banking: NMB, NBL, Global IME
├── Hydro: Nepal Electricity Authority
└── Insurance: NIC Asia, Siddhartha

Why a Tree?

• Ensures no cycles (e.g., a stock can’t belong to both Banking and Hydro).
• Efficient lookup: To find all banking stocks, traverse the "Banking" subtree.

Applications of Trees

1. File Systems: Directories and subdirectories form trees (e.g., Windows Explorer).
2. Organizational Charts: Employees report to managers in hierarchical trees.
3. Decision Trees: Used in machine learning (e.g., classifying loan applicants in banks like NMB).

---

Spanning Trees and Applications

A spanning tree connects all vertices of a graph with the fewest edges. For weighted graphs, the Minimum Spanning Tree (MST) minimizes total edge weight.

Kruskal’s Algorithm (Greedy Approach)

1. Sort all edges by weight.
2. Add the smallest edge that doesn’t form a cycle.
3. Repeat until $N-1$ edges are added.

Worked Example: NTC’s Fiber-Optic Network NTC wants to connect 4 cities (A, B, C, D) with fiber links:

• A-B: 5 km
• A-C: 3 km
• B-C: 2 km
• C-D: 4 km
• B-D: 1 km

Kruskal’s Steps:

1. Sort edges: B-D (1), B-C (2), A-C (3), C-D (4), A-B (5).
2. Add B-D (1 km).
3. Add B-C (2 km). Total: 3 km.
4. Add A-C (3 km). Total: 6 km.
5. Stop (3 edges for 4 nodes). MST: B-D, B-C, A-C (total 6 km).

Prim’s Algorithm (Greedy, Vertex-Centric)

1. Start at any vertex, add its smallest edge.
2. From the growing tree, add the smallest edge connecting a new vertex.
3. Repeat until all vertices are included.

Comparison: Kruskal vs. Prim

---

Real-World Applications

1. Pathao’s Ride Matching

• Graph: Riders and drivers as nodes; edges represent possible matches based on location/time.
• Traversal: BFS finds the nearest available driver to a rider’s request, ensuring efficiency.
• Tree: Decision tree for fare calculation (e.g., base fare + distance + time).

2. Khalti’s Transaction Validation

• Graph: Transactions as nodes; edges represent dependencies (e.g., a payment must confirm before a withdrawal).
• Traversal: DFS validates transaction chains recursively to prevent fraud.
• Tree: Hierarchy of transaction types (e.g., peer-to-peer, merchant payments).

3. Daraz’s Product Catalog

• Tree: Categories (Electronics → Mobile → Smartphones) for efficient search.
• Traversal: BFS to explore all subcategories when a user searches for "phones."

4. NTC’s Network Redundancy

• Spanning Tree: Ensures backup paths if a fiber link fails (e.g., in Kathmandu-Pokhara route).
• Algorithm: Prim’s to minimize cable costs while ensuring connectivity.

5. NEPSE’s Stock Price Updates

• Tree: Organizes stocks by sector for quick updates (e.g., all banking stocks update simultaneously).
• Traversal: DFS to propagate price changes through the hierarchy.

---

Exam Tip

1. Understand the Difference Between DFS and BFS:

   • DFS uses a stack (recursion or explicit stack); BFS uses a queue.
   • DFS explores depth-first; BFS explores level-by-level.
   • Exam Question: Given a graph, trace DFS and BFS starting from a node. Show the order of visited nodes.

2. Spanning Trees and MST:

   • Know Kruskal’s (sort edges, add smallest) and Prim’s (start at a vertex, add smallest adjacent edge).
   • Exam Question: For a given weighted graph, construct the MST using both algorithms and compare their steps.

3. Applications:

   • Relate traversal algorithms to real-world systems (e.g., Pathao’s BFS for ride matching, NTC’s MST for network design).
   • Exam Question: "How would you use DFS/BFS to optimize [X] system?" (e.g., Daraz’s product search).

4. Time Complexity:

   • Both DFS and BFS are $O(V+E)$, but BFS uses more memory for large graphs.
   • Exam Question: "Why is BFS preferred for finding the shortest path in unweighted graphs?"

5. Tree Properties:

   • Memorize: A tree with $N$ nodes has $N-1$ edges and is acyclic.
   • Exam Question: "Prove that a graph with $N$ nodes and $N$ edges must contain at least one cycle."

6. Visual Proofs:

   • Draw graphs for traversal examples. Label nodes/edges clearly.
   • For spanning trees, show the original graph and the MST side by side.

---

Key Formula to Remember: For a connected graph with $V$ vertices and $E$ edges:

• A spanning tree has exactly $V-1$ edges.
• If $E>V-1$, the graph contains at least one cycle.