12 graph （BFS）

这里主要是讲些图相关的bfs和dfs题，还有就是topological sort了。bfs主要就是用个Queue，dfs就是递归搜索了。BFS的时间复杂度都是O(m+n)，m是边数，n是点数

技巧：

如果是矩阵的话可以用 i * m + j来避免用pair class
上面那个其实很难记住，某次pramp的时候，某亚洲面孔小哥哥，指了条名路。可以用int[] .Queue<int[]> q = new LinkedList<>(); q.add(new int[]{i, j});
搜的时候可以考虑用direction matrix， int[] x = {0, 0, 1, -1}, int[] y = {1, -1, 0, 0}，然后loop k 从 0 -- 4

如果是扫雷那样8个方向的话，用这个

    int[] x = {0, 0, -1, 1, 1, 1, -1, -1};
    int[] y = {-1, 1, 0, 0, 1, -1, 1, -1};

BFS / DFS :

L477 Surrounded Regions - 也可以用union find来做&DFS (130)

200 Number of Islands (L433) - BFS/DFS/Union Find

695 Max Area of Island -- 跟200 Number of Islands几乎一样，还是bfs/dfs/union find都能解

694 Number of Distinct Islands

711 Number of Distinct Islands II

302 Smallest Rectangle Enclosing Black Pixels - 还可以用bfs，不过2分比较好 (L600)

133 Clone Graph --与138 Copy LIst with Random Pointer有点关系

399 Evaluate Division

301 Remove Invalid Parentheses

286 Walls and Gates

417 Pacific Atlantic Water Flow

317 Shorest Distance from All Buildings (L573 Build Post Office II)

490 The Maze

505 The Maze II

499 The Maze III

332 Reconstruct Itinerary

L531 Six Degrees

L431 Connected Component in Undirected Graph - can use bfs or dfs or union find as well （求联通块里具体有什么node） (323 Number of Connected Components in an Undirected Graph -- 求联通块个数)

L618 Search Graph nodes

L611 Knight Shortest Path

L598 Zombie in Matrix

994 Rotting Oranges

529 Minesweeper

785 Is Graph Bipartite

Detect Cycle in directed graph -- dfs

Detect Cycle in undirected graph -- dfs / union find

419 Battleships in a Board

PrintShortestPath - bfs with backtrack, Uber

743 Network Delay Time -- Dijkstra （BFS）

1631 Path With Minimum Effort