算法导论 作业笔记

Posted by Cww97 on 2017-09-27

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/78115800
# 9/27 第三次作业

22.4-2

要求在一个有向无环图中,给定两点,求出这两点之间有多少条路径

伪代码:

1
2
3
4
5
6
7
8
9
list = topological_sort(G); 
create count[*] = 0;
count[s]=1
for each v in list
if(v!=t)
for each w in adj[v]
count[w] = count[w] + count[v];
else break;
return count[t];

复杂度:
O(V+E)

22.4-4

先说结论: 对于有环图,top排序不一定可以生成坏边最小的序列

证明:

  1. 假设G至少需要去掉k条边才能变成无环图,则任意序列P的坏边数目bad[P] >= k;

    证明: 如果存在P使得bad[P] < k, 则只要去掉P中的坏边则剩下的必然为无环图,这个和假设矛盾

    推论:存在序列P使得bad[P]=k,去掉k条边,然后top排序即可

  2. 对有环图进行拓扑排序得到的序列P, bad[P]和反向边数目相等

    证明:有反向边定义可证

  3. 需要证明反向边数和k的关系,通过反例可证明反向边树可能大于k

    DFS之后的树为A–>B->C, 然后存在C->B, C->A两条反向边,但是实际上只要去掉B->C一条边就可以变成无环图

    ps:其实直接通过反例证伪即可,上面的主要是记录我思考的过程

22.4-5

思考:
初始时,所有入度为0的顶点入队列
while队列不为空,作以下处理:
取队列头结点,并出队列
处理以头结点为起点的所有的边,将边的终点的入度-1
若入度减为0,则入队列
若G中包含回路:找不到入度为0的点,且G中仍然还有节点没有删除(剩下的就是G的回路)