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 |

Common graph representations | Adjacent matrix, adjacent list, hashmap of hashmaps |

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

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

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

Duplicate edge | |

Cycle in undirected graphs | |

Cycle in DAG | LeetCode: Redundant Connection II |

For matrix graph problems: rectangle vs square |

**Top 10 Graph Algorithm**

Num | Problem | Summary |
---|---|---|

1 | Dijkstra’s algorithm | Greedy. Shortest path for two nodes in a weighted grap. See #dijkstra |

2 | Bellman-Ford algorithm | Shortest path for two nodes in a weighted graph + negative edges. See #floyd |

3 | Floyd-Warshall algorithm | Find shortest paths in a weighted graph |

4 | Kruskal’s algorithm | Union find + Greedy. Minimum Spanning Tree(MST). |

5 | Prim’s algorithm | Greedy + Heap. Minimum Spanning Tree(MST). |

6 | Tarjan’s algorithm | Cut node |

7 | Cut edge | |

8 | Topological Sort | Node dependencies |

9 | #bipartite | Whether graph is a bipartite graph |

**Top Questions**

Num | Problem | Summary |
---|---|---|

1 | Graph Connectivity: Count islands in a 2D matrix | LeetCode: Number of Islands, LeetCode: Island Perimeter |

2 | Get the size of the largest island | LeetCode: Max Area of Island |

3 | Cycle detection in a directed graph | LeetCode: Redundant Connection II |

4 | Detect all cycles in a directed graph | LeetCode: Find Eventual Safe States |

5 | Whether a graph is a tree | LeetCode: Graph Valid Tree |

6 | Update a specific region | LeetCode: Flood Fill |

7 | Update regions for a given rule | LeetCode: Surrounded Regions |

8 | Number of Distinct Islands | LeetCode: Number of Distinct Islands |

9 | Mark levels | LeetCode: 01 Matrix |

10 | Diameter of a tree in graph theory | LeetCode: Tree Diameter |

11 | Duplicate edges | LeetCode: Reconstruct Itinerary |

12 | Find a certain node in a graph | LeetCode: Find the Celebrity |

13 | Graph with next steps by a trie | Leetcode: Word Search II |

14 | Coloring graph | LeetCode: Minesweeper |

15 | Find a certain path from source to destination in a graph | LeetCode: Path With Maximum Minimum Value |

16 | Find the minimum steps from point1 to point2 | LeetCode: Word Ladder, LeetCode: Sliding Puzzle |

17 | Find all minimum paths from point1 to point2 | LeetCode: Word Ladder II |

18 | All Paths from Source Lead to Destination | LeetCode: All Paths from Source Lead to Destination |

19 | Node connectivity problem for a sparse 2D matrix | LeetCode: Escape a Large Maze |

20 | Bricks Falling When Hit | LeetCode: Bricks Falling When Hit |

21 | Bridges in a connected graph – Tarjan’s algorithm | LeetCode: Critical Connections in a Network |

22 | Valid & Invalid moves | LeetCode: Alphabet Board Path |

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

24 | String Transforms Into Another String | LeetCode: String Transforms Into Another String |

25 | Candidates are (i, j, r), instead of (i, j) | LeetCode: Shortest Path in a Grid with Obstacles Elimination |

26 | Clone Graph | Leetcode: Clone Graph |

27 | Array problem with hidden graph | LeetCode: Number of Squareful Arrays |

28 | Find shortest paths in a weighted graph | LeetCode: Find the City With the Smallest Number of Neighbors |

29 | Find shortest distance for two nodes in an undirected graph | |

30 | Graph trasversal from boarders | Leetcode: Surrounded Regions |

31 | Is Graph Bipartite | LeetCode: Is Graph Bipartite |

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: Web Crawler
- Leetcode: Tree Diameter
- Leetcode: The Maze II

See more blog posts.