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:

• Find the minimum steps from point1 to point2: Word Ladder, Sliding Puzzle
• Find all minimum paths from point1 to point2: Word Ladder II

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:

• When to update visited_set? When add or when pop? Employee Importance

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:

• Perfect Squares
• Island Perimeter
• Surrounded Regions
• Swim in Rising Water

---

See all grap problems: #grap

See more blog_posts.

---