[summary] Graph BFS solves problems

210: Course Schedule II
269: Alien Dictionary
题目描述见网站

210: 课程的dependency本来就存在edges数组表示,可以转换成map方便访问,然后对graph进行bfs
269: 从dict中抽出字母先后顺序,字母组成一个graph,对graph进行bfs

bfs的过程:

Queue先存入in degree为0的点
当queue不为空时:
取出点,加入结果
此点在map中指向的所有下一个点,给他们的in degree都减1
此时in degree为0的点重新加入queue

其实是有顺序的bfs,顺序为先访问dependency最小的点。这个方法两道题都可以解决。