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

**Basic Abstractions**

Name | Summary |
---|---|

bfs and dfs relationship | Leetcode: Word Ladder II |

From BFS to Bidirectional BFS | Half of the time. Leetcode: Word Ladder |

3 cases: state is invalid/visited/unexamined | Leetcode: Word Ladder |

Bridge | Bridge is an edge, when removed, will disconnect the graph |

Duplicate edge | |

Cycle in undirected graphs | |

Cycle in DAG | Leetcode: Redundant Connection II |

**Questions**

Name | Example |
---|---|

For matrix graph problems: rectangle vs square | |

Kruskal’s algorithm: Minimum spanning tree of a weighted graph | Leetcode: Connecting Cities With Minimum Cost |

Dijkstra’s algorithm: shortest path for two nodes in a weighted graph | |

Floyd-Warshall algorithm: find shortest paths in a weighted graph | |

Move in different directions: 4 directions, 8 directions | Leetcode: Queens That Can Attack the King |

Keep moving in the same direction | Leetcode: Queens That Can Attack the King |

Floyd-Warshall algorithm: Time O(n*n*n)

BFS/DFS/UnionFind; Binarysearch

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?

- Move in 4 directions

// https://code.dennyzhang.com/as-far-from-land-as-possible // ... for len(queue) > 0 { nexts := [][]int{} for _, node := range queue { i, j := node[0], node[1] for _, offset := range [][]int{[]int{1, 0}, []int{-1, 0}, []int{0, 1}, []int{0, -1}} { i2, j2 := i+offset[0], j+offset[1] if i2<0 || i2>=len(grid) || j2<0 || j2>=len(grid[0]) || grid[i2][j2] == 1 { continue } grid[i2][j2] = 1 nexts = append(nexts, []int{i2, j2}) } } level++ queue = nexts }

- Move in 9 directions

// https://code.dennyzhang.com/queens-that-can-attack-the-king // ... i, j := king[0], king[1] for x:=-1; x<=1; x++ { for y:=-1; y<=1; y++ { if x==0 && y==0 { continue } // keep searching this direction i2, j2 := i+x, j+y for i2>=0 && i2<8 && j2>=0 && j2<8 { if m[[2]int{i2,j2}] { res = append(res, []int{i2, j2}) break } i2, j2 = i2+x, j2+y } } }

Questions:

- 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:

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

Common graph algorithm problems:

- Find length of shortest path from node s to all other nodes
- Search all nodes for a node containing a given value
- Find shortest path from node s to all other nodes

DFS:

- visit all neighbors of a neighbor before visiting your other neighbors
- 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: #graph

- Review: Graph Problems
- LintCode: Social Network
- LintCode: Sliding Puzzle III
- LintCode: Island City
- Leetcode: Word Search
- Leetcode: Word Ladder II
- Leetcode: Word Ladder
- Leetcode: The Maze II
- Leetcode: Surrounded Regions
- Leetcode: Shortest Bridge
- Leetcode: Redundant Connection II
- Leetcode: Redundant Connection
- Leetcode: Reconstruct Itinerary
- Leetcode: Queens That Can Attack the King
- Leetcode: Possible Bipartition
- Leetcode: Path With Maximum Minimum Value
- Leetcode: Pacific Atlantic Water Flow
- Leetcode: Number of Islands II
- Leetcode: Number of Islands
- Leetcode: Maximum Level Sum of a Binary Tree
- Leetcode: Max Area of Island
- Leetcode: Island Perimeter
- Leetcode: Is Graph Bipartite?
- Leetcode: Flood Fill
- Leetcode: Find the Celebrity
- Leetcode: Find Eventual Safe States
- Leetcode: Escape a Large Maze
- Leetcode: Employee Importance
- Leetcode: Critical Connections in a Network
- Leetcode: Contain Virus
- Leetcode: Connecting Cities With Minimum Cost
- Leetcode: Coloring A Border
- Leetcode: Clone Graph
- Leetcode: Bricks Falling When Hit
- Leetcode: As Far from Land as Possible
- Leetcode: All Paths from Source Lead to Destination
- Leetcode: 01 Matrix

See more blog_posts.