八、请给出如下猜想的一个反例：如果有向图G包含一条从结点u到结点v的路径，并且在对图G进行深度优先搜索时有u.d<v.d，则结点v是结点u在深度优先森林中的一个后代。如果要写代码，请用go语言。...

七、请重写DFS算法的伪代码，以便使用栈来消除递归调用。如果要写代码，请用go语言。

六、证明：在无向图中，根据深度优先搜索算法是先探索(u，v)还是先探索(v，u)来将边(u，v)分类为树边或者后向边，与根据分类列表中的4种类型的次序进行分类是等价的。如果要写代码，请用go语言。...

四、证明：使用单个位来存放每个结点的颜色已经足够。这一点可以通过证明如下事实来得到：如果将DFS-VISIT的第8行删除，DFS给出的结果相同。如果要写代码，请用go语言。...

一、画一个 $3times3$ 的网格，行和列的抬头分别标记为白色、灰色和黑色。对于每个表单元 (i，j) ，请指出在对有向图进行深度优先搜索的过程中，是否可能存在一条边，连接一个颜色为 i 的结点和一个颜色为 j 的结点。对于每种...

九、设$G=(V,E)$为一个连通无向图。请给出一个$O(V+E)$时间的算法来计算图$G$中的一条这样的路径:该路径正反向通过$E$中每条边恰好一次(该路径通过每条边两次，但这两次的方向相反)。如果给你大量的分币作为奖励，请描述...

八、我们将一棵树$T=(V，E)$的直径定义为$max_{(u,v)∈V}δ(u,v)$，也就是说，树中所有最短路径距离的最大值即为树的直径。请给出一个有效算法来计算树的直径，并分析算法的运行时间。如果要写代码，请用go语言。...

七、职业摔跤手可以分为两种类型:“娃娃脸”(“好人”)型和“高跟鞋”(“坏人”)型。在任意一对职业摔跤手之间都有可能存在竞争关系。假定有 n 个职业摔跤手，并且有一个给出竞争关系的 r 对摔跤手的链表。请给出一个...

六、举出一个有向图$G=(V，E)$的例子，对于源结点$s∈V$和一组树边$E_π∈E$，使得对于每个结点 $v∈V$，图$(V，E_π)$中从源结点$s$到结点$v$的唯一简单路径也是图$G$中的一条最短路径，但是，不管邻接链表里结点之间的次序如何，边...

五、证明：在广度优先搜索算法里，赋给结点 u 的 u.d 值与结点在邻接链表里出现的次序无关。使用图 22-3 作为例子，证明：BFS 所计算出的广度优先树可以因邻接链表中的次序不同而不同。如果要写代码，请用go语言。...