Graph Traversal

⏱ Time: O(V + E)💾 Space: O(V)

Traverse and manipulate networks of vertices connected by edges. Common representations include adjacency lists and matrices, explored via Breadth-First or Depth-First search.

🎯 When to Use

  • ✓Network routing and topology
  • ✓Social network connections
  • ✓Dependency resolution and cycle detection
  • ✓State machines and games

📝 Pseudocode

Graph Traversal TemplateO(V + E)
1function traverseGraph(adjList):
2  visited = new Set()
3  for vertex in adjList.keys():
4    if vertex not in visited:
5      explore(vertex, adjList, visited)

🏢 Real-World Use Cases

Meta
Social Graph

Modeling user friendships and entity relationships as nodes and edges to recommend friends and rank social feed items.

💡 Practice Problems (1)

1.Clone GraphMedium
→
← Back to Patterns