CS61B - Lec 29 - Graphs2, BFS, DFS
Lec 29 - Graphs2, BFS, DFS
这一章学了具体怎么实现Graph。
BreadthFirstPaths
BreadthFirst，广度优先，意思就是从根节点开始，遍历完所有到根节点距离相同的节点，再遍历下一个深度的。
再复习一遍DepthFirst，从根节点开始，遍历完一个子集，然后再遍历下个子集。
上节课的结尾提出了这样一个问题：找到s到其他顶点最短的path。距离最短，很容易就想到广度优先遍历。
答案是这样的。首先要用到queue数据结构，有着enqueue和dequeue两个方法，像队列一样。
下面看具体的例子：
第一步，把0加入队列，并设置disTo[0] = 0。
进入循环，截止条件是队列为空。
- remove队列的头并返回，目前是0
- 遍历unmarked neighbor，这里只有1，mark(1)，加入队列，edgeTo[1] = 0(连接1和0），最后disTo[0] = disTo[0] + 1 = 1
然后重复循环，remove掉1，遍历1的neighbor2和4，mark, 加入队列，dist++。这时，距离根节点0距离为2的节点就遍历完了。
接着，是距离为3的两个节点5和3.
然后，是5的两个neighbor，6和8
3没有neighbor了，没有操作，对6进行操作，加入最后一个节点7。最后对8和7进行操作，无neighbor，所以无操作，remove掉之后循环结束。
Graph API
API就是接口，interface，先想好这个结构要实现什么功能，具体结构的实现有多种方式。
选择的标准是：runtime, memory和实现的难度。
Reprensentation and Runtimes
现在看如何实现这个adj方法。
- 用一个二维矩阵，0代表不相连，1代表相连。
可以看到是有一些冗余的结构，每组连接被表示了两次，看runtime的问题：
每个顶点都要遍历，每个顶点的每个neighbor都要遍历，表格是V * V，所以runtime是O(V2)。
- 建一个Edge的集合，每个Edge用两个顶点表示。
- 建一个hashTable，index代表顶点编号，存储相邻的节点list。
分析3的runtime。此时需要遍历的顶点数是V，每个顶点需要遍历的neighbor可能的范围是1~V(中心散射或者单一相连)。最好的情况是O(V)，最坏的情况是O(V2)，似乎算不出runtime。
答案其实是O(V + E)。V是顶点数量，E是边的数量。
实际的graph还是用的adjacency list。
Graph Traversal Implementation and Runtime
常见的graph算法是独立于graph类的。先建立一个graph对象，然后传递给一个graph-processing方法in a client class。
以下是深度优先的实现方式。
再分析广度优先的runtime。
