Graph Traversal, Trees & Applications: DFS, BFS, Spanning Trees & Real-World Uses

TAKEAWAYS:

• Graph traversal (DFS/BFS) explores nodes systematically: DFS uses a stack (LIFO) for depth-first exploration, while BFS uses a queue (FIFO) for breadth-first exploration.
• Trees are connected acyclic graphs with hierarchical structures, used to model hierarchies (e.g., organizational charts) and optimize search/insertion operations (e.g., binary search trees).
• Spanning trees connect all vertices of a graph with the minimum number of edges (no cycles), critical for network design (e.g., NTC’s fiber-optic backbone).
• Applications include pathfinding (Pathao’s delivery routes), social networks (Khalti’s transaction graphs), and scheduling (Daraz’s order processing).
• Key theorems: Kirchhoff’s theorem counts spanning trees via matrix determinants; Euler’s formula links vertices, edges, and faces in planar graphs.
• Exam focus: Prove properties (e.g., "A graph has a spanning tree iff it’s connected"), compare traversal algorithms, and apply concepts to real scenarios (e.g., NEPSE’s stock market dependency graph).

1. Graph Traversal: DFS and BFS

Graph traversal visits all vertices of a graph in a systematic way. Two primary methods:

• Depth-First Search (DFS): Uses a stack (LIFO). Explores as far as possible along a branch before backtracking.
• Breadth-First Search (BFS): Uses a queue (FIFO). Explores all neighbors at the present depth before moving deeper.

How They Work

graph TD
    A["Start at Vertex S"] --> B["DFS: Push S to stack, pop and visit S"]
    B --> C["Mark S as visited"]
    C --> D["Push unvisited neighbors of S (e.g., A, B) to stack"]
    D --> E["Pop A, visit A, repeat"]
    E --> F["Backtrack if no unvisited neighbors"]
    G["BFS: Enqueue S, dequeue and visit S"] --> H["Enqueue unvisited neighbors (A, B)"]
    H --> I["Dequeue A, visit A, enqueue its neighbors"]

Key Differences

Worked Example: Pathao’s Delivery Route Optimization

Scenario: Pathao needs to find the shortest route from a restaurant to a customer’s doorstep, avoiding traffic jams (represented as blocked edges). Graph Representation:

• Vertices: Intersections (A, B, C, D).
• Edges: Roads with weights (travel time).
• Traversal: Use BFS to find the shortest path in an unweighted graph (simplified model).

graph TD
    A["Restaurant"] -->|"5 min"| B["Intersection 1"]
    A -->|"10 min"| C["Intersection 2"]
    B -->|"3 min"| D["Customer"]
    C -->|"7 min"| D

BFS Steps:

1. Start at A, enqueue A.
2. Dequeue A, enqueue B and C (distance = 1).
3. Dequeue B, enqueue D (distance = 2 via B).
4. Result: Path A → B → D (total 8 minutes) is shorter than A → C → D (17 minutes).

2. Trees: Properties and Applications

A tree is a connected acyclic graph. Key properties:

• Rooted Tree: One vertex designated as the root (e.g., organizational hierarchy).
• Binary Tree: Each node has at most 2 children (used in binary search trees).
• Leaf: Node with no children (e.g., end of a file system path).

Tree Traversals

graph TD
    A["Root"] --> B["Left Subtree"]
    A --> C["Right Subtree"]
    B --> D["Node 1"]
    B --> E["Node 2"]
    C --> F["Node 3"]

Types:

1. Pre-order: Root → Left → Right (e.g., serializing a file system).
2. In-order: Left → Root → Right (e.g., BST in-order gives sorted list).
3. Post-order: Left → Right → Root (e.g., deleting a tree).

Real-World Example: Khalti’s Transaction Graph

Khalti uses trees to model transaction dependencies:

• Root: Initial payment request.
• Children: Sub-transactions (e.g., merchant verification, fund transfer).
• Leaves: Final confirmation or failure nodes. Why Trees?
• Ensures no cycles (prevents double-charging).
• Efficient rollback: If a leaf fails, only its subtree is reversed.

3. Spanning Trees and Applications

A spanning tree of a connected graph $G$ is a subgraph that:

1. Includes all vertices of $G$.
2. Is a tree (no cycles, connected).

Kirchhoff’s Theorem (Matrix-Tree Theorem)

Counts the number of spanning trees in a graph using determinants: For a graph $G$ with $n$ vertices, the number of spanning trees $=\frac{1}{n}\times$ determinant of any cofactor of its Laplacian matrix.

Example: Wheel Graph $W_3$

• Vertices: 4 (center + 3 outer vertices).
• Edges: 6 (3 spokes + 3 rim edges). Laplacian Matrix $L$:

| 3 -1 -1 -1 |
|-1  2 -1  0 |
|-1 -1  2  0 |
|-1  0  0  2 |

Steps:

1. Remove any row/column (e.g., last row/column).
2. Compute determinant of the remaining 3×3 matrix:

   | 3 -1 -1 |
   |-1  2 -1 |
   |-1 -1  2 |
   

3. Determinant = $3(4-1)-(-1)(-2+1)+(-1)(1+2)=9-1-3=5$.
4. Number of spanning trees = $\frac{5}{4}\times 4=5$.

Visualization:

graph TD
    A["Center"] --> B["Outer 1"]
    A --> C["Outer 2"]
    A --> D["Outer 3"]
    B --> C
    C --> D
    D --> B

Possible Spanning Trees:

1. All 3 spokes.
2. 2 spokes + 1 rim edge (e.g., spokes to B/C + rim B-C).
3. 1 spoke + 2 rim edges (e.g., spoke to B + rims B-C and C-D).

4. Planar Graphs and Euler’s Formula

A planar graph can be drawn on a plane without edge crossings. Euler’s Formula for connected planar graphs: $$V-E+F=2$$ where:

• $V$ = vertices,
• $E$ = edges,
• $F$ = faces (including the outer face).

Example: Kathmandu Traffic Network Scenario: Model intersections (vertices) and roads (edges) to check if traffic lights can be optimized without crossings. Graph:

• $V=10$ (intersections),
• $E=15$ (roads),
• $F=7$ (blocks + outer area). Check: $$10-15+7=2$$ → Planar (can be drawn without crossings).

Application: NTC uses planar graph theory to design non-overlapping fiber-optic cable routes.

5. Graph Representations

Worked Example: Ncell’s Tower Coverage Graph: Towers (vertices) and coverage areas (edges). Adjacency Matrix:

|   | A | B | C |
|---|---|---|---|
| A | 0 | 1 | 1 |
| B | 1 | 0 | 0 |
| C | 1 | 0 | 0 |

Interpretation:

• Tower A covers B and C.
• Towers B and C only cover A (no direct link between B and C).

6. Applications in Nepalese Context

a. eSewa’s Service Dependency Graph

• Vertices: Services (e.g., bill payment, ticket booking).
• Edges: Dependencies (e.g., "ticket booking" depends on "user authentication").
• Traversal: DFS to validate service chains before processing.

b. Daraz’s Order Processing Queue

• Vertices: Orders (e.g., Order123, Order456).
• Edges: Processing steps (e.g., "Order123 → Payment → Packing").
• BFS: Ensures orders are processed in FIFO order (fairness).

c. NEPSE’s Stock Market Dependency

• Vertices: Stocks (e.g., NABIL, NMB).
• Edges: Correlation (e.g., "NABIL’s price affects NMB").
• Spanning Tree: Identifies critical dependencies for risk assessment.

7. Proofs and Counting

Theorem: A connected graph with $n$ vertices has at least $n-1$ edges.

Proof:

1. Start with a tree (minimal connected graph): $n-1$ edges.
2. Adding any edge creates a cycle.
3. Thus, no connected graph can have fewer than $n-1$ edges.

Counting Paths in a Graph

Example: How many paths from A to D in the graph below?

graph TD
    A --> B
    A --> C
    B --> D
    C --> D

Solution:

• Paths: A→B→D, A→C→D.
• Total: 2 paths.

In the Real World

1. Pathao’s Route Optimization

   • Idea Used: BFS for shortest-path finding in unweighted graphs.
   • How: Converts Kathmandu’s roads into a graph where intersections are vertices and roads are edges. BFS finds the fastest route avoiding traffic (blocked edges).

2. Khalti’s Transaction Validation

   • Idea Used: Tree traversal (DFS) to validate transaction dependencies.
   • How: Each transaction is a node; dependencies are edges. DFS ensures no circular dependencies (e.g., "Transfer X requires Transfer Y, which requires Transfer X").

3. NTC’s Fiber-Optic Network Design

   • Idea Used: Spanning trees and planar graphs.
   • How: NTC models cities as vertices and fiber links as edges. A spanning tree ensures all cities are connected with minimal cable (cost-saving). Planar graphs help avoid physical cable crossings in trenches.

4. Daraz’s Order Processing

   • Idea Used: Queue (BFS) for fair order fulfillment.
   • How: Orders are enqueued upon receipt. BFS processes them in arrival order, ensuring no order is delayed indefinitely (unlike DFS, which might prioritize complex orders).

5. NEPSE’s Stock Correlation Analysis

   • Idea Used: Graph adjacency matrices to model stock dependencies.
   • How: Stocks are vertices; edges represent correlation coefficients. Analysts use adjacency matrices to identify clusters (e.g., banks vs. hydropower stocks) and predict market shifts.

Exam Tip

1. Graph Traversal:

   • DFS: Use a stack. Always backtrack when no unvisited neighbors remain.
   • BFS: Use a queue. Guarantees shortest path in unweighted graphs.
   • Exam Pitfall: Forgetting to mark vertices as visited leads to infinite loops.

2. Trees:

   • Spanning Tree: Must include all vertices and have no cycles. For $n$ vertices, it has exactly $n-1$ edges.
   • Kirchhoff’s Theorem: Only applies to connected undirected graphs. Practice computing Laplacian matrices.

3. Planar Graphs:

   • Euler’s Formula: $V-E+F=2$ for connected planar graphs. For disconnected graphs, add $k$ (number of components).
   • Real-World Check: If $V-E+F\ne 2$, the graph is non-planar (e.g., $K_5$ or $K_{3,3}$).

4. Proofs:

   • Induction: Base case + inductive step. For graphs, often use the number of edges/vertices.
   • Counting: Use adjacency matrices or recursive relations (e.g., "Number of paths of length $k$ from A to B").

5. Applications:

   • Pathfinding: Always use BFS for unweighted shortest paths (e.g., Pathao routes).
   • Network Design: Spanning trees minimize cost (e.g., NTC’s fiber network).
   • Dependency Analysis: Trees/graphs model hierarchies (e.g., Khalti transactions).

6. Common Exam Questions:

   • Define and compare: DFS vs. BFS, spanning tree vs. minimum spanning tree.
   • Prove: "A graph with $n$ vertices and $n$ edges has a cycle."
   • Apply: Given a graph, find all spanning trees or shortest paths.
   • Real-World: "How would you model Daraz’s order processing system as a graph?" (Answer: Vertices = orders, edges = dependencies; use BFS for FIFO processing.)

Visual Summary:

mindmap
  root((Graph Traversal & Trees))
    DFS
      stack
      backtracking
      example: maze solving
    BFS
      queue
      shortest path
      example: Pathao routes
    Trees
      acyclic
      connected
      applications: file systems, org charts
    Spanning Trees
      minimal edges
      Kirchhoff's theorem
      example: NTC network
    Planar Graphs
      Euler's formula
      real-world: traffic networks