Algorithms第3章及少量习题

第三章的主要思想就是DFS。讲了图上的DFS操作，然后讲了各种应用。这章默认图都是用邻接矩阵存的。

  1. procedure explore(G, v)
  2. Input: G = (V, E) is a graph;
  3. Output: visited(u) is set to true for all nodes u reachable from v
  5. visited(v) = true
  6. previstit(v)
  7. for each edge(v,u) in E:
  8. if not visited(u); explore(u)
  9. postvisit(v)
  11. procedure dfs(G)
  12. for all v in V
  13. visited(v) = false
  14. for all v in V
  15. if not visited(v) explore(v)
  18. procedure previsit(v)
  19. pre[v] = clock
  20. clock = clock+1
  22. procedure postvisit(v)
  23. post[v] = clock
  24. clock = clock+1

上面的代码就是这章里面所用到的所有代码了，也是DFS的整个代码，首先对于每个点，如果没有被访问过，那么就从这个点开始进行DFS，也就是explore过程，explore过程中，会访问和当前点相连的所有点[即当前点的可达点]，previst和postvisit过程只是记录每个点的pre值和post值，这个值在某些方面还是很有用的，后面会说到。这整个DFS的时间复杂度是O(V+E)的，每个点和每条边都只访问一次。

在有向图中，对边进行了一些其他的定义
Tree edges: 指向儿子节点的边
Forward edges：从一个点指向非儿子后继节点的边
Back edges： 从一个点指向其祖先节点的边
Cross edges： 既不指向后继节点也不指向祖先节点的边

对于不同的边，这些点的pre值和post值的关系如下所示
pre/post ordering for(u,v) Edge type
pre[u] pre[v] post[v] post[u] tree/forward
pre[v] pre[u] post[u] post[v] back
pre[v] post[v] pre[u] post[u] cross

接下来将的是DAG[directed acyclic graphs]也就是有向无环图。在DAG中，每个点的后继节点的post值都会比当前节点的小，每个DAG至少有一个源点，一个汇点。DAG延伸出来的就是强联通分量了。

对于有向图，对所有的对 in V，都有从u到v的路径，那么就是强联通图，这里<1,2>和<2,1>表示不同的顶点对。如果我们从一个有向图的汇联通分量中的某个点开始进行DFS搜索的话，那么最后会且仅会把整个汇联通分量的点都找出来。这样的话我们如果知道某个汇联通分量里面的一个点，那么就可以知道整个汇联通分量，现在的问题是(I)怎么知道汇联通分量里面的一个点，和(II)求得一个汇联通分量之后要怎么做？

我们知道对于汇点[把联通分量缩成一个点]来说，我们没有好的方法可以容易，轻松的求得，但是对于源点我们就有比较简单的方法可以得到。首先我们可以知道，如果一个点的post值最高的话，那么这个点一定是源点，这个可以从两方面来证明，如果C和C’是图的两个联通分量，且有一条从C到C‘的边，那么C中的所有点的post值的最大值一定回比C’中所有点的post值的最大值要大。因为，如果我们的DFS是从C中开始的话，那么开始的那个点的post值比C‘中所有点的post值都要大；如果是从C’中开始搜索的话，那么先搜索完整个C‘联通分量，然后再搜索C联通分量，这样的话，所有在C中的点的post值比在C’中的点的post值都要大。到此得证。知道这个之后，我们就可以解决问题(I)了，我们可以把有向图反向之后，进行一次DFS，这样的话，post值最大的一定是反向之后的源点，也就是原图的汇点了。对于问题(II)那么我们可以先把找出来的联通分量去掉，然后再在剩余的点中找post值最大的，这个点一定是剩下的图中的汇点，上面的证明可以保证这一点。

所以对于寻找一个图的强联通分量来说，我们只需要对图反向，然后在反向图中进行一次DFS，得到所有点的post值，然后根据post值从大到小的顺序在原图上进行一次DFS，这样就可以得到整个图的所有联通分量了。总时间还是线性的，就相当于2次DFS所用的时间。

接下来是后面几个习题，这几个习题是在这本书的网站上找的几个习题，并不是书中所有的习题。

1.给出一个图，要标出每个点的pre/post值。
这个只需要细心一点就行来

2.对于一个给定的图，用线性的方法把图进行反向。
这个可以循环所有点v，对 in E把v加到u的出边就行了，这样我们只需要循环每个点，每条边1次，所以是线性的

3.证明，无向图中，所有点的度数和是边数的2倍
每条边对两个点共享来度数，总的来说就变成来所有点的度数和是边数的2倍

4.在无向图中，计算每个点的邻接点的数目
这个直接循环所有点就行来，对于边那么u点的邻接点和v点的邻接点都+1就行来。

5.用非递归的方法实现explore

  1. procedure explore(G, u)
  3. S = (empty stack)
  4. push(S, u)
  5. while S is not empty:
  6. v = top(S)
  7. if not visited[v]:
  8. visited[v] = true
  9. previsit(v)
  10. if there is an edge (v, w) in E with visited[w] = false:
  11. push(S, w)
  12. else: (we’re done with v, the node at the top of the stack)
  13. pop(S)

  14. postvisited(v)


6.某学校需要对课表进行安排，某些课必须在另外一些课的前面上。每个学生每学期选多少门课都没关系，问对于给定的所有课之间的关系，同一个人至少需要多少个学期，才能把所有的课修完。
首先我们可以用线性时间计算出每个点的入度，并把入度为0 的点加到队列currL中。然后利用如下过程可以处理剩下的问题，下面的过程中in表示每个点的入度，currL表示当前入度为0的点

  • time = 0

  • repeat until currL is empty:
  • time = time + 1
  • nextL = empty list
  • for all u in currL:
  • for all (u, w) in E
  • in[w] = in[w] - 1
  • if(in[w] is 0)
  • add w to nextL
  • currL = nextL
  • output time

    • 这样，我们得到的还是线性的时间复杂度。
    另外还想了一种为经过验证的方法[私以为是正确的]，先对图跑一次DFS，然后把所有点然post值降序排列起来，然后，对排好序的点进行扫描，如果相邻的两个点u,v之间有一条边u->v的话，那么学期数就需要加1[初始化为1]，这样的话，最后的数目就是所有的学期数了。

    Comments

    ▲