Graphs

Master graph traversal, shortest paths, and advanced graph algorithms.

Showing 20 of 20 questions
Easy: 0 Medium: 0 Hard: 0
QUESTIONDIFFICULTY
Depth-First Search (DFS)
Implement depth-first search traversal for graphs
Easy
All Paths From Source to Target
Find all possible paths from source node to target node in a directed acyclic graph (DAG)
Medium
Bellman-Ford Algorithm
Find shortest paths from a source vertex to all other vertices in a weighted graph, capable of handling negative edge weights
Medium
BFS Shortest Path in Unweighted Graph
Find shortest path between two vertices in an unweighted graph using BFS traversal
Medium
Breadth-First Search (BFS)
Implement breadth-first search traversal of a graph
Medium
Clone Graph
Create a deep copy of an undirected graph represented with adjacency lists
Medium
Course Schedule
Determine if you can finish all courses given prerequisite relationships using topological sorting
Medium
Detect Cycle in Directed Graph
Determine if a directed graph contains a cycle
Medium
Detect Cycle in Undirected Graph
Determine if an undirected graph contains a cycle
Medium
Floyd-Warshall Algorithm - All Pairs Shortest Path
Find shortest paths between all pairs of vertices in a weighted graph using dynamic programming
Medium
Is Graph Bipartite
Check if a graph can be colored with exactly two colors such that no two adjacent nodes have the same color
Medium
Minimum Spanning Tree
Find the minimum spanning tree of a weighted undirected graph using Kruskals and Prims algorithms
Medium
Network Delay Time (Dijkstras Algorithm)
Find the time it takes for a signal to reach all nodes in a network using shortest path algorithms
Medium
Number of Islands
Count the number of islands in a 2D grid
Medium
Strongly Connected Components
Find all strongly connected components in a directed graph
Medium
Topological Sort
Find a linear ordering of vertices in a directed acyclic graph
Medium
Alien Dictionary
Given a sorted dictionary of alien language, find the order of characters in the alien alphabet
Hard
Articulation Points (Cut Vertices)
Find all articulation points in an undirected graph - vertices whose removal increases the number of connected components
Hard
Find Bridges in a Graph
Find all bridges (critical edges) in an undirected graph using Tarjans algorithm
Hard
Word Ladder
Find the shortest transformation sequence from beginWord to endWord using single character changes
Hard

Overview

Graphs are versatile data structures used to model relationships and networks. This section covers graph representation, traversal, and advanced algorithms.

Key Concepts

  • Graph representation (adjacency list, matrix)
  • Depth-first search (DFS)
  • Breadth-first search (BFS)
  • Shortest path algorithms (Dijkstra, Bellman-Ford)
  • Topological sorting
  • Union-find (disjoint set)

Common Problems

Easy

  • Find if Path Exists in Graph
  • Number of Islands
  • Clone Graph
  • Course Schedule

Medium

  • Number of Connected Components
  • Pacific Atlantic Water Flow
  • Word Ladder
  • Network Delay Time

Hard

  • Word Ladder II
  • Alien Dictionary
  • Critical Connections in a Network

Practice Tips

  1. Choose traversal wisely: DFS for paths, BFS for shortest paths
  2. Track visited nodes: Prevent infinite loops
  3. Graph representation: Choose based on density
  4. Time complexity: Consider V (vertices) and E (edges)

Resources