Graph Patterns

This file lists commonly used graph patterns for DSA problems, along with typical problem types, keywords, and usage guidance. Focus on pattern recognition first, then implementation. Understanding triggers will help identify the right algorithm efficiently.

---

**Pattern Table **

Pattern	Typical Question Types	Keywords in Question	Why Use / Notes
BFS	Shortest path, Levels	breadth, queue, neighbor	Level-by-level exploration; shortest path unweighted
DFS	Connected components, Cycle detection	depth, recursion, stack	Explore path fully before backtracking
Topological Sort	Dependency resolution, Task scheduling	order, prerequisites	Use DFS or Kahn’s algorithm for ordering
Dijkstra / Bellman-Ford	Shortest path with weights	weighted, shortest	Priority queue (Dijkstra) or relaxation (Bellman-Ford)
Union-Find / Disjoint Set	Connected components, Kruskal MST	merge, find, parent	Efficiently detect cycles; track components
Minimum Spanning Tree	Kruskal/Prim	MST, min cost	Greedy approach to build MST
Eulerian Circuit / Path	Eulerian path/cycle	all edges visited	Special graph properties: in/out degrees
XOR Graph Problems (Bonus)	Special bitwise graph problems	XOR, edges	Use XOR along paths or pairs

---

Mini Notes / Tips

### Tips

- BFS is ideal for unweighted shortest path, level order traversal, or when exploring neighbors layer by layer.
- DFS is ideal for connected components, cycle detection, and backtracking.
- Topological sort helps in dependency resolution, scheduling tasks, and DAG-related problems.
- Dijkstra is for shortest paths with non-negative weights; Bellman-Ford handles negative weights and detects negative cycles.
- Union-Find efficiently tracks connected components and is crucial in Kruskal’s MST and cycle detection problems.
- Minimum Spanning Tree patterns often appear with Kruskal or Prim algorithms; greedy choice is key.
- Eulerian Circuit/Path problems are rare but critical for specialized graph problems involving all edges.
- XOR Graph Problems combine bit manipulation with graph traversal; often appear as rare bonus problems.

---

Graph Patterns – Detection & Usage Guide

1. BFS – Common (Graph & Tree)

When to use / Detection cues:

• Input structure: Graph or tree, unweighted edges.
• Question keywords: breadth, queue, level, shortest.
• Problem hints: Shortest path in unweighted graph, find levels, or explore neighbors layer by layer.
• Why it works: BFS explores nodes level by level, guaranteeing minimal steps in unweighted graphs.

Typical questions:

• Shortest path in unweighted graph
• Level order traversal of a tree
• Minimum moves on a grid

Mental trigger: “Level-by-level” + “queue” → BFS.

---

2. DFS – Common (Graph & Tree)

When to use / Detection cues:

• Input structure: Graph or tree, may be connected/disconnected.
• Question keywords: depth, recursion, stack, explore fully.
• Problem hints: Connected components, cycle detection, path existence, topological order.
• Why it works: DFS explores paths fully before backtracking; easy to implement recursively or with stack.

Typical questions:

• Count connected components
• Detect cycles in graph
• Path existence in maze/graph

Mental trigger: “Explore path fully” + “recursion/stack” → DFS.

---

3. Topological Sort – Common (Graph only)

When to use / Detection cues:

• Input structure: Directed acyclic graph (DAG).
• Question keywords: prerequisites, order, dependency.
• Problem hints: Task scheduling, course prerequisite ordering.
• Why it works: DFS post-order or Kahn’s algorithm generates valid topological ordering.

Typical questions:

• Course schedule / prerequisites
• Build system task ordering
• Dependency resolution

Mental trigger: “Dependency/order” + “DAG” → Topological Sort.

---

4. Dijkstra / Bellman-Ford – Common (Graph only)

When to use / Detection cues:

• Input structure: Weighted graph (non-negative for Dijkstra; can have negative for Bellman-Ford).
• Question keywords: weighted, shortest, distance, min path.
• Problem hints: Compute shortest paths efficiently; detect negative cycles (Bellman-Ford).
• Why it works: Dijkstra uses a priority queue; Bellman-Ford relaxes edges iteratively.

Typical questions:

• Shortest path in weighted graph
• Detect negative cycle
• Minimum cost path

Mental trigger: “Weighted shortest path” → Dijkstra/Bellman-Ford.

---

5. Union-Find / Disjoint Set – Common (Graph only)

When to use / Detection cues:

• Input structure: Undirected graph, often edge list.
• Question keywords: merge, find, parent, connected components.
• Problem hints: Detect cycles, maintain connected components, Kruskal’s MST.
• Why it works: Union-Find allows O(α(n)) merges and finds efficiently.

Typical questions:

• Count connected components
• Detect cycle in undirected graph
• Kruskal’s MST

Mental trigger: “Merge/find components” → Union-Find.

---

6. Minimum Spanning Tree – Common (Graph only)

When to use / Detection cues:

• Input structure: Weighted undirected graph.
• Question keywords: MST, min cost, connect all nodes.
• Problem hints: Connect all vertices with minimal total edge cost.
• Why it works: Greedy selection of minimum edge while avoiding cycles (Kruskal/Prim).

Typical questions:

• Kruskal’s MST
• Prim’s MST
• Minimum cost to connect points

Mental trigger: “Connect all nodes with minimum cost” → MST.

---

7. Eulerian Circuit / Path – Rare (Graph only)

When to use / Detection cues:

• Input structure: Graph (directed or undirected).
• Question keywords: visit all edges exactly once, Eulerian.
• Problem hints: Check in/out degrees (directed), all vertices even (undirected) to determine existence.
• Why it works: Special degree properties determine path or cycle existence.

Typical questions:

• Find Eulerian path or circuit
• Verify if Eulerian tour exists
• Construct Eulerian trail

Mental trigger: “All edges exactly once” → Eulerian Circuit / Path.

---

8. XOR Graph Problems – Rare / Bonus

When to use / Detection cues:

• Input structure: Graph with weighted edges; usually XOR properties involved.
• Question keywords: XOR, path, edges.
• Problem hints: Find paths or pairs using XOR; combine with DFS/BFS or bit manipulation.
• Why it works: XOR properties (associative, cancels duplicates) combined with traversal help solve special problems.

Typical questions:

• XOR along path between nodes
• Count pairs with XOR = target
• Specialized bitwise graph queries

Mental trigger: “XOR + Graph” → XOR Graph Problems.