chapter06
复制本地路径 | 在线编辑
1. 关联矩阵
1.1 说明无向图关联矩阵的定义是什么,指出其和邻接矩阵的关系
1.2 说明有向图关联矩阵的定义是什么,指出其和邻接矩阵的关系
2. 简述增加定点引起的向量扩容,并且证明分摊复杂度为O(n)
3. 证明平面图满足e = O(n)
4. BFS-相关问题
4.1 分别说明BFS有哪几种边，每种类型对应于什么情况，分有向和无向
5. DFS-相关问题
5.1 分别说明DFS有哪几种边，每种类型对应于什么情况，分有向和无向
5.2 证明: u是v的祖先 当且仅当 [dtime(u),ftime(u)] [dtime[v],ftime(v)]
5.3 证明: u和v没有承袭关系 当且仅当 [dtime(u),ftime(u)] [dtime(v),ftime(v)]=
5.4 证明: 假设当前节点为v,则u为DISCOVERED 当且仅当 u是v的祖先
5.5 将DFS算法改成PFS的格式，即给出DFS的优先级判断和更新标准
6. 相关算法
6.1 判断无向图是否是欧拉环路，存在则给出
6.2 判断有向图是否有拓扑排序，存在则给出
6.3 输入有向图，返回强连通分量
6.4 输入有向图，返回双联通分量个数和相应关节点
6.5 输入有向图，保证权值为正且无循环，求(s,u)的最长距离
7. Prim算法
7.1 给出消除重复边引起的歧义的算法，并证明算法的正确性
7.2 证明Prim算法的正确性
8. 判断题汇总
8.1 对于有负边的图，Prim算法是否适用，是给证明，否给反例
8.2 对于有负边的图，Dijkstra算法是否试用，是给证明，否给反例
8.3 对于无权值一样边的图，Dijkstra算法结果是否唯一，是给证明，否给反例
8.4 对于一幅图，如果每条边都加上1，Dijkstra算法原来的结果是否正确，是给证明，否给反例
8.5 对于一幅图，如果每条边都乘以2，Dijkstra算法原来的结果是否正确，是给证明，否给反例