•作业讲解 –TC第22.1节练习3、8–TC第22.2节练习3、4、5–TC第22.3节练习6、7、8、9、12–TC第22.4节练习2、3–TC第22.5节练习5、7
1 TC第22.1节练习
8 •找到点的位置时间是O
(1)，哈希链表的查找时间是O(α)，所以总共查找时间为O(1+α) •哈希表的缺点：空间消耗太大•改进：BST•改进之后的缺点：时间消耗增加
2 TC第22.3节练习
7 •需要注意整个图不连通的情况
3 TC第22.4节练习
2 •从起始点开始，根据拓扑排序的结果向后搜索•Funcition(G,u,v) –除了u以外的点count为0，count[u]=1–根据拓扑排序结果，对每个节点n依次进行： •Forallminadj[n]count[m]+=count[n] –returncount[v] •不建议用DFS –不易写对，写对了时间复杂度也很高
4 TC第22.4节练习
3 •如何证明算法的时间复杂度是O(|V|)？ –如果不存在回边，那么|E|=|V|-
1，DFS复杂度为O(|E|)=O(|V|)–如果存在回边，那么在检测到回边的时候算法就终止了，之前检测过的子图必然 是不存在回边的，那么算法时间复杂度也是O(|V|)
5 •教材讨论 –TC第23章
6 问题1：Genericmethod •什么样的边称作safe？•safe边为什么一定存在？•如何证明这个算法的正确性？
7 问题1：Genericmethod(续) •定理23.1的作用是什么？ •请结合这个图，简述定理的主要证明过程。

8 问题1：Genericmethod(续) ••
9 问题1：Genericmethod(续) • 10 问题2：KruskalandPrim •Kruskal和Prim分别如何选择safe边？ •请简述Kruskal和Prim的实现方法 11 问题2：KruskalandPrim(续) • 12 问题2：KruskalandPrim(续) • 13