Review: Graph Problems

Graph related questions mainly focus on depth first search and breath first search.



Common graph algorithm problems:

  1. Count regions: Number of Islands
  2. Get the size of the largest region: Max Area of Island
  3. Update a specific region: Flood Fill
  4. Update regions for a given rule: Surrounded Regions
  5. Mark levels: 01 Matrix

Typical Problems:

1. How to get the initial set to examine?
2. How to move to next? What's the time complexity?
3. What if we want all possible answers, instead of the min step count?

Questions:

  1. Why so many algorithms to find the shortest path? Shouldn’t it be some optimal one(s)?

BFS:

BFS:

  1. visit all neighbors before visiting neighbors of your neighbors
  2. Keep a queue of nodes to visit
  3. The performamce may be different if we search from starting point or target point. Perfect Squares

Common graph algorithm problems:

  1. Find length of shortest path from node s to all other nodes
  2. Search all nodes for a node containing a given value
  3. Find shortest path from node s to all other nodes

DFS:

  1. visit all neighbors of a neighbor before visiting your other neighbors
  2. It doesn’t use queue, but mark nodes as to their status. White(unchecked), Gray(Seen, but not finished), Black(finished)

Key points:

  • How to evaluable the time complexity. Normally it’s O(m*n). But how we can convince people with solid argument?

For DFS, if the path is too deep, we might run into stack overflow.

The most impressive problems to me:


See all grap problems: #grap

See more blog_posts.

linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.