Graphs

A graph is a non-linear data structure consisting of vertices (nodes) connected by edges. Unlike trees, graphs can have cycles and multiple paths between nodes.

Key properties:

• Vertices (V): The nodes in the graph
• Edges (E): Connections between vertices
• Directed vs Undirected: Edges have direction or not
• Weighted vs Unweighted: Edges have costs or not
• Cyclic vs Acyclic: Contains cycles or not (DAG = Directed Acyclic Graph)

Representations:

• Adjacency Matrix: 2D array, O(V²) space, O(1) edge lookup
• Adjacency List: Array of lists, O(V+E) space, O(degree) edge lookup
• Edge List: List of edges, O(E) space, good for some algorithms

• Real-world modeling: Social networks, maps, dependencies, circuits, web pages

  • Versatile structure: Can represent almost any relationship
  • Rich algorithms: DFS, BFS, Dijkstra, Floyd-Warshall, Kruskal, Tarjan
  • Interview frequency: ~15% of coding problems, often challenging

  Common applications:

  • Social networks (friends, followers)
  • Maps and navigation (shortest path)
  • Task scheduling (topological sort)
  • Network flow (max flow, min cut)
  • Recommendation systems (collaborative filtering)
  • Compiler design (dependency graphs)

  Performance varies by algorithm:

  • DFS/BFS: O(V + E)
  • Dijkstra: O((V + E) log V) with heap
  • Floyd-Warshall: O(V³)
  • Kruskal/Prim MST: O(E log E)

Use graphs when you need to model:

1. Relationships: Connections between entities (social networks)
2. Networks: Roads, flights, internet, electrical circuits
3. Dependencies: Task prerequisites, package dependencies
4. State spaces: Game states, puzzle configurations
5. Hierarchies with cross-links: Unlike trees, nodes can have multiple parents

Common problem types:

• Connectivity (connected components, islands)
• Cycle detection (detect loops, deadlocks)
• Shortest path (navigation, routing)
• Topological sort (task scheduling, build order)
• Minimum spanning tree (network design)
• Strongly connected components (web crawling)
• Bipartite matching (assignment problems)

1. DFS (Depth-First Search) Explore as far as possible before backtracking:

• Detect cycles
• Find connected components
• Topological sort (postorder in DAG)
• Path finding
• Time: O(V + E), Space: O(V)

2. BFS (Breadth-First Search) Explore neighbors level by level:

• Shortest path in unweighted graph
• Level-order traversal
• Bipartite check
• Time: O(V + E), Space: O(V)

3. Dijkstra's Algorithm Shortest path in weighted graph (non-negative weights):

• Use priority queue (min-heap)
• Greedy approach
• Time: O((V + E) log V)

4. Union-Find (Disjoint Set Union) Track connected components efficiently:

• Union: Connect two components
• Find: Check if two nodes are connected
• Time: O(α(n)) ≈ O(1) with path compression

Traversal problems:

• Number of islands (connected components)
• Clone graph
• All paths from source to target
• Word ladder (BFS on implicit graph)

Shortest path:

• Dijkstra for weighted graphs
• BFS for unweighted graphs
• Bellman-Ford for negative weights
• Floyd-Warshall for all pairs

Cycle detection:

• DFS with color marking (white/gray/black)
• Union-Find for undirected graphs
• Detect back edges

Topological sort:

• DFS-based (postorder)
• Kahn's algorithm (BFS with in-degree)
• Course schedule problems

Minimum spanning tree:

• Kruskal's (sort edges, union-find)
• Prim's (grow tree from vertex)

• Not handling disconnected graphs: May need to start DFS/BFS from multiple sources
  • Infinite loops: Forgetting to mark visited nodes
  • Directed vs undirected: Different edge representations and algorithms
  • Negative cycles: Dijkstra doesn't work; use Bellman-Ford
  • Memory issues: Large graphs may not fit in memory (use streaming algorithms)
  • Wrong representation: Adjacency matrix for sparse graphs wastes space
  • Not considering self-loops or multi-edges: May need special handling

1. Find connected components? → DFS or Union-Find
2. Shortest path (unweighted)? → BFS
3. Shortest path (weighted, non-negative)? → Dijkstra
4. Shortest path (negative weights)? → Bellman-Ford
5. All pairs shortest path? → Floyd-Warshall
6. Detect cycle? → DFS with color marking
7. Topological sort? → DFS postorder or Kahn's algorithm
8. Minimum spanning tree? → Kruskal or Prim
9. Check if bipartite? → BFS/DFS with 2-coloring
10. Dynamic connectivity? → Union-Find