avatar_url

Sandesh Rana | Python

I'm a developer from Himalayas, with a passion for crafting efficient and elegant code, with creativity and precision.

Graph Theory

21 Aug 2024 » programming, math

Graph Theory: Easy to Hard Problems

Easy

  1. Number of Islands (Counts the number of islands in a grid)
  2. Valid Sudoku (Validates a Sudoku board)
  3. Flood Fill (Fills connected regions with a new color)
  4. Graph Valid Tree (Checks if a given graph forms a valid tree)
  5. Shortest Path in Binary Matrix (Finds the shortest path in a binary matrix from top-left to bottom-right)

Medium

  1. Course Schedule (Determines if all courses can be finished given prerequisites)
  2. Minimum Height Trees (Finds the roots of trees with the minimum height)
  3. Network Delay Time (Finds the time it takes for all nodes to receive a signal from a source node)
  4. Topological Sort (Finds a valid ordering of courses given prerequisites)
  5. Critical Connections in a Network (Finds all critical connections in a network graph)

Hard

  1. Reconstruct Itinerary (Reconstructs an itinerary from a list of tickets)
  2. Shortest Path in a Grid with Obstacles Elimination (Finds the shortest path in a grid with obstacles and allowed eliminations)
  3. Graph Bipartiteness (Checks if a graph is bipartite)
  4. Find the Weakly Connected Component in the Graph (Finds the weakly connected component in a directed graph)
  5. Networkx Maximum Flow Problem (Finds the maximum flow in a flow network)