算法导论20.4 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 1.9k 阅读时长 ≈ 2 分钟

20.4-1

可以得出上图\(G\)的所有节点信息如下：

\(\begin{array}{|l|l|l|l|}\hline v&v.d&v.f&v.\pi\\\hline m&1&20&\text{NIL}\\\hline q&2&5&m\\\hline t&3&4&q\\\hline r&6&19&m\\\hline u&7&8&r\\\hline y&9&18&r\\\hline v&10&17&y\\\hline w&11&14&v\\\hline z&12&13&w\\\hline x&15&16&v\\\hline n&21&26&\text{NIL}\\\hline o&22&25&n\\\hline s&23&24&o\\\hline p&27&28&\text{NIL}\\\hline \end{array}\)

因此，按照\(v.f\)从大到小的顺序列出所有\(v\)，即可得到\(G\)的其中一个拓扑序列：

\[p\rightarrow n\rightarrow o\rightarrow s\rightarrow m\rightarrow r\rightarrow y\rightarrow v\rightarrow x\rightarrow w\rightarrow z\rightarrow u\rightarrow q\rightarrow t\]

20.4-2

考虑使用动态规划的思想来解决本题。

令\(f_G(s,t)\)表示在有向无环图\(G\)，从\(s\)到\(t\)的路径条数。那么可以写出如下状态转移方程：

\(f_G(s,t)= \left \{\begin{aligned} &1 & & \text{if}\quad s=t \\ &\sum_{u\in G.Adj[s]} f_G(u,t) & & \text{if}\quad s\neq t\ \end{aligned}\right.\)

方程的第二行说明，从\(s\)到\(t\)的所有路径，可以看作是\(s\)的后继节点\(w\)到\(t\)的所有路径前面再添加一个\(s\)即可。由于\(G\)是一个有向无环图，\(f_G\)并不会形成循环。我们可以考虑从\(G\)的拓扑序列上实现计算\(f_G\)的过程。计算\(f_G(u,v)\)的算法由CAL-PATHS过程给出。

1
2
3
4
5
6
7
8
9
10
11
CAL-PATHS(G, s, t)
  order = TOPOLOGICAL-SORT(G)
  REVERSE(order)                // 对拓扑系列order进行逆序
  for each u in order
    if u == t
      u.paths = 1
    else
      u.paths = 0
        for each v in G.Adj[u]
          u.paths = u.paths + v.paths
  return s.paths

20.4-3

根据定理B.2的第5条和第6条可以得知，如果无向图\(G\)有超过\(|V|-1\)条边，那么\(G\)必定是有环的，我们不遍历整个图并直接返回结果。否则，遍历图\(G\)中的每个连通分量，并判断每个连通分量是否有环即可。算法由HAVE-CYCLE给出，由于\(|E|\le |V|-1\)，因此其时间复杂度为\(O(|V|)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
DFS-C(G, u, fa)
  u.vis = True
  for each v in G.Adj[u]
    if v != fa
      if v.vis == True
        return True
  return False

HAVE-CYCLE(G)
  if |G.E| ≥ |G.V|
    return True
  for each u in G.V
    u.vis = False
  for each u in G.V
    if u.vis == False
      if DFS-C(G, u, NIL)
        return True
  return False

20.4-4

算法TOPOLOGICAL-SORT生成的节点序列中，不能保证坏边的数量最少。

令有向图\(G=(V,E),V=\{a,b,c,d\},E\{(a,b),(b,c),(a,d),(d,c),(c,a)\}\)。如下图所示：

如果按照\(c,a,b,d\)的顺序发现\(G\)中的所有节点，那么每个节点的时间戳如图所示，最终产生的拓扑序列为\((c,d,a,b)\)，它将会产生\(2\)条坏边\((b,c),(d,c)\)。然而序列\((a,b,d,c)\)只产生\(1\)条坏边（如右图所示）。

20.4-5

我们将使用队列保存所有入度为\(0\)的节点。队列每弹出一个节点，那么就将这个节点的所有出边删除，如果后续节点有的入度变成了\(0\)，那么将这个节点加入队列中。整个算法由TOPOLOGICAL-SORT-BFS给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
TOPOLOGICAL-SORT-BFS(G)
  let order be new array
  Q = ∅
  for each u in G.V
    u.deg = G.Adj[u].size
    if u.deg == 0
        ENQUEUE(Q, u)
  while Q != ∅ 
    u = DEQUEUE(Q)
    INSERT(order, u)
    for each v in G.Adj[u]
      v.deg = v.deg - 1
      if v.deg == 0
        ENQUEUE(Q, v)
  if order.size != |G.V|
    return NIL
  else
    return order

给定的其中一个拓扑序列即为节点的出队序列。由于每个节点最多只会入队，出队一次，因此第11-14行的循环每个节点只会被运行一次，最终算法TOPOLOGICAL-SORT-BFS的时间复杂度为\(O(V+E)\)。

当\(G\)中存在环时，环中的所有节点将会无法进入队列。因此，第8行的while循环执行次数将会小于\(|V|\)。最终构造出来的侯选序列order大小也不等于\(|V|\)，由此这个图没有对应的拓扑序列。