Basics

• BFS 的使用场景
  • 图的遍历 graph traversal
  • 简单图求最短路径 shortest path in graph
  • o(m+n) m - 边数 n - 顶点数
• 图的表示
  • https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs
  • edge lists
  • adjacency matrices
  • adjacency lists

class UndirectedGraphNode {
    int label;
    List<UndirectedGraphNode> neighbors;

    UndirectedGraphNode(int label) {
        this.label = label;
        this.neighbors = new ArrayList<>()
    }
}

Problems

clone graph: http://www.lintcode.com/en/problem/clone-graph/

topological sort: http://www.lintcode.com/en/problem/topological-sorting/

• http://www.geeksforgeeks.org/topological-sorting/

course schedule: https://leetcode.com/problems/course-schedule/description/

graph valid tree: https://leetcode.com/problems/graph-valid-tree/description/

is reachable

topological sort

hasCycle