教材全解_算法导论

题目	题型
证明：使用单个位来存放每个节点的颜色已经足够，这一点可以通过证明如下事实来...	问答
证明：边（u,v）是： a.树边或前向边当且仅当u.d<v.d...	问答
证明：在无向图中，根据深度优先搜索算法是先探索（u,v）还是先探索（v,u...	问答
请重写DFS算法的伪代码，以便使用栈来消除递归调用。	问答
请给出如下猜想的一个反例：如果有向图G包含一条从节点u到节点v的路径，则任...	问答
修改深度优先搜索的伪代码，让其打印出有向图G的每条边及其分类，并指出，如果...	问答
请解释有向图的一个节点u怎样才能成为深度优先树中的唯一节点。即使节点u同时...	问答
证明：我们可以在无向图G上使用深度优先搜索来获得G的连通分量，并且深度优先...	问答
对于有向图G=(V,E)来说，如果意味着图G至多包含一条从u到v的简单路径...	问答
给出算法TOPOLOGICAL-SORT运行在下图时所生成的节点次序。	问答
请给出一个线性时间的算法，算法的输入为一个有向无环图G=(V,E)以及两个...	问答
给出一个算法来解决判断给定无向图G=(V,E)是否包含一个环路，算法运行时...	问答
证明或反证下述断论：如果有向图G包含环路，则在算法TOPOLOGICAL-...	问答
在有向无环图G=(V,E)上执行拓扑排序还有一种方法，就是重复寻找入度为0...	问答
如果在图G中加入一条新的边，G中的强连通分量的数量会发生怎样的变化？	问答
给出算法STRONGLY-CONNECTED-COMPONENTS在下图运...	问答
Bacon教授声称，如果在第二次深度优先搜索时使用原始图G而不是图G的转置...	问答
证明：对于任意有向图G来说(（G^T）^SOC...	问答
给出一个时间复杂度为O(V+E)的算法来计算有向图G=(V,E)的分量图，...	问答
给定有向图G=(V,E)，请说明如何创建另一个图G'=(V,E')，使得：...	问答

题目

题型

证明：使用单个位来存放每个节点的颜色已经足够，这一点可以通过证明如下事实来...

问答

证明：边（u,v）是： a.树边或前向边当且仅当u.d<v.d...

问答

证明：在无向图中，根据深度优先搜索算法是先探索（u,v）还是先探索（v,u...

问答

请重写DFS算法的伪代码，以便使用栈来消除递归调用。

问答

请给出如下猜想的一个反例：如果有向图G包含一条从节点u到节点v的路径，则任...

问答