习题课_图.pptx

习题课 图 林秋燕linqiuyan 题目 画出原图 写出其邻接矩阵 写出每个点的入度和出度 从顶点v2出发 分别画出其深度优先搜索和广度优先搜索的生成森林 1 答案 a 原图 b 邻接矩阵 邻接矩阵为 01 0 8 1 3 0 0 352 2 66 05 0 3 0 0 c 每个点的出度入度 V0 出度2 入度1V4 出度2 入度0V1 出度1 入度3V5 出度1 入度2V2 出度3 入度1V6 出度2 入度1V3 出度1 入度2V7 出度0 入度2 d 1 从顶点v2出发的深度优先搜索生成的森林如下 d 2 从顶点v2出发的广度优先搜索生成的森林如下 2 设计算法判断一有向图G是否有环 答案 图中的一个节点 根据其C N 的值 有三种状态 0 此节点没有被访问过 1 被访问过至少1次 其后代节点正在被访问中1 其后代节点都被访问过 按照这样的假设 当按照DFS进行搜索时 碰到一个节点时有三种可能 1 如果C V 0 这是一个新的节点 不做处理2 如果C V 1 说明是在访问该节点的后代的过程中访问到该节点本身 则图中有环 3 如果C V 1 类似于2的推导 没有环 题目证明 只要适当地排列顶点的次序 就能使有向无环图的邻接矩阵中主对角线以下的元素全部为0 答案 任意n个结点的有向无环图都可以得到一个拓扑序列 设拓扑序列为v0v1v2 vn 1 我们来证明此时的邻接矩阵A为上三角矩阵 证明采用反证法 假设此时的邻接矩阵不是上三角矩阵 那么 存在下标i和j i j 使得A i j 不等于零 即图中存在从vi到vj的一条有向边 由拓扑序列的定义可知 在任意拓扑序列中 vi的位置一定在vj之前 而在上述拓扑序列v0v1v2 vn 1中 由于i j 即vi的位置在vj之后 导致矛盾 因此命题正确 3 证明题 题目Dr Stranger的电脑染上了一种特殊的病毒 该病毒发作时会将字母用其他字母代替 但不会将单词顺序交换 也不会产生新的字母 在病毒发作前文档D中的单词顺序为字典排序 比如在字典序下单词ab会排在单词ac前 且文档D中所有的单词只由字母集合 a b c d e 中的字母组成 病毒发作后文档D中的所有单词顺序如下 cebdbac cac ecd dca aba bac 求文档D在病毒发作前的内容 并说明解题思路和步骤 答案 解题的主要思路就是推断病毒发作后文档D中的字母顺序 与字典序的字母顺序进行一一对应即可 具体方法就是从相邻的两个字符串之间推断字母之间的顺序 如题目中单词cac在单词ecd之前 所以可以推断被替换后的字母顺序中字母c在字母e之前 将字母之间的顺序关系看成有向边 画出字母关系图 然后对图进行拓扑排序 得出的序列就是病毒发作后文档D中的字母顺序 4 答案 续 该题中可求得字母的顺序关系图如下 通过拓扑排序 得到的病毒发作后文档D中的字母顺序 c e d a b 而字典序为 a b c d e 所以可以判断病毒将字母a替换为字母c 将字母b替换为字母e 将字母c替换为字母d 将字母d替换为字母a 将字母e替换为字母b 最终文档D的原内容如下 abeceda ada bac cad ded eda 请证明kruskal算法的正确性 命题 对任意的n阶带权图G 算法能得到G的一棵最小生成树 5 题目 单源最短路径问题中 当路径中存在负权边时 不存在负权回路 不可以使用Dijkstra算法 注 题中分析时间复杂度时 默认存储结构是邻接表 且使用最小堆存储源点到各点的路径值 a 一种想法是 先在每条边上加上一个常数 从而消除负权边 然后再利用Dijkstra算法 请问这种算法可行吗 若可行 请说明理由并分析时间复杂度 若不可行 请举反例 b 另外一种想法是 利用Dijkstra算法 在算法运行过程中 若w已经在S中 但是由于与w相邻的点加入S中而新计算得到的dist w 比S中存储的dist w 还要小 那么将w从S中剔除 重新加入未知集合T中 请问这种算法可行吗 若可行 请说明理由并分析时间复杂度 若不可行 请举反例 6 Dijkstra算法 含负权边图 答案 a 不可行 能举例说明由于加上常数后 结果出错即可 比如 p1 v1 v2 3 v2 v3 4 p2 v1 v3 8 都是从v1到v3路径 最短路径应该选p1 若此时整个图中存在某个负权为 5 则均加上5 那么再利用算法时 选择了p2 v1 v3 13 而p1 v1 v2 8 v2 v3 9 不选 b 可行 因为当一个点v在已知集合S中 则在以后的算法步数中 不再检查经过点v的路径 但是因为存在负权边 可能v的权重会变的更小 此时所有经过v到达的点 权值均可能改变 则按照改进的算法 v会重新加入T 会重新计算 则最后肯定能得到正确的结果 分析复杂度 每次加入一个节点j到S中 前面所有的节点的值dist i i j 都会减少 按照算法 前面所有的节点都要从S中剔除 并且这些被剔除的节点又要重新加入S中 即导致了前面所有节点再重新更新一次 这就得到了一个递推的公式 设更新节点j时的总共需要更新的节点数是t j 则有 tj 0 i j t1 1 可以得到 tn 2 1当更新一个节点时 所做的操作都是先更新自己的dist 最多是O