属性2.2 图搜索函数会检查图中的每条边并标记每个顶点，条件是当且仅当所用的搜索函数标记了包含起始顶点的联通分量中的每个顶点，并检查了其中每条边。
属性2.3 对于邻接矩阵表示的图，其DFS需要的时间与V^2成正比。
属性2.4 对于用邻接表表示的图，其DFS需要的时间与V+E成正比。
2.4 DFS森林的属性
树是图的一种表示，其中顶点对应于图中的各个顶点，而边则对应于图中的各条边。
两种明显不同的边：
1.表示一个递归调用的边（树边）；
2.将一个顶点与其在DFS树种的一个祖先相连的边，而且该祖先并非其父结点（回边）。
在DFS树中，对于表示一条树边的从v到w的链接，我们将它称为：
1.树链接，如果w未做标记；
2.父链接，如果st[w]为v；
另外一棵DFS树中，对于表示一条回边的从v到w的链接，我们将它称为：
1.回链接，如果ord[w]
2.下链接，如果ord[w]>ord[v]。
图中的每条边要么表示为一条树链接和一条父链接，要么表示为一条下链接和一条回链接。
树链接对应的DFS是遇到了树边的第一个表示，这将导致一个递归调用（指向尚未见过的顶点）；父链接对应的DFS为遇到了树边另一个表示（第二个表示是在第一次递归调用中走过邻接表时遇到的），并忽略此链接。回链接对应的DFS是遇到了回边的第一个表示，它指向一个顶点，而对该顶点的递归搜索函数尚未完成；下链接对应的DFS为遇到了某个顶点，而且对该顶点的递归搜索在遇到此边时已经完成。
阅读(506) | 评论(0) | 转发(0) |
